# ปัญหาวันเกิด
ปัญหาวันเกิด หรือ ปฏิทรรศน์วันเกิด คำว่า "ปฏิทรรศน์" นี้มิได้หมายถึงความรู้สึกที่นำไปสู่ความขัดแย้งทางตรรกศาสตร์ แต่ถูกหยิบยกขึ้นเนื่องจากความจริงทางคณิตศาสตร์ขัดแย้งกับการหยั่งรู้ด้วยตนเอง กล่าวคือคนส่วนใหญ่มักประมาณว่าโอกาสที่คนสองคนจะมีวันเกิดตรงกันต้องน้อยกว่า 50% อย่างมาก สำหรับกลุ่มคน 23 คน ในเรื่องทฤษฎีความน่าจะเป็น เกี่ยวข้องกับความน่าจะเป็นที่กลุ่มคนซึ่งถูกเลือกโดยการสุ่ม n คน จะมีบางคู่ในกลุ่มที่มีวันเกิดตรงกัน หากพิจารณาตามหลักรังนกพิราบ ความน่าจะเป็นดังกล่าวจะเป็น 100% ถ้าจำนวนคนในกลุ่มมี 367 คน (เนื่องจากวันที่เป็นไปได้ทั้งหมดมี 366 วัน รวม 29 กุมภาพันธ์ด้วย) อย่างไรก็ตาม ความน่าจะเป็น 99% จะเกิดกับกลุ่มคนเพียง 57 คน และความน่าจะเป็น 50% จะเกิดกับกลุ่มคนเพียง 23 คน การสรุปเหล่านี้ใช้พื้นฐานบนสมมติฐานว่า แต่ละวันของปีมีความเป็นไปได้ที่จะเป็นวันเกิดอย่างเท่าเทียมกัน (ยกเว้น 29 กุมภาพันธ์)

คณิตศาสตร์ที่อยู่เบื้องหลังปัญหานี้นำไปสู่ปัญหาการโจมตีทางวิทยาการเข้ารหัสลับอันเป็นที่รู้จักเรียกว่า การโจมตีวันเกิด ซึ่งใช้ตัวแบบความน่าจะเป็นนี้ลดความซับซ้อนในการเจาะฟังก์ชันแฮช

thumb|right|300px|กราฟแสดงความน่าจะเป็นโดยการคำนวณ ที่คนอย่างน้อยสองคนจะมีวันเกิดตรงกัน ในระหว่างกลุ่มคนตามจำนวนที่แน่นอน

 ความเข้าใจในตัวปัญหา 
ปัญหาวันเกิดถามว่า คนหนึ่งคนใดในกลุ่มที่กำหนด มีวันเกิดตรงกับคนอื่นคนใดหรือไม่ มิได้ถามเฉพาะเจาะจงว่าตรงกับคนหนึ่งเพียงคนเดียวหรือไม่

ตัวอย่างที่ให้มาก่อนหน้านี้คือกลุ่มคน 23 คน การเปรียบเทียบวันเกิดของคนแรกกับวันเกิดของคนอื่นจะมีโอกาส 22 ครั้งเพื่อหาว่าวันเกิดตรงกันหรือไม่ วันเกิดของคนที่สองกับวันเกิดของคนอื่นก็จะมีโอกาส 21 ครั้ง วันเกิดของคนที่สามก็จะมีโอกาส 20 ครั้ง เป็นเช่นนี้ต่อไปเรื่อย ๆ เพราะฉะนั้นโอกาสรวมทั้งหมดที่จะเปรียบเทียบคือ 22 + 21 + 20 + ... + 1 = 253 ครั้ง ดังนั้นการเปรียบเทียบทุก ๆ คนกับคนอื่นทั้งหมดจะทำได้ 253 วิธีที่แตกต่างกัน (การจัดหมู่) หรือกล่าวได้ว่า กลุ่มคน 23 คนสามารถจับคู่ได้ทั้งหมด  คู่

