פרדוקס יום ההולדת

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
גרף ההסתברות למציאת זוג אנשים שנולדו באותו יום כפונקציה של מספר האנשים הנבדקים

פרדוקס יום ההולדת הוא שמה של תוצאה בתורת ההסתברות לפיה בקבוצה של 23 אנשים או יותר, שנבחרו באקראי, הסיכוי לכך שלפחות שניים מהם נולדו באותו יום בשנה עולה על 50%. תוצאה זו אינה פרדוקס במובן המקובל של המילה, שכן אין בה סתירה לוגית, אך היא סותרת את האינטואיציה של מרבית האנשים, הסבורים כי ההסתברות תהיה קטנה בהרבה מחצי משום שמספר הימים שבהם אפשר להיוולד (365) גדול בהרבה מ-23.

תוצאה זו היא מקרה פרטי של עובדה כללית יותר, שיש לה חשיבות רבה ביישומים של תורת ההסתברות, ובפרט בהתקפת יום הולדת בקריפטוגרפיה: אם בוחרים ערכים בעלי סיכוי שווה מבין \ n אפשרויות, אז החזרות הראשונות תופענה כבר כאשר מספר הערכים הוא מסדר גודל של \ \sqrt{n}.

תיאור התופעה[עריכת קוד מקור | עריכה]

פרדוקס יום ההולדת עוסק בסדרה של מספרים המוגרלים בצורה אקראית מתוך טווח מסוים – במקרה של ימי הולדת, הטווח הוא המספרים השלמים מ-1 ועד 365. לשם הפשטות, אפשר להתעלם מקיומן של שנים מעוברות (כלומר, שיום הולדתו של אדם עשוי לחול ב-29 בפברואר). בניתוח התופעה נניח גם שההסתברות להיוולד שווה בכל הימים בשנה,‏[1] אך אי הדיוק רק מגדיל את הסיכוי ששני אנשים יוולדו באותו יום. לבסוף, מניחים שתאריכי הלידה של האנשים שנבחרו בלתי תלויים זה בזה – הפרדוקס מאבד את עוקצו אם בין הנבחרים זוג תאומים.

כדי להבטיח שני אנשים שנולדו באותו יום, יש לבחור לפחות 366 אנשים – זהו עקרון שובך היונים. אולם, הדרישה הסטטיסטית להימנע מימי הולדת משותפים הולכת ומכבידה. בבחירה של 23 הסיכוי שכל ימי ההולדת שונים יורד ל-49.2%, בבחירה של 41 אנשים הסיכוי שכל ימי ההולדת שונים הוא 9.6%, וסיכוי זה יורד אל מתחת לאחוז אחד כאשר בוחרים 57 אנשים.

ניתוח מפורט[עריכת קוד מקור | עריכה]

את תופעת יום ההולדת, או החַזרה בבחירה מתוך מרחב גדול בעל התפלגות אחידה, אפשר לנתח משלוש זוויות שונות, המביאות, בקירוב, לאותה מסקנה. נניח שזורקים \ m כדורים באקראי ל-\ n תאים, שההסתברות ליפול לכל אחד מהם שווה.

מספר ההתנגשויות[עריכת קוד מקור | עריכה]

אפשר להתייחס לכל זוג כדורים כאל ניסוי עצמאי. הסיכוי שזוג הכדורים \ i, j יפלו לאותו תא הוא בדיוק \ \tfrac{1}{n}, ולכן, כשעוברים על פני כל \ \tfrac{m(m-1)}{2} הזוגות, התוחלת של מספר הזוגות שיפלו לאותו תא שווה ל- \ \tfrac{m(m-1)}{2n}. כל עוד מספר הכדורים \ m הוא קטן, התוחלת קטנה מ-1 ולכן אפשר להניח שלא תהיה אף התנגשות אחת. התוחלת של מספר ההתנגשויות עולה ל-1 כאשר \ m\approx \sqrt{2n}.

ההסתברות לאי-חזרה[עריכת קוד מקור | עריכה]

את התנאי לחוסר חזרה אפשר להבין כך: הכדור הראשון אינו מוגבל. הכדור השני יכול ליפול לאחד מבין \ n-1 תאים, כדי לא לפגוע בראשון; הסיכוי לכך בזריקה אקראית הוא \ \tfrac{n-1}{n}. הכדור השלישי צריך ליפול לאחד מבין \ n-2 התאים שנותרו לאחר פסילת שני התאים הראשונים, והסיכוי לכך הוא \ \tfrac{n-2}{n}; וכן הלאה. לאחר שנזרקו \ k כדורים שנכנסו כולם לתאים שונים, הסיכוי לכך שגם הכדור הבא יפול לתא משלו הוא \ \tfrac{n-k}{n}.

אם כך, ההסתברות לכך ש- \ m הכדורים הראשונים יפלו לתאים שונים, ללא התנגשות, שווה למכפלה \ p_m=1\cdot \left(1-\tfrac{1}{n}\right)\cdot \left(1-\tfrac{2}{n}\right)\cdot \dots \cdot \left(1-\tfrac{m-1}{n}\right). כדי להעריך מספר זה, אפשר להיעזר בחסם \ e^{-x}> 1-x (הנובע מפיתוח פונקציית האקספוננט לטור טיילור, ותקף לכל \ x>0). לפי חסם זה, \ 
p_m < e^{-\frac{1}{n}}\cdot 
e^{-\frac{2}{n}}\cdot \dots \cdot 
e^{-\frac{m-1}{n}} = e^{-(\frac{1}{n}+\frac{2}{n}+\dots+\frac{m-1}{n})} = e^{-\frac{m(m-1)}{2n}}, ובקירוב, \ e^{-\frac{m^2}{2n}}. הסיכוי לאי-חזרה יורד לחצי, אם-כן, כאשר \ m \approx \sqrt{2\log(2)\cdot n}. ככל שהיחס \ \tfrac{m^2}{n} גדול יותר כך הסיכוי לאי-חזרה קטן יותר, ובסימון אסימפטוטי: עבור \ m=o(\sqrt{n}) ההסתברות לאי חזרה היא \ o(1). מצד שני, לא קשה להראות שאם \ m=\omega(\sqrt{n}) אז ההסתברות היא \ 1-o(\sqrt{n}).

זמן ההמתנה להתנגשות הראשונה[עריכת קוד מקור | עריכה]

נסמן ב- \ T את המשתנה המקרי הסופר כמה כדורים נזרקו, באקראי, עד להתנגשות הראשונה. זהו משתנה העשוי לקבל כל ערך שלם מ- \ 1 ועד \ n+1. ידוע שהתוחלת של משתנה כזה שווה לסכום ההסתברויות \ E(T) = \sum_{m=1}^{\infty}P(T\geq m) = \sum_{m=1}^{\infty}p_{m-1} \approx 
\sum_{m=0}^{n}e^{-\frac{m(m-1)}{2n}}, שאותו אפשר להעריך בעזרת אינטגרל מתאים. התוצאה מחישוב מדויק היא שכאשר \ n גדול, תוחלת זמן ההמתנה עד להתנגשות הראשונה היא \ E(T)\approx \sqrt{\frac{\pi n}{2}}.

קישורים חיצוניים[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ למעשה, הסתברות להיוולד אינה שווה בכל הימים בשנה. סיבה אחת למשל, היא שקיימות תקופות, כמו חופשות וחגים, בהן קיים פנאי רב יותר, וסיכוי גדול יותר להרות. בהתאם קיימות תקופות בהן הסיכוי להיוולד גדול יותר.