ปัญหาวันเกิด

ปัญหาวันเกิด หรือ ปฏิทรรศน์วันเกิด ในเรื่องทฤษฎีความน่าจะเป็น เกี่ยวข้องกับความน่าจะเป็นที่กลุ่มคนซึ่งถูกเลือกโดยการสุ่ม "n" คน จะมีบางคู่ในกลุ่มที่มีวันเกิดตรงกัน หากพิจารณาตามหลักรังนกพิราบ ความน่าจะเป็นดังกล่าวจะเป็น 100% ถ้าจำนวนคนในกลุ่มมี 367 คน (เนื่องจากวันที่เป็นไปได้ทั้งหมดมี 366 วัน รวม 29 กุมภาพันธ์ด้วย) อย่างไรก็ตาม ความน่าจะเป็น 99% จะเกิดกับกลุ่มคนเพียง 57 คน และความน่าจะเป็น 50% จะเกิดกับกลุ่มคนเพียง 23 คน การสรุปเหล่านี้ใช้พื้นฐานบนสมมติฐานว่า แต่ละวันของปีมีความเป็นไปได้ที่จะเป็นวันเกิดอย่างเท่าเทียมกัน (ยกเว้น 29 กุมภาพันธ์)
คณิตศาสตร์ที่อยู่เบื้องหลังปัญหานี้นำไปสู่ปัญหาการโจมตีทางวิทยาการเข้ารหัสลับอันเป็นที่รู้จักเรียกว่า การโจมตีวันเกิด ซึ่งใช้ตัวแบบความน่าจะเป็นนี้ลดความซับซ้อนในการเจาะฟังก์ชันแฮช
ความเข้าใจในตัวปัญหา.
ปัญหาวันเกิดถามว่า คนหนึ่งคนใดในกลุ่มที่กำหนด มีวันเกิดตรงกับคนอื่นคนใดหรือไม่ มิได้ถามเฉพาะเจาะจงว่าตรงกับคนหนึ่งเพียงคนเดียวหรือไม่
ตัวอย่างที่ให้มาก่อนหน้านี้คือกลุ่มคน 23 คน การเปรียบเทียบวันเกิดของคนแรกกับวันเกิดของคนอื่นจะมีโอกาส 22 ครั้งเพื่อหาว่าวันเกิดตรงกันหรือไม่ วันเกิดของคนที่สองกับวันเกิดของคนอื่นก็จะมีโอกาส 21 ครั้ง วันเกิดของคนที่สามก็จะมีโอกาส 20 ครั้ง เป็นเช่นนี้ต่อไปเรื่อย ๆ เพราะฉะนั้นโอกาสรวมทั้งหมดที่จะเปรียบเทียบคือ 22 + 21 + 20 + ... + 1 = 253 ครั้ง ดังนั้นการเปรียบเทียบทุก ๆ คนกับคนอื่นทั้งหมดจะทำได้ 253 วิธีที่แตกต่างกัน (การจัดหมู่) หรือกล่าวได้ว่า กลุ่มคน 23 คนสามารถจับคู่ได้ทั้งหมด <math>\textstyle {23 \choose 2} = \frac{23 \cdot 22}{2} = 253</math> คู่
สมมติว่าวันเกิดทั้งหมดสามารถเป็นไปได้อย่างเท่าเทียมกัน ความน่าจะเป็นที่วันที่ตั้งขึ้นมาจะเป็นวันเกิดของใครสักคน ซึ่งเลือกมาโดยการสุ่มจากประชากรทั้งหมดอยู่ที่ 1/365 (ไม่พิจารณาอธิกวารคือ 29 กุมภาพันธ์) ถึงแม้การจับคู่ภายในกลุ่มคน 23 คน ไม่เทียบเท่าเชิงสถิติศาสตร์กับการเลือกคู่โดยอิสระ 253 คู่ ปฏิทรรศน์วันเกิดจะแปลกประหลาดน้อยลง ถ้ากลุ่มคนถูกพิจารณาว่าเป็นจำนวนคู่ที่เป็นไปได้ทั้งหมด มากกว่าที่จะเป็นจำนวนรายคน
การคำนวณความน่าจะเป็น.
ปัญหาคือการคำนวณความน่าจะเป็นโดยประมาณว่า ในกลุ่มคน "n" คน จะมีอย่างน้อยสองคนที่มีวันเกิดตรงกัน สำหรับกรณีง่ายสุดคือไม่สนใจความแปรปรวนในการแจกแจง เช่นปีอธิกสุรทิน ฝาแฝด ความแปรปรวนเชิงฤดูกาลหรือวันในสัปดาห์ และสมมติว่าวันเกิดที่เป็นไปได้ 365 วันอย่างเท่าเทียมกัน การแจกแจงวันเกิดในชีวิตจริงไม่เป็นเอกรูปเพราะทุกวันมิได้มีโอกาสอย่างเท่าเทียมกัน
ถ้าให้ "P"("A") คือความน่าจะเป็นที่อย่างน้อยสองคนในกลุ่มมีวันเกิดตรงกัน เราอาจคำนวณง่ายขึ้นจาก "P"("A"′) คือความน่าจะเป็นที่ไม่มีสองคนใดเลยที่มีวันเกิดตรงกัน เนื่องจาก "A" และ "A"′ เป็นความน่าจะเป็นเพียงสองประการที่จะเกิดขึ้นได้และเป็นเหตุการณ์ไม่เกิดร่วม ดังนั้นเราจะได้ "P"("A") = 1 − "P"("A"′)
คำตอบของปัญหาที่เผยแพร่อย่างกว้างขวางสรุปว่า กลุ่มคน 23 คนก็เพียงพอที่จะทำให้ "P"("A") มีค่ามากกว่า 50% การคำนวณ "P"("A") ต่อไปนี้จะใช้กลุ่มคน 23 คนมาเป็นตัวอย่าง
เมื่อเหตุการณ์เป็นอิสระซึ่งกันและกัน ความน่าจะเป็นของเหตุการณ์ทั้งหมดที่เกิดขึ้น จะเท่ากับผลคูณของความน่าจะเป็นของแต่ละเหตุการณ์ที่เกิดขึ้น เพราะฉะนั้น "P"("A"′) จึงสามารถแยกได้เป็นเหตุการณ์อิสระ 23 เหตุการณ์ และคำนวณได้จาก "P"(1) × "P"(2) × "P"(3) × ... "P"(23)
เหตุการณ์อิสระ 23 เหตุการณ์นี้สอดคล้องกับจำนวนคน 23 คนและสามารถนิยามไปตามลำดับ แต่ละเหตุการณ์สามารถนิยามว่าคนนั้นจะไม่มีวันเกิดตรงกับคนอื่นคนใดที่ได้วิเคราะห์ไปแล้วก่อนหน้า สำหรับเหตุการณ์ที่ 1 คือไม่มีคนอื่นคนใดก่อนหน้านี้ให้วิเคราะห์เลย เพราะฉะนั้นความน่าจะเป็น "P"(1) ซึ่งคนแรกไม่มีวันเกิดตรงกับคนอื่นคนใดที่ได้วิเคราะห์ไปแล้วก่อนหน้าเท่ากับ 1 หรือ 100% หรือเขียนในรูปแบบ 365/365 โดยไม่พิจารณาอธิกวารสำหรับการวิเคราะห์นี้ ส่วนเหตุผลจะได้ปรากฏชัดเจนต่อไป
สำหรับเหตุการณ์ที่ 2 คือมีเพียงคนที่หนึ่งที่ได้วิเคราะห์แล้วก่อนหน้านี้ สมมติว่าวันเกิดเป็นไปได้อย่างเท่าเทียมกัน 365 วันเช่นเดิม ความน่าจะเป็น "P"(2) ซึ่งคนที่สองมีวันเกิดต่างกับคนที่หนึ่งเท่ากับ 364/365 นั่นเป็นเพราะถ้าคนที่สองเกิดในวันใดก็ได้ในจำนวน 364 วันที่เหลือ ทำให้คนที่หนึ่งกับคนที่สองมีวันเกิดไม่ตรงกัน
ในทางเดียวกัน ถ้าคนที่สามเกิดในวันใดก็ได้ในจำนวน 363 วันที่เหลือ ทำให้ทั้งคนที่หนึ่ง ที่สอง ที่สาม มีวันเกิดไม่ตรงกันเลย จะได้ความน่าจะเป็น "P"(3) เท่ากับ 363/365
การวิเคราะห์เช่นนี้ดำเนินต่อไปจนกระทั่งถึงคนที่ยี่สิบสาม ซึ่งความน่าจะเป็นที่วันเกิดจะไม่ตรงกับคนที่ได้วิเคราะห์ไปแล้วก่อนหน้านี้เลย "P"(23) เท่ากับ 343/365
"P"("A"′) เท่ากับผลคูณของความน่าจะเป็นรายเหตุการณ์เหล่านี้ นั่นคือ
 "P"("A"′) = 365/365 × 364/365 × 363/365 × 362/365 × ... × 343/365