สมมติว่าวันเกิดทั้งหมดสามารถเป็นไปได้อย่างเท่าเทียมกัน ในความเป็นจริง วันเกิดไม่แจกแจงตลอดทั้งปีอย่างเท่าเทียมกัน การเกิดต่อวันในบางฤดูกาลมีมากกว่าฤดูกาลอื่น แต่เพื่อจุดมุ่งหมายของปัญหานี้ การแจกแจงจะถูกทำให้เป็นเอกรูป (รูปแบบเดียว)  ความน่าจะเป็นที่วันที่ตั้งขึ้นมาจะเป็นวันเกิดของใครสักคน ซึ่งเลือกมาโดยการสุ่มจากประชากรทั้งหมดอยู่ที่  (ไม่พิจารณาอธิกวารคือ 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% หรือเขียนในรูปแบบ  โดยไม่พิจารณาอธิกวารสำหรับการวิเคราะห์นี้ ส่วนเหตุผลจะได้ปรากฏชัดเจนต่อไป

สำหรับเหตุการณ์ที่ 2 คือมีเพียงคนที่หนึ่งที่ได้วิเคราะห์แล้วก่อนหน้านี้ สมมติว่าวันเกิดเป็นไปได้อย่างเท่าเทียมกัน 365 วันเช่นเดิม ความน่าจะเป็น P(2) ซึ่งคนที่สองมีวันเกิดต่างกับคนที่หนึ่งเท่ากับ  นั่นเป็นเพราะถ้าคนที่สองเกิดในวันใดก็ได้ในจำนวน 364 วันที่เหลือ ทำให้คนที่หนึ่งกับคนที่สองมีวันเกิดไม่ตรงกัน

ในทางเดียวกัน ถ้าคนที่สามเกิดในวันใดก็ได้ในจำนวน 363 วันที่เหลือ ทำให้ทั้งคนที่หนึ่ง ที่สอง ที่สาม มีวันเกิดไม่ตรงกันเลย จะได้ความน่าจะเป็น P(3) เท่ากับ 

การวิเคราะห์เช่นนี้ดำเนินต่อไปจนกระทั่งถึงคนที่ยี่สิบสาม ซึ่งความน่าจะเป็นที่วันเกิดจะไม่ตรงกับคนที่ได้วิเคราะห์ไปแล้วก่อนหน้านี้เลย P(23) เท่ากับ 

P(A′) เท่ากับผลคูณของความน่าจะเป็นรายเหตุการณ์เหล่านี้ นั่นคือ
 P(A′) =  ×  ×  ×  × ... × 
สมการดังกล่าวสามารถดึงตัวประกอบร่วมได้เป็น
 P(A′) = 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 จะได้ว่า

โดยสัญลักษณ์ ! คือตัวดำเนินการแฟกทอเรียล  คือสัมประสิทธิ์ทวินาม และ  หมายถึงการเรียงสับเปลี่ยน

สมการดังกล่าวแสดงข้อเท็จจริงว่า สำหรับคนที่หนึ่งไม่มีคนใดที่มีวันเกิดตรงกัน  สำหรับคนที่สองก็ไม่มีวันเกิดตรงกับคนที่หนึ่ง  สำหรับคนที่สามก็ไม่มีวันเกิดตรงกับคนที่หนึ่งและที่สอง  ฯลฯ และในกรณีทั่วไปวันเกิดของคนที่ n ก็จะไม่มีวันเกิดตรงกับ n − 1 คนที่อยู่ก่อนหน้า

เหตุการณ์ที่อย่างน้อยสองคนจากกลุ่มคน n คนมีวันเกิดตรงกัน คือเหตุการณ์เติมเต็มที่วันเกิดของ n คนแตกต่างกันทั้งหมด เพราะฉะนั้นความน่าจะเป็น p(n) จะมีค่าเท่ากับ

ความน่าจะเป็นนี้มีค่าเกินกว่า  เมื่อ n = 23 (ค่าจริงประมาณ 50.7%) ตารางต่อไปนี้แสดงความน่าจะเป็นสำหรับ n อื่น ๆ บางค่า (โดยไม่พิจารณาปีอธิกสุรทินตามที่ได้อธิบายแล้วด้านบน)

thumb|right|300px|กราฟแสดงความน่าจะเป็นโดยประมาณ ที่ไม่มีใครเลยในกลุ่มคน n คนมีวันเกิดตรงกัน สังเกตว่ามาตราส่วนตามแนวตั้งเป็นลอการิทึม (แต่ละขีดจากบนลงล่างลดลงทีละ 1020 เท่า)

 n  p(n) 10  11.7% 20  41.1% 23  50.7% 30  70.6% 50  97.0% 57  99.0% 100  99.99997% 200  99.9999999999999999999999999998% 300  (100 − (6))% 350  (100 − (3))% 365  (100 − (1.45))% 366  100%

 การประมาณค่า 
thumb|right|300px|กราฟแสดงความน่าจะเป็นโดยประมาณ ที่คนอย่างน้อยสองคนจะมีวันเกิดตรงกัน (แดง) และเหตุการณ์เติมเต็มของมัน (น้ำเงิน)
thumb|right|300px|กราฟแสดงความแม่นยำของการประมาณค่าด้วย  (ขาว)
การกระจายอนุกรมเทย์เลอร์ของฟังก์ชันเลขชี้กำลัง (ค่าคงตัว e ≈ 2.718281828)

สามารถประมาณค่า ex อันดับที่หนึ่งเมื่อ x ≪ 1 ดังนี้

เพื่อใช้การประมาณนี้แก่นิพจน์แรกที่มาจาก p̅(n) กำหนดให้ x =  ดังนั้นเราจะได้

จากนั้นแทนที่ i ด้วยจำนวนเต็มไม่เป็นลบสำหรับแต่ละพจน์ในสูตรของ p̅(n) จนกระทั่ง i = n − 1 ตัวอย่างเช่นเมื่อ i = 1 จะได้

นิพจน์แรกที่มาจาก p̅(n) จึงสามารถประมาณค่าได้ดังนี้

เพราะฉะนั้น

การประมาณที่หยาบกว่าของสูตรดังกล่าวคือ

ซึ่งยังคงแม่นยำพอใช้ได้ ดังที่เห็นจากกราฟในภาพประกอบ

จากการประมาณค่าดังกล่าว แนวทางที่เหมือนกันสามารถใช้ได้กับ "คน" และ "วัน" จำนวนเท่าใดก็ได้ ถ้าให้จำนวนวันเป็น n วันแทนที่จะเป็น 365 วัน ให้จำนวนคน m คน และ m ≪ n จากแนวทางข้างต้นเราจะได้ผลสำเร็จเป็น Pr[(m, n)] คือความน่าจะเป็นที่อย่างน้อยสองคนในกลุ่ม m คน มีวันเกิดตรงกันภายใน n วันที่กำหนด ดังนี้

 การยกกำลังอย่างง่าย 
ความน่าจะเป็นที่คนสองคนไม่มีวันเกิดตรงกันเท่ากับ  หากกลุ่มคนมีจำนวน n คน จะสามารถจับคู่ได้ C(n, 2) =  คู่ หรือเรียกได้ว่ามี C(n, 2) เหตุการณ์ ความน่าจะเป็นที่คนสองคนไม่มีวันเกิดตรงกันในกลุ่มคนดังกล่าว สามารถประมาณได้จากเหตุการณ์เหล่านี้ซึ่งสมมติว่าเป็นอิสระต่อกัน โดยคูณความน่าจะเป็นของพวกมันเข้าด้วยกัน กล่าวอย่างสั้นคือ  สามารถคูณกับตัวเองเป็นจำนวน C(n, 2) ตัว จะได้

เนื่องจากสิ่งนี้คือความน่าจะเป็นที่ไม่มีใครมีวันเกิดตรงกัน ดังนั้นความน่าจะเป็นที่จะมีใครบางคนมีวันเกิดตรงกันก็คือ

 การประมาณปัวซง 
ใช้การประมาณปัวซงสำหรับทวินามกับกลุ่มคน 23 คน

ผลลัพธ์มีค่ามากกว่า 50% เช่นเดียวกับที่ได้อธิบายไว้ก่อนหน้านี้

 การประมาณจำนวนคน 
การประมาณจำนวนคนเท่าที่จำเป็นที่จะทำให้เกิดโอกาส 50% เป็นอย่างน้อยที่จะมีวันเกิดตรงกัน โดยแฟรงก์ เอช. แมทิส สามารถหาได้จากสูตรดังนี้

นี่เป็นผลลัพธ์ของการประมาณที่ดี ซึ่งเหตุการณ์ 1 ใน k ของความน่าจะเป็นจะมีโอกาสเกิดขึ้น 50% เป็นอย่างน้อย ถ้าเหตุการณ์นั้นเกิดซ้ำ k ln 2 ครั้ง 

 ตารางความน่าจะเป็น 

 ความยาวสายอักขระฐานสิบหก #บิต ขนาดของปริภูมิแฮช(2#บิต) จำนวนสมาชิกของแฮชที่ทำให้ {ความน่าจะเป็นที่แฮชชนกันอย่างน้อยหนึ่งครั้ง = p} p =  p =  p =  p =  p =  p = 0.1% p = 1% p = 25% p = 50% p = 75% 8 32 4.3 2 2 2 2.9 93 2.9 9.3 5.0 7.7 1.1 16 64 1.8 6.1 1.9 6.1 1.9 6.1 1.9 6.1 3.3 5.1 7.2 32 128 3.4 2.6 8.2 2.6 8.2 2.6 8.3 2.6 1.4 2.2 3.1 64 256 1.2 4.8 1.5 4.8 1.5 4.8 1.5 4.8 2.6 4.0 5.7 (96) (384) (3.9) 8.9 2.8 8.9 2.8 8.9 2.8 8.9 4.8 7.4 1.0 128 512 1.3 1.6 5.2 1.6 5.2 1.6 5.2 1.6 8.8 1.4 1.9

ช่องสีขาวในตารางนี้แสดงจำนวนสมาชิกของแฮชที่จำเป็น ที่ทำให้ความน่าจะเป็นที่แฮชชนกันตามกำหนด (ตามหลัก) โดยกำหนดปริภูมิแฮชในหน่วยบิตขนาดต่าง ๆ (ตามแถว) อุปมากับปัญหาวันเกิดได้ว่า "ขนาดของปริภูมิแฮช" คล้ายกับ "จำนวนวันที่ใช้ได้", "ความน่าจะเป็นที่แฮชชนกัน" คล้ายกับ "ความน่าจะเป็นที่คนมีวันเกิดตรงกัน", และ "จำนวนสมาชิกของแฮชที่จำเป็น" ก็คล้ายกับ "จำนวนคนที่จำเป็นในกลุ่ม" แน่นอนว่าใครก็ตามสามารถใช้แผนผังนี้เพื่อกำหนดขนาดของแฮชน้อยสุดที่จำเป็น (โดยกำหนดขอบเขตบนของแฮชและความน่าจะเป็นของความผิดพลาด) หรือความน่าจะเป็นที่แฮชชนกันได้ (เพื่อหาจำนวนแฮชตายตัวและความน่าจะเป็นของความผิดพลาด)

ยกตัวอย่างเพื่อการเปรียบเทียบ ความน่าจะเป็น  ถึง  คืออัตราความผิดพลาดบิตที่แก้ไขไม่ได้ของฮาร์ดดิสก์ทั่วไป Jim Gray, Catharine van Ingen. Empirical Measurements of Disk Failure Rates and Error Rates ฟังก์ชันแฮช 128 บิตอย่างเช่น เอ็มดี5 จึงควรดำรงอยู่ในช่วงนั้นจนกว่าจะแฮชเอกสารไปแล้วประมาณ 8.2 แสนล้านเอกสารในทางทฤษฎี ถึงแม้ว่าผลลัพธ์ที่เป็นไปได้ของมันจะมีได้มากยิ่งกว่านั้น

 ขอบเขตบน 
การอ้างเหตุผลด้านล่างดัดแปลงจากการอ้างเหตุผลของพอล ฮาลโมส ฮาลโมสได้วิจารณ์รูปแบบของปฏิทรรศน์วันเกิดที่มักจะถูกนำเสนอ ด้วยการคำนวณเชิงตัวเลขในอัตชีวประวัติของเขา เขาเชื่อว่ามันควรใช้เป็นตัวอย่างของมโนทัศน์ทางคณิตศาสตร์ที่นามธรรมมากขึ้น เขาเขียนว่า
"การให้เหตุผลมีพื้นฐานอยู่บนเครื่องมือสำคัญที่ว่าผู้ศึกษาคณิตศาสตร์ทุกคนควรพร้อมที่จะเข้าถึง ปัญหาวันเกิดเคยเป็นการสาธิตที่ยอดเยี่ยมของความได้เปรียบแห่งความคิดอันบริสุทธิ์เหนือการจัดดำเนินการเชิงกล อสมการสามารถได้มาในนาทีสองนาที ในขณะที่การคูณจะใช้เวลายิ่งกว่านั้นมาก และทำให้เกิดความผิดพลาดมากขึ้นไปอีก ไม่ว่าเครื่องมือนั้นจะเป็นดินสอหรือเครื่องคำนวณบนโต๊ะที่ล้าสมัย สิ่งที่เครื่องคิดเลขไม่ได้ให้ผลลัพธ์ออกมานั่นคือความเข้าใจ หรือคุณสมบัติทางคณิตศาสตร์ หรือพื้นฐานที่หนักแน่นสำหรับทฤษฎีวางนัยทั่วไปชั้นสูงยิ่งขึ้น"

ความน่าจะเป็นที่ไม่มีวันเกิดของคนใดตรงกัน ดังที่ได้อธิบายไว้ด้านบนคือ

จากย่อหน้าก่อน ๆ นั้น สิ่งที่สนใจคือค่าของ n น้อยสุดที่ทำให้ p(n) >  หรือกล่าวอีกนัยหนึ่ง ค่าของ n น้อยสุดที่ทำให้ p̅(n) < 

ใช้อสมการ 1 − x < e−x จากนิพจน์ด้านบนซึ่งเราได้แทนค่า 1 −  ด้วย e−k/365 จะได้ว่า

เพราะฉะนั้น นิพจน์ดังกล่าวมิได้เป็นเพียงแค่การประมาณค่า แต่ยังเป็นขอบเขตบนของ p̅(n) ด้วย

อสมการนี้

แสดงนัยถึง p̅(n) <  แก้อสมการเพื่อหาค่า n จะได้

730 ln 2 มีค่าประมาณ 505.997 ซึ่งน้อยกว่า 506 เล็กน้อย ค่าของ n2 − n ขึ้นมาถึง 506 เมื่อ n = 23 ดังนั้น 23 คนก็เพียงพอที่จะเป็นคำตอบ

อย่างไรก็ดี การแก้สมการ n2 − n = 2 · 365 ln 2 เพื่อหาค่า n ก็จะเป็นสูตรประมาณของแฟรงก์ เอช. แมทิส ดังที่ได้แสดงไว้แล้ว

การได้มานี้แสดงเพียงว่า 23 คนเป็นจำนวนคนที่ มากสุด ที่จำเป็นเพื่อให้แน่ใจว่าวันเกิดจะตรงกันด้วยโอกาสครึ่งต่อครึ่ง กล่าวคือมันเปิดโอกาสความเป็นไปได้ว่าหาก n เท่ากับ 22 คนหรือน้อยกว่าก็อาจได้ผลเช่นกัน