The Birthday Paradox

The Birthday paradox หรือ The Birthday problem ถือว่าเป็นปัญหาคลาสสิกของวิชา Probability เลยก็ว่าได้ สำหรับผมแล้วเจอปัญหานี้ในการเรียนคาบแรกเลยของวิชา Probability

สำหรับคนที่รู้จักปัญหานี้แล้วก็ถือว่าหลงเข้ามานะครับ ส่วนใครไม่เคยพบเห็นมาก่อนก็มาดูกันเลย...

Defining the problem

จำเป็นต้องมีคนอยู่ในห้องกี่คนที่จะทำให้มีโอกาสอย่างน้อย 50% ที่จะมีคนเกิดในวันเดียวกันอยู่ในห้อง

เจอครั้งแรกผมงงเลยนะครับว่ามันต้องมีกี่คนกันแน่...แต่ที่งงกว่าในตอนนั้นคือไม่เข้าใจคำถามครับ หนักเลย...

คำถามนี้ถ้าเราสมมติเงื่อนไขบางอย่างขึ้นเชื่อไหมครับว่ามันจะเป็นปัญหาที่ง่ายขึ้นเยอะเลยและสิ่งที่เราจะสมมติกันคือ

เราสมมติว่าไม่มีวันที่ 29 กุมภาพันธ์ ครับดังนั้นในหนึ่งปีจะมีเพียง 365 วันเท่านั้น
เราจะสมมติให้โอกาสที่คนจะเกิดในวันใดๆก็ตามใน 365 วันนี้มีโอกาสเกิดเท่าๆกัน เราสมมติแบบนี้เพื่อตัดปัจจัยของเทศที่มีผลต่อการเกิดของคนออก ยกตัวอย่างเช่น คนในประเทศไทยน่าจะเกิด 9 เดือนหลังจากวันวาเลนไทน์มากกว่าคนที่เกิด 9 เดือนหลังจากวันวิสาขบูชา(คนไทยอาจจะถือพรหมจรรย์ในวันพระครับ)
การเกิดของแต่ละคนเป็นอิสระต่อกัน หมายถึงว่าการที่คนหนึ่งคนเกิดในวันใดๆก็ตามจะไม่ส่งผลอะไรทั้งนั้นถึงการเกิดของคนอื่นๆ (ก็ดูเป็นเงื่อนไขที่ธรรมชาตินะครับ)

เราจะได้ปัญหาที่ชัดเจนมากขึ้นว่า

สมมติให้โอกาสที่คนจะเกิดในแต่ละวันมีโอกาสเท่ากันและการเกิดของแต่ละคนเป็นอิสระต่อกัน(ไม่คิดถึงวันที่ 29 กุมภาพันธ์) จะต้องมีคนอยู่ในห้องกี่คนที่จะทำให้มีโอกาสอย่างน้อย 50% ที่จะมีคนเกิดในวันเดียวกันอยู่ในห้อง

Solving the problem

ตอบไวๆเลยต้องมีมากกว่า 2 คนแน่นอนครับ(ฮ่าๆๆ) เพราะเราต้องการให้มีคนเกิดซำ้วันกันหนิและต้องมีคนน้อยกว่า 365 คนแน่นอนเพราะโอกาสที่ใน 365 คนจะไม่มีคนที่เกิดวันเดียวกันเลยนั้นน้อยกว่า 50% มากจึงทำให้โอกาสมีมากกว่า 50% มากเลยที่ในห้องที่มีคน 365 คนจะมีวันเกิดวันเดียวกัน(เรากำลังคิดกรณีสุดโต่งอยู่)
ดังนั้นช่วงของคำตอบควรจะอยู่ใน [2,365]

แล้วถ้ามีคนที่ไม่ได้เกิดวันเดียวกันเกินครึ่งของปีอยู่ในห้องแล้วหละ คนถัดไปที่เดินเข้าไปในห้องควรจะมีโอกาสอย่างน้อย 50% ที่จะมีวันเกิดตรงกับใครสักคนในห้องแล้วสิ
365/2=182.5 ปัดเป็น 183 งั้นถ้ามีคน 183 คน(เกินครึ่ง)ไม่เกิดวันเดียวกันเลยดังนั้นคนที่ 184 ควรจะมีโอกาสอย่างน้อย 50% ที่จะมีวันเกิดตรงกับใครสักคนในห้องแล้วใช่ไหม
ดังนั้นช่วงของคำตอบควรจะอยู่ใน [2,184]