สมการดังกล่าวสามารถดึงตัวประกอบร่วมได้เป็น
 "P"("A"′) = (1/365)23 × (365 × 364 × 363 × 362 × ... × 343)
ประเมินค่าออกมาจะได้ "P"("A"′) ≈ 0.492703
ดังนั้น "P"("A") ≈ 1 − 0.492703 = 0.507297 หรือ 50.7297%
กระบวนการนี้สามารถทำให้เป็นกรณีทั่วไปสำหรับกลุ่มคน "n" คน เมื่อ "p"("n") คือความน่าจะเป็นที่อย่างน้อยสองคนในกลุ่ม "n" คนมีวันเกิดตรงกัน เราคำนวณง่ายขึ้นด้วย "p̅"("n") คือความน่าจะเป็นที่วันเกิดของ "n" คนแตกต่างกันทั้งหมด ตามหลักรังนกพิราบ "p̅"("n") จะเป็นศูนย์เมื่อ "n" > 365 และเมื่อ "n" ≤ 365 จะได้ว่า
<math> \begin{align} \bar p(n) &= 1 \times \left(1-\frac{1}{365}\right) \times \left(1-\frac{2}{365}\right) \times \cdots \times \left(1-\frac{n-1}{365}\right) \\ &= { 365 \times 364 \times \cdots \times (365-n+1) \over 365^n } \\ &= { 365! \over 365^n (365-n)!} = \frac{n!\cdot{365 \choose n}}{365^n} = \frac{^{365}P_n}{365^n}\end{align} </math>
โดยสัญลักษณ์ ! คือตัวดำเนินการแฟกทอเรียล <math>\textstyle {365 \choose n}</math> คือสัมประสิทธิ์ทวินาม และ <math>{^{k}P_r}</math> หมายถึงการเรียงสับเปลี่ยน
สมการดังกล่าวแสดงข้อเท็จจริงว่า สำหรับคนที่หนึ่งไม่มีคนใดที่มีวันเกิดตรงกัน (365/365) สำหรับคนที่สองก็ไม่มีวันเกิดตรงกับคนที่หนึ่ง (364/365) สำหรับคนที่สามก็ไม่มีวันเกิดตรงกับคนที่หนึ่งและที่สอง (363/365) ฯลฯ และในกรณีทั่วไปวันเกิดของคนที่ "n" ก็จะไม่มีวันเกิดตรงกับ "n" − 1 คนที่อยู่ก่อนหน้า
เหตุการณ์ที่อย่างน้อยสองคนจากกลุ่มคน "n" คนมีวันเกิดตรงกัน คือเหตุการณ์เติมเต็มที่วันเกิดของ "n" คนแตกต่างกันทั้งหมด เพราะฉะนั้นความน่าจะเป็น "p"("n") จะมีค่าเท่ากับ
<math> p(n) = 1 - \bar p(n) \, </math>
ความน่าจะเป็นนี้มีค่าเกินกว่า 1/2 เมื่อ "n" = 23 (ค่าจริงประมาณ 50.7%) ตารางต่อไปนี้แสดงความน่าจะเป็นสำหรับ "n" อื่น ๆ บางค่า (โดยไม่พิจารณาปีอธิกสุรทินตามที่ได้อธิบายแล้วด้านบน)
การประมาณค่า.
การกระจายอนุกรมเทย์เลอร์ของฟังก์ชันเลขชี้กำลัง (ค่าคงตัว e ≈ 2.718281828)
<math> e^x = 1 + x + \frac{x^2}{2!}+\cdots </math>
สามารถประมาณค่า "e""x" อันดับที่หนึ่งเมื่อ "x" ≪ 1 ดังนี้
<math> e^x \approx 1 + x \ </math>
เพื่อใช้การประมาณนี้แก่นิพจน์แรกที่มาจาก "p̅"("n") กำหนดให้ "x" = −"i"/365 ดังนั้นเราจะได้
<math> e^{-i/365} \approx 1 - \frac{i}{365} \ </math>
จากนั้นแทนที่ "i" ด้วยจำนวนเต็มไม่เป็นลบสำหรับแต่ละพจน์ในสูตรของ "p̅"("n") จนกระทั่ง "i" = "n" − 1 ตัวอย่างเช่นเมื่อ "i" = 1 จะได้
<math> e^{-1/365} \approx 1 - \frac{1}{365} \ </math>
นิพจน์แรกที่มาจาก "p̅"("n") จึงสามารถประมาณค่าได้ดังนี้
<math>
\bar p(n) & \approx 1 \times e^{-1/365} \times e^{-2/365} \cdots e^{-(n-1)/365} \\
& = 1 \times e^{-(1+2+ \cdots +(n-1))/365} \\
</math>
เพราะฉะนั้น
<math> p(n) = 1-\bar p(n) \approx 1 - e^{- n(n-1)/(2 \times 365)} </math>
การประมาณที่หยาบกว่าของสูตรดังกล่าวคือ
<math> p(n) \approx 1-e^{- n^2/(2 \times 365)} </math>
ซึ่งยังคงแม่นยำพอใช้ได้ ดังที่เห็นจากกราฟในภาพประกอบ
จากการประมาณค่าดังกล่าว แนวทางที่เหมือนกันสามารถใช้ได้กับ "คน" และ "วัน" จำนวนเท่าใดก็ได้ ถ้าให้จำนวนวันเป็น "n" วันแทนที่จะเป็น 365 วัน ให้จำนวนคน "m" คน และ "m" ≪ "n" จากแนวทางข้างต้นเราจะได้ผลสำเร็จเป็น "Pr"[("m", "n")] คือความน่าจะเป็นที่อย่างน้อยสองคนในกลุ่ม "m" คน มีวันเกิดตรงกันภายใน "n" วันที่กำหนด ดังนี้
<math> Pr[(m, n)] \approx 1-e^{-m^2 / 2n} \ </math>
การยกกำลังอย่างง่าย.
ความน่าจะเป็นที่คนสองคนไม่มีวันเกิดตรงกันเท่ากับ 364/365 หากกลุ่มคนมีจำนวน "n" คน จะสามารถจับคู่ได้ "C"("n", 2) = "n"("n" − 1)/2 คู่ หรือเรียกได้ว่ามี "C"("n", 2) เหตุการณ์ ความน่าจะเป็นที่คนสองคนไม่มีวันเกิดตรงกันในกลุ่มคนดังกล่าว สามารถประมาณได้จากเหตุการณ์เหล่านี้ซึ่งสมมติว่าเป็นอิสระต่อกัน โดยคูณความน่าจะเป็นของพวกมันเข้าด้วยกัน กล่าวอย่างสั้นคือ 364/365 สามารถคูณกับตัวเองเป็นจำนวน "C"("n", 2) ตัว จะได้
<math>\bar p(n) \approx \left(\frac{364}{365}\right)^{C(n,2)}</math>
เนื่องจากสิ่งนี้คือความน่าจะเป็นที่ไม่มีใครมีวันเกิดตรงกัน ดังนั้นความน่าจะเป็นที่จะมีใครบางคนมีวันเกิดตรงกันก็คือ
<math>p(n) \approx 1 - \left(\frac{364}{365}\right)^{C(n,2)}</math>
การประมาณปัวซง.
ใช้การประมาณปัวซงสำหรับทวินามกับกลุ่มคน 23 คน
<math>\mathrm{Poi}\left(\frac{C(23, 2)}{365}\right) =\mathrm{Poi}\left(\frac{253}{365}\right) \approx \mathrm{Poi}(0.6932)</math>
<math>\Pr(X>0)=1-\Pr(X=0) \approx 1-e^{-0.6932} \approx 1-0.499998=0.500002</math>
ผลลัพธ์มีค่ามากกว่า 50% เช่นเดียวกับที่ได้อธิบายไว้ก่อนหน้านี้
การประมาณจำนวนคน.
การประมาณจำนวนคนเท่าที่จำเป็นที่จะทำให้เกิดโอกาส 50% เป็นอย่างน้อยที่จะมีวันเกิดตรงกัน โดยแฟรงก์ เอช. แมทิส สามารถหาได้จากสูตรดังนี้
<math>n \approx \frac{1}{2} + \sqrt{\frac{1}{4} - 2 \times 365 \times \ln(0.5)} = 22.999943</math>
นี่เป็นผลลัพธ์ของการประมาณที่ดี ซึ่งเหตุการณ์ 1 ใน "k" ของความน่าจะเป็นจะมีโอกาสเกิดขึ้น 50% เป็นอย่างน้อย ถ้าเหตุการณ์นั้นเกิดซ้ำ "k" ln 2 ครั้ง 
ตารางความน่าจะเป็น.
ช่องสีขาวในตารางนี้แสดงจำนวนสมาชิกของแฮชที่จำเป็น ที่ทำให้ความน่าจะเป็นที่แฮชชนกันตามกำหนด (ตามหลัก) โดยกำหนดปริภูมิแฮชในหน่วยบิตขนาดต่าง ๆ (ตามแถว) อุปมากับปัญหาวันเกิดได้ว่า "ขนาดของปริภูมิแฮช" คล้ายกับ "จำนวนวันที่ใช้ได้", "ความน่าจะเป็นที่แฮชชนกัน" คล้ายกับ "ความน่าจะเป็นที่คนมีวันเกิดตรงกัน", และ "จำนวนสมาชิกของแฮชที่จำเป็น" ก็คล้ายกับ "จำนวนคนที่จำเป็นในกลุ่ม" แน่นอนว่าใครก็ตามสามารถใช้แผนผังนี้เพื่อกำหนดขนาดของแฮชน้อยสุดที่จำเป็น (โดยกำหนดขอบเขตบนของแฮชและความน่าจะเป็นของความผิดพลาด) หรือความน่าจะเป็นที่แฮชชนกันได้ (เพื่อหาจำนวนแฮชตายตัวและความน่าจะเป็นของความผิดพลาด)
ยกตัวอย่างเพื่อการเปรียบเทียบ ความน่าจะเป็น 10−18 ถึง 10−15 คืออัตราความผิดพลาดบิตที่แก้ไขไม่ได้ของฮาร์ดดิสก์ทั่วไป ฟังก์ชันแฮช 128 บิตอย่างเช่น เอ็มดี5 จึงควรดำรงอยู่ในช่วงนั้นจนกว่าจะแฮชเอกสารไปแล้วประมาณ 8.2 แสนล้านเอกสารในทางทฤษฎี ถึงแม้ว่าผลลัพธ์ที่เป็นไปได้ของมันจะมีได้มากยิ่งกว่านั้น
ขอบเขตบน.
การอ้างเหตุผลด้านล่างดัดแปลงจากการอ้างเหตุผลของพอล ฮาลโมส 
ความน่าจะเป็นที่ไม่มีวันเกิดของคนใดตรงกัน ดังที่ได้อธิบายไว้ด้านบนคือ
<math>1-p(n) = \bar p(n) = \prod_{k=1}^{n-1}\left(1-{k \over 365}\right)</math>
จากย่อหน้าก่อน ๆ นั้น สิ่งที่สนใจคือค่าของ "n" น้อยสุดที่ทำให้ "p"("n") > 1/2 หรือกล่าวอีกนัยหนึ่ง ค่าของ "n" น้อยสุดที่ทำให้ "p̅"("n") < 1/2
ใช้อสมการ 1 − "x" < "e"−"x" จากนิพจน์ด้านบนซึ่งเราได้แทนค่า 1 − "k"/365 ด้วย "e"−"k"/365 จะได้ว่า
<math>\bar p(n) = \prod_{k=1}^{n-1}\left(1-{k \over 365}\right) < \prod_{k=1}^{n-1}\left(e^{-k/365}\right) = e^{-(n(n-1))/(2\times 365)}</math>
เพราะฉะนั้น นิพจน์ดังกล่าวมิได้เป็นเพียงแค่การประมาณค่า แต่ยังเป็นขอบเขตบนของ "p̅"("n") ด้วย
อสมการนี้
<math>e^{-(n(n-1))/(2\cdot 365)} < \frac{1}{2}</math>
แสดงนัยถึง "p̅"("n") < 1/2 แก้อสมการเพื่อหาค่า "n" จะได้
<math>n^2-n > 2\times365\ln 2 \,\!</math>
730 ln 2 มีค่าประมาณ 505.997 ซึ่งน้อยกว่า 506 เล็กน้อย ค่าของ "n"2 − "n" ขึ้นมาถึง 506 เมื่อ "n" = 23 ดังนั้น 23 คนก็เพียงพอที่จะเป็นคำตอบ
อย่างไรก็ดี การแก้สมการ "n"2 − "n" = 2 · 365 ln 2 เพื่อหาค่า "n" ก็จะเป็นสูตรประมาณของแฟรงก์ เอช. แมทิส ดังที่ได้แสดงไว้แล้ว
การได้มานี้แสดงเพียงว่า 23 คนเป็นจำนวนคนที่ "มากสุด" ที่จำเป็นเพื่อให้แน่ใจว่าวันเกิดจะตรงกันด้วยโอกาสครึ่งต่อครึ่ง กล่าวคือมันเปิดโอกาสความเป็นไปได้ว่าหาก "n" เท่ากับ 22 คนหรือน้อยกว่าก็อาจได้ผลเช่นกัน