פרדוקס יום ההולדת
פרדוקס יום ההולדת הוא שמה של תוצאה בתורת ההסתברות לפיה בקבוצה של 23 אנשים או יותר, שנבחרו באקראי, הסיכוי לכך שלפחות שניים מהם נולדו באותו יום בשנה עולה על 50%. תוצאה זו אינה פרדוקס במובן המקובל של המילה, שכן אין בה סתירה לוגית, אך היא סותרת את האינטואיציה של מרבית האנשים, הסבורים כי ההסתברות תהיה קטנה בהרבה מחצי משום שמספר הימים שבהם אפשר להיוולד (365) גדול בהרבה מ-23.
תוצאה זו היא מקרה פרטי של עובדה כללית יותר, שיש לה חשיבות רבה ביישומים של תורת ההסתברות, ובפרט בהתקפת יום הולדת בקריפטוגרפיה: אם בוחרים ערכים בעלי סיכוי שווה מבין הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n} אפשרויות, אז החזרות הראשונות תופענה כבר כאשר מספר הערכים הוא מסדר גודל של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \sqrt{n}} .
פרדוקס יום ההולדת תואר לראשונה במאמר על ידי הסטטיסטיקאי ריצ'רד פון מיזס ב-1939, אם כי סביר להניח שגרסאות קודמות של הבעיה היו ידועות ונחקרו על ידי מתמטיקאים אחרים. הפרדוקס היה נושא למחקר ודיונים רבים בתחומי ההסתברות והסטטיסטיקה, ויש לו יישומים רבים במדעי המחשב, בקריפטוגרפיה ובתחומים נוספים.
תיאור התופעה
פרדוקס יום ההולדת עוסק בסדרה של מספרים המוגרלים בצורה אקראית מתוך טווח מסוים – במקרה של ימי הולדת, הטווח הוא המספרים השלמים מ-1 ועד 365. לשם הפשטות, אפשר להתעלם מקיומן של שנים מעוברות (כלומר, שיום הולדתו של אדם עשוי לחול ב-29 בפברואר). בניתוח התופעה נניח גם שההסתברות להיוולד שווה בכל הימים בשנה,[א] אך אי הדיוק רק מגדיל את הסיכוי ששני אנשים ייוולדו באותו יום. לבסוף, מניחים שתאריכי הלידה של האנשים שנבחרו בלתי תלויים זה בזה – הפרדוקס מאבד את עוקצו אם בין הנבחרים זוג תאומים.
כדי להבטיח שני אנשים שנולדו באותו יום, יש לבחור לפחות 367 אנשים – זהו עקרון שובך היונים. אולם, הדרישה הסטטיסטית להימנע מימי הולדת משותפים הולכת ומכבידה. בבחירה של 23 הסיכוי שכל ימי ההולדת שונים יורד ל-49.3%, בבחירה של 41 אנשים הסיכוי שכל ימי ההולדת שונים הוא 9.7%, וסיכוי זה יורד אל מתחת לאחוז אחד כאשר בוחרים 57 אנשים.
ניתוח מפורט
את תופעת יום ההולדת, או החֲזרה בבחירה מתוך מרחב גדול בעל התפלגות אחידה, אפשר לנתח משלוש זוויות שונות, המביאות, בקירוב, לאותה מסקנה. נניח שזורקים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ m} כדורים באקראי ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n} תאים, שההסתברות ליפול לכל אחד מהם שווה.
מספר ההתנגשויות
אפשר להתייחס לכל זוג כדורים כאל ניסוי עצמאי. הסיכוי שזוג הכדורים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ i, j} ייפלו לאותו תא הוא בדיוק הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \tfrac{1}{n}} , ולכן, כשעוברים על פני כל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \tfrac{m(m-1)}{2}} הזוגות, התוחלת של מספר הזוגות שיפלו לאותו תא שווה ל- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \tfrac{m(m-1)}{2n}} . כל עוד מספר הכדורים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ m} הוא קטן, התוחלת קטנה מ-1 ולכן אפשר להניח שלא תהיה אף התנגשות אחת. התוחלת של מספר ההתנגשויות עולה ל-1 כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ m\approx \sqrt{2n}} .
ההסתברות לאי-חזרה
את התנאי לחוסר חזרה אפשר להבין כך: הכדור הראשון אינו מוגבל. הכדור השני יכול ליפול לאחד מבין הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n-1} תאים, כדי לא לפגוע בראשון; הסיכוי לכך בזריקה אקראית הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \tfrac{n-1}{n}} . הכדור השלישי צריך ליפול לאחד מבין הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n-2} התאים שנותרו לאחר פסילת שני התאים הראשונים, והסיכוי לכך הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \tfrac{n-2}{n}} ; וכן הלאה. לאחר שנזרקו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ k} כדורים שנכנסו כולם לתאים שונים, הסיכוי לכך שגם הכדור הבא ייפול לתא משלו הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \tfrac{n-k}{n}} .
אם כך, ההסתברות לכך ש- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ m} הכדורים הראשונים יפלו לתאים שונים, ללא התנגשות, שווה למכפלה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 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)} . כדי להעריך מספר זה, אפשר להיעזר בחסם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ e^{-x}> 1-x} (הנובע מפיתוח פונקציית האקספוננט לטור טיילור, ותקף לכל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x>0} ). לפי חסם זה, הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 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}}} , ובקירוב, הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ e^{-\frac{m^2}{2n}}} . הסיכוי לאי-חזרה יורד לחצי, אם-כן, כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ m \approx \sqrt{2\ln(2)\cdot n}} . ככל שהיחס הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \tfrac{m^2}{n}} גדול יותר כך הסיכוי לאי-חזרה קטן יותר, ובסימון אסימפטוטי: עבור הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ m=o(\sqrt{n})} ההסתברות לאי חזרה היא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ o(1)} . מצד שני, לא קשה להראות שאם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ m=\omega(\sqrt{n})} אז ההסתברות היא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 1-o(1)} .
זמן ההמתנה להתנגשות הראשונה
נסמן ב- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ T} את המשתנה המקרי הסופר כמה כדורים נזרקו, באקראי, עד להתנגשות הראשונה. זהו משתנה העשוי לקבל כל ערך שלם מ- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 1} ועד הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n+1} . ידוע שהתוחלת של משתנה כזה שווה לסכום ההסתברויות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 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}}} , שאותו אפשר להעריך בעזרת אינטגרל מתאים. התוצאה מחישוב מדויק היא שכאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n} גדול, תוחלת זמן ההמתנה עד להתנגשות הראשונה היא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ E(T)\approx \sqrt{\frac{\pi n}{2}}} .
קישורים חיצוניים
- גדי אלכסנדרוביץ', כיצד פרדוקס יום ההולדת מוליד חוב בבנק, באתר "לא מדויק", 26 ביולי 2008
- סיינטיפיק אמריקן ישראל, לעולם אל תאמרו לעולם לא / דייוויד ג'י האנד, באתר "הידען", 29 ביוני 2014
- פרדוקס יום ההולדת, באתר MathWorld (באנגלית)
בדקו את האינטואיציה שלכם: בעיית יום ההולדת - דייויד קנופקה, סרטון באתר יוטיוב
ביאורים
- ^ למעשה, ההסתברות להיוולד אינה שווה בכל הימים בשנה. סיבה אחת למשל, היא שקיימות תקופות, כמו חופשות וחגים, שבהן קיים פנאי רב יותר, וסיכוי גדול יותר להרות. בהתאם קיימות תקופות שבהן הסיכוי להיוולד גדול יותר.