เรามาคำนวณกันดีกว่าครับ
วิธีแรก : เราจะหาโอกาสที่จะมีอย่างน้อย 2 คนจากกลุ่มคน n คนที่จะมีวันเกิดเป็นวันเดียวกัน เราจะเพิ่มจำนวนคนไปเรื่อยๆจนกว่าโอกาศที่เราคำนวณออกมาจะมีค่ามากกว่า 50%

กรณี n=2 โอกาสที่จะมีอย่างน้อย 2 คนจากคน 2 คนที่จะมีวันเกิดวันเดียวกันคือ

$(365)(1)/365^2$

ประมาณ 0.27%

กรณี n=3 สำหรับกรณีนี้เราจำเป็นต้องคิดกรณีหยิบย่อยก่อนคือ

โอกาสที่คนที่ 1 กับคนที่ 2 จะเกิดวันเดียวกันแต่คนที่ 3 เกิดในวันที่ต่างออกไปคือ

$(365)(1)(364)/365^3$

เช่นเดียวกับการที่คนที่ 1 และ 3 เกิดวันเดียวกันแต่คนที่ 2 ไม่ และสุดท้ายคือคนที่ 2 และ 3 เกิดวันเดียวกันแต่ไม่เป็นวันเดียวกันกับคนที่ 1
และโอกาสที่ทั้งสามคนเกิดในวันเดียวกันคือ $(365)/365^3$

ดังนั้นโอกาสที่จะมีอย่างน้อย 2 คนจาก 3 คนมีวันเกิดวันเดียวกันคือ

$[(365)(1)(364) + (365)(364)(1) + (364)(365)(1) + (365)(1)(1)]/365^3$

ประมาณ 0.82%

กรณี n=4

คิดต่อจนกว่าจะได้ค่าโอกาสที่มากกว่า 50% วิธีนี้แค่คิดกรณีที่ 3 ก็เริ่มปวดหัวแล้วครับ แล้วว่ามันจะไปถึง 50% คงท้อใจไปก่อนหรือไม่ก็นับกรณีหยิบย่อยผิดครับ

วิธีที่สอง : เราจะ Focus ไปที่ complementary event แทนนั่นก็คือเราจะไปหาความน่าจะเป็นที่คน n คนจะไม่เกิดวันเดียวกันเลยแทนแล้วถ้าค่ามันใกล้ 50% เท่าไหร่แต่ไม่เกินนั่นแหละคือคำตอบของเรา

เพราะถ้า complementary event มีโอกาสเกิดน้อยกว่า 50% แล้ว เหตุการณ์ที่เราสนใจแต่แรกมันก็จะมีโอกาสเกิดมากว่า 50% นั่นเอง

โอกาสที่คน n คนจะไม่เกิดวันเดียวกันเลยหาได้จาก

$(365/365)*(364/365)*...*((365-(n-1))/365)$

ดังนั้นโอกาสที่จะมีอย่างน้อย 2 คนเกิดวันเดียวกันจาก n คนคือ

$1-[(365/365)*(364/365)*...*((365-(n-1))/365)]$

https://en.wikipedia.org/wiki/Birthday_problem

ถ้าลองคำนวณดูจะได้ว่า ถ้า n=23 จะมีโอกาส 50.7% ที่จะมีอย่างน้อย 2 คนเกิดวันเดียวกัน

ดังนั้นเราจึงตอบคำถามได้ว่าต้องการคน 23 คนในห้องที่จะทำให้มีโอกาสมากกว่า 50% ที่จะมีอย่างน้อย 2 คนเกิดวันเดียวกัน

ปัญหา The Birthday Problem นี้ความ Paradox ของมันก็อยู่ตรงที่ จริงๆแล้วใช้คนแค่ 23 คนเอง... ซึ่งอาจน้อยกว่าที่คาดไว้ถ้าเราเดาการเพิ่มขึ้นของโอกาสเป็นไปแบบ linear

เราจะเอาปัญหานี้ไปใช้ในชีวิตได้อย่างไร เช่น

ถ้าวันหนึ่งคิดอยากสะสมของเล่นที่แถมในถุงขนมขึ้นมาแล้วถามตัวเองว่าจะต้องซื้อกี่ถุงถึงจะได้ของเล่นซ้ำที่มีแล้วด้วยความน่าจะเป็นต่างๆตามที่อยากกำหนด

ใครเป็นโอตะก็อยากจะเก็บการ์ด BNK ก็ว่าไปครับ

ปล. ขอบคุณความรู้จาก The probability lifesaver
ปล. ขอบคุณที่อ่านจนจบครับ