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

מתוך ויקיפדיה, האנציקלופדיה החופשית

יש לך הודעות חדשות (השווה לגרסה הקודמת).

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

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

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

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

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

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

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

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

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

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

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

אם כך, ההסתברות לכך ש- m הכדורים הראשונים יפלו לתאים שונים, ללא התנגשות, שווה למכפלה $\ p_m=1\cdot \left(1-\frac{1}{n}\right)\cdot \left(1-\frac{2}{n}\right)\cdot \dots \cdot \left(1-\frac{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}{n}}$ . הסיכוי לאי-חזרה יורד לחצי, אם-כן, כאשר $\ m \approx \sqrt{\log(2)\cdot n}$ . ככל שהיחס $\ 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}}$ .