פרדוקס האוטובוס הצפוף

אהוד אהרוני (שבנוסף למעלליו בפוסט הזה גם יוצר סרטוני וידאו די פנטסטיים למראה) פנה אלי עם סיפור שאותו המציא: ישנה עיירה ובה מפעל, ובכל יום הפועלים נוסעים למפעל באוטובוס. יש 30 פועלים ועומדים לרשותם 3 אוטובוסים שממתינים בחניה, וכל פועל בוחר באקראי לאיזה אוטובוס לעלות (כלומר, לכל אוטובוס יש את אותה הסתברות להיבחר על ידי כל פועל). עבור מתבונן מבחוץ שעוקב אחרי מה שקורה יום אחרי יום, נראה שבתוחלת (כלומר, בממוצע לאורך זמן) כל אוטובוס מכיל 10 אנשים. לעומת זאת, הפועל בוב טוען שחד משמעית, תוחלת מספר האנשים על האוטובוס שלו היא גדולה יותר מ-10, כלומר האוטובוס של בוב יותר צפוף ממה שהיה צפוי. ואז באה הפועלת אליס ואומרת שגם אצלה זה ככה!

איך זה ייתכן?

ובכן, אני במבט ראשון לא האמנתי שזה ייתכן ושיערתי שיש כאן בעיה כלשהי בניסוח הסיפור. אז מה עושים במקרים כאלו? כשזה מגיע לשאלות הסתברותיות פשוטות, מתמטיקה יכולה להיות מדע אמפירי לגמרי – אפשר לערוך ניסויים ולראות מה התוצאות שלהן. את הניסויים שלנו אנחנו עורכים בדרך כלל בסימולציית מחשב, אז כתבתי חיש קל סימולציה שכזו שבה פועלים באמת עולים לאוטובוס ואני מודד מה קורה. מדדתי שלושה דברים – את כמות הפעמים שבהן האוטובוס של בוב היה הצפוף ביותר (דהיינו, היו בו ממש יותר אנשים מאשר באוטובוסים האחרים; אם מספר האנשים באוטובוס של בוב היה שווה למספרם באוטובוס אחר, זה לא נחשב), את מספר האנשים הכולל באוטובוס הראשון לאורך כל הימים, ואת מספר האנשים הכולל באוטובוס שבוב היה בו לאורך כל הימים, ואת שלושת המספרים הללו חילקתי במספר הימים של הסימולציה – 100,000. התוצאה: ההסתברות לכך שהאוטובוס של בוב יהיה הצפוף ביותר היא $latex 0.3812$; תוחלת מספר האנשים באוטובוס הראשון הייתה $latex 10.0076$, ואילו תוחלת מספר האנשים באוטובוס של בוב הייתה $latex 10.65412$. במילים אחרות, יש לנו סוג של חוק מרפי הסתברותי: "האוטובוס שאליו אתה עולה יהיה תמיד האוטובוס הצפוף ביותר" (רק לא תמיד אלא בהסתברות כלשהי שגדולה מההסתברות של התפלגות אקראית אחידה).

אוקיי, זה מפתיע.

במבט ראשון היינו מצפים שהמספר הראשון יהיה $latex 0.333\dots$ – הרי בוב עולה באקראי לאחד מבין שלושת האוטובוסים, אז יש לו הסתברות של שליש לעלות לאוטובוס הצפוף ביותר. אבל כמובן, האינטואיציה הזו שגויה, כי לפעמים בוב משפיע על השאלה מהו האוטובוס הצפוף ביותר. זה קורה כאשר יש שני אוטובוסים שמספר האנשים שאינם בוב שעלו אליהם הוא זהה ולאוטובוס השלישי עלו פחות אנשים מאשר לכל אחד משניהם; במקרה הזה, לא משנה איזה משני האוטובוסים בוב יבחר, ההסתברות שלו לבחור את "האוטובוס הצפוף ביותר" תהיה $latex \frac{2}{3}$. בשאר המקרים ההסתברות שלו תהיה תמיד $latex \frac{1}{3}$, כי אם יש רק אוטובוס יחיד עם מספר אנשים גדול ביותר, רק אם בוב יבחר אותו הוא יגיע לאוטובוס הצפוף ביותר.

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

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

בואו נחשוב על מקרה פשוט שבו יש רק שתי תוצאות אפשריות – "הצלחה" או "כשלון". למשל, אנחנו מנסים לקלוע לסל. יש לנו 30 זריקות וההסתברות שלנו לקלוע היא $latex \frac{1}{3}$. עכשיו אפשר לשאול שאלות כמו "מה ההסתברות שנקלע לסל בדיוק 12 פעמים"?

את הסיטואציה הזו מתאר מה שנקרא משתנה מקרי בינומי. נהוג לסמן זאת $latex X\sim\mbox{Bin}\left(n,p\right)$ כאשר $latex n,p$ הם הפרמטרים שמאפיינים את המשתנה הבינומי הספציפי הזה: $latex n$ הוא מספר הניסויים הכולל שמתקיים (זריקות לסל) ו-$latex p$ היא ההסתברות שניסוי "יצליח" (קלענו לסל).

עכשיו, נניח שאנחנו לא שואלים "מה ההסתברות שנקלע לסל בדיוק 12 פעמים" אלא שאלה קצת יותר פשוטה: "מה ההסתברות שנקלע לסל בדיוק ב-12 הזריקות הראשונות ואת היתר נחטיא?". התשובה לזה פשוטה ונובעת מעקרון הכפל בהסתברות, שאומר שאם יש לנו סדרה של ניסויים בלתי תלויים ותוצאות ספציפיות לכל אחד מהניסויים הללו, ההסתברות לקבלת סדרת התוצאות הזו היא בדיוק המכפלה של ההסתברות לכל את התוצאה בכל שלב. במקרה שלנו ההסתברות של קליעה היא $latex \frac{1}{3}$ וההסתברות של החטאה היא $latex \frac{2}{3}$ ולכן ההסתברות הכוללת היא $latex \frac{1}{3}\cdots\frac{1}{3}\cdot\frac{2}{3}\cdots\frac{2}{3}=\left(\frac{1}{3}\right)^{12}\left(\frac{2}{3}\right)^{18}$ .

עכשיו, שימו לב שלא הייתה חשיבות לסדר כאן – כלומר, ההסתברות שקיבלנו לא התעניינה בשאלה אם אנחנו קולעים את 12 הסלים בהתחלה או לא. אפשר באותה מידה היה להסתכל על סדרת קליעות אחרת שכוללת בדיוק 12 קליעות מוצלחות, והיינו מקבלים שההסתברות של אותה סדרת קליעות היא עדיין $latex \left(\frac{1}{3}\right)^{12}\left(\frac{2}{3}\right)^{18}$. לכן אפשר להסיק מכך שההסתברות לקלוע 12 סלים לסל בסדר כלשהו שווה ל-$latex \left(\frac{1}{3}\right)^{12}\left(\frac{2}{3}\right)^{18}$ כפול מספר הסדרות מאורך 30 של אפסים ואחדים שיש בהן בדיוק 12 פעמים 1 ויתר הפעמים 0 (1 מייצג קליעה מוצלחת). מציאת מספר הסדרות הללו היא בעיה קומבינטורית קלה: כבר ראינו בבלוג שהתשובה היא $latex \frac{30!}{12!18!}$, ולצורך פשטות מסמנים את המספר הזה בסימון $latex {30 \choose 12}$ (שנקרא "מקדם הבינום" מסיבות שהסברתי פעם בבלוג, ולכן קוראים להתפלגות הזו "בינומית"). לכן ההסתברות לקלוע בדיוק 12 פעמים לסל היא $latex {30 \choose 12}\left(\frac{1}{3}\right)^{12}\left(\frac{2}{3}\right)^{18}$.

מכאן אני מקווה שההכללה ברורה: אם יש לנו משתנה מקרי שמתפלג בינומית עם פרמטרים $latex n,p$, $latex X\sim\mbox{Bin}\left(n,p\right)$, אז $latex \mbox{Pr}\left[X=k\right]={n \choose k}p^{k}\left(1-p\right)^{n-k}$. נסו להוכיח לעצמכם את הנוסחה הזו אם אתם לא בטוחים שהיא נכונה!

הבנו איך מחשבים את ההסתברות לערך קונקרטי של משתנה בינומי, עכשיו בואו נדבר על התוחלת שלו. התוחלת היא במובן מסויים הערך ה"ממוצע" של המשתנה: פורמלית, היא מוגדרת בתור $latex \mbox{E}\left[X\right]=\sum k\cdot\mbox{Pr}\left[X=k\right]$ כאשר המשתנה $latex k$ רץ על כל הערכים ש-$latex X$ יכול לקבל (כאן אני מניח שיש מספר סופי שלהם ולכן לא צריך להטריד את עצמי עם שאלות כמו מה זה סכום של מספר לא סופי של מחוברים). את התוחלת של משתנה בינומי גם כן חישבתי כבר בעבר ולא אחזור על זה כרגע: היא יוצאת ממש פשוטה – $latex np$. דהיינו, קחו את מספר הניסויים שמבצעים וכפלו אותו בהסתברות שניסוי יצליח.

זה מספיק כדי למצוא שניים משלושת המספרים שהסימולציה שלי החזירה. ראשית, כמה אנשים יהיו בממוצע על אוטובוס מס' 1? ובכן, $latex X$ שלנו יספור כמה אנשים עלו לאוטובוס הזה. $latex n=30$ במקרה שלנו כי יש 30 אנשים שעולים לאוטובוסים, וכל אחד עולה באופן בלתי תלוי בשני כך שזה אכן מתאים לסיטואציה של משתנה בינומי. ההסתברות שמישהו יעלה לאוטובוס מס' 1 דווקא היא $latex p=\frac{1}{3}$. לכן התוחלת יוצאת 10 – אכן, קרוב מאוד למספר שקיבלנו בפועל.

עכשיו לשאלה השניה – מה תוחלת מספר האנשים ב"אוטובוס של בוב"? כאן החישוב צריך להיות קצת שונה. באוטובוס של בוב תמיד יש לפחות את בוב, והשאלה היא מה קורה עם שאר 29 האנשים. כל אחד מהם עולה לאוטובוס של בוב בהסתברות $latex \frac{1}{3}$ כמו קודם, כך שהפעם יש לנו 29 ניסויים, ולכן אנחנו מקבלים שלאוטובוס של בוב עולים בתוחלת $latex \frac{29}{3}$ אנשים מלבדו. אם רוצים להיות פורמליים, צריך להגדיר משתנה מקרי $latex Y=1+X$ כאשר $latex X\sim\mbox{Bin}\left(29,\frac{1}{3}\right)$ – המשתנה המקרי $latex Y$ הזה מתאר את מספר האנשים באוטובוס של בוב. התוחלת שלו שווה ל-

$latex \mbox{E}\left[1+X\right]=1+\mbox{E}\left[X\right]=1+\frac{29}{3}=\frac{32}{3}=10.666\dots$

כאשר כאן השתמשתי בלי הוכחה בכמה עובדות בסיסיות על תוחלת (מה שנקרא לינאריות התוחלת). אכן, גם כאן אנחנו רואים שתוצאת הניסוי בפועל הייתה קרובה למספר הצפוי. ושהמספר הצפוי גדול מ-10. חישוב דומה יעבוד, כמובן, גם במקרה הכללי: אם יש לנו $latex N$ פועלים ו-$latex k$ אוטובוסים אז תוחלת מספר הפועלים באוטובוס מס' 1 היא $latex \frac{N}{k}$ אבל תוחלת מספר הפועלים באוטובוס של בוב היא $latex \frac{N+k-1}{k}$.

נותר עדיין להסביר מתמטית את המספר השלישי מבין התוצאות האמפיריות שלי – ההסתברות של 0.38 בערך לכך שבוב יהיה באוטובוס העמוס ביותר. לרוע המזל, אני לא מכיר דרך פשוטה לחשב את ההסתברות הזו שנותנת נוסחה קצרה ויפה (אולי מישהו כן מכיר?), אבל זה כן נותן לי תירוץ להציג את ההכללה של ההתפלגות הבינומית – התפלגות מולטינומית.

הרעיון הוא זה: נניח שלניסוי שלנו יש יותר תוצאות מאשר רק "הצלחה/כשלון", ואנחנו רוצים למצוא את ההסתברות עבור כך-וכך תוצאות מכל סוג – שוב, בלי חשיבות לסדר. למשל, נניח שאני זורק כדור לסל ורוצה לספור כמה פעמים קלעתי (בהסתברות $latex \frac{1}{3}$), כמה פעמים הכדור הגיע אל הסל אבל לא נכנס (הסתברות $latex \frac{1}{6}$) וכמה פעמים כל הסיפור הסתיים בצורה מבישה כשהכדור בכלל לא הגיע אל הסל (הסתברות $latex \frac{1}{2}$). לא אלאה אתכם בפרטים אלא אקפוץ להדגמה של מספר סופי: אם אני רוצה לדעת את ההסתברות ל-8 קליעות, 3 החטאות-עם-הגעה-לסל ו-19 החטאות מבישות (שימו לב שהכל מסתכם ל-30), ההסתברות תהיה $latex \frac{30!}{8!3!19!}\left(\frac{1}{3}\right)^{8}\left(\frac{1}{6}\right)^{3}\left(\frac{1}{2}\right)^{19}$. זה נראה כמו הכללה טבעית של הנוסחה שנתתי קודם, רק שהפעם יש לנו שלושה איברים במקום שניים.

כך גם באופן כללי: נניח שיש לנו $latex t$ תוצאות אפשריות עם הסתברויות $latex p_{1},\dots,p_{t}$ (שמסתכמות ל-1) ואנחנו רוצים לדעת מה ההסתברות לקבל בדיוק $latex k_{1}$ תוצאות מסוג מס' 1, $latex k_{2}$ תוצאות מסוג מס' 2 וכן הלאה עד $latex k_{t}$ תוצאות מסוג מס' $latex t$. נסמן $latex n=\sum_{i=1}^{n}k_{i}$ ואז ההסתברות נתונה על ידי הנוסחה $latex \frac{n!}{k_{1}!\cdots k_{t}!}p_{1}^{k_{1}}\cdots p_{t}^{k_{t}}$. בכתיב מקוצר זה יוצא $latex {n \choose k_{1}\dots k_{t}}\prod p_{i}^{_{k}}$.

איך זה קשור לבוב והאוטובוסים? חשבו על מה שאמרתי קודם – ההסתברות שבוב יעלה לאוטובוס העמוס ביותר היא $latex \frac{2}{3}$ אם יש שני אוטובוסים בעלי אותו מספר אנשים (חוץ מבוב) והשלישי מכיל פחות אנשים, והיא $latex \frac{1}{3}$ בסיטואציות אחרות. לכן, אם $latex q$ היא ההסתברות לסיטואציה הראשונה, אז ההסתברות הכוללת שבוב יעלה לאוטובוס העמוס ביותר היא $latex \frac{2}{3}q+\frac{1}{3}\left(1-q\right)$. רק צריך לחשב את $latex q$. וכדי לחשב את $latex q$ אני משתמש בהתפלגות מולטינומית.

השאלה שאני שואל עכשיו היא זו: איך צריכים 29 אנשים להתחלק לאוטובוסים כך ששני האוטובוסים הראשונים יכילו את אותו מספר אנשים והשלישי יכיל פחות? ובכן, למשל, הם יכולים להתחלק 14 לאוטובוס הראשון, 14 לשני ו-1 לשלישי. נסמן את זה $latex \left(14,14,1\right)$. באופן דומה גם $latex \left(13,13,3\right),\left(12,12,5\right),\left(11,11,7\right),\left(10,10,9\right)$ הן אפשרויות חוקיות, אבל $latex \left(9,9,11\right)$ כבר לא (כי עכשיו האוטובוס השלישי מכיל את מספר האנשים הגבוה ביותר). עכשיו משתמשים בהתפלגות מולטינומית כדי לדעת מה ההסתברות של כל סיטואציה כזו, ומקבלים את הזוועה הבאה:

$latex \left(\frac{30!}{14!14!1!}\frac{30!}{13!13!3!}+\frac{30!}{12!12!5!}+\frac{30!}{11!11!7!}+\frac{30!}{10!10!9!}\right)\left(\frac{1}{3}\right)^{30}$

(ה-$latex \left(\frac{1}{3}\right)^{30}$ נובע מכך שההסתברות של כל אחד מהאוטובוסים להיבחר היא $latex \frac{1}{3}$, כלומר כל ה-$latex p_{i}$-ים שווים במקרה הזה).

שימו לב שההסתברות הזו עדיין אינה $latex q$ המדובר; זו ההסתברות שבאוטובוסים 1 ו-2 יהיה מספר אנשים שווה ובאוטובוס מס' 3 יהיה את מספר האנשים הקטן ביותר. באותו האופן יכלנו לבחור שדווקא באוטובוס 2 יהיה מספר האנשים הקטן ביותר, או באוטובוס 1. דהיינו, צריך להכפיל את המספר ההוא ב-3 כדי לקבל את $latex q$.

החישוב הזה אולי נראה מזעזע, אבל במחשב הוא כמובן טריוויאלי לחלוטין – אפילו לא צריך להקליד את כל המספרים אם משתמשים בשפת סקריפטינג נוחה עבור החישובים. התוצאה המספרית הסופית? אני קיבלתי $latex 0.38159\dots$, קרוב מאוד לתוצאות האמפיריות. הבעיה היחידה היא שלהכליל את החישוב הזה עבור מספר גדול יותר של אוטובוסים יהיה כאב ראש (עבור מספר גדול יותר של אנשים רק צריך לשנות מספר אחד בשורת הקוד שמבצעת את החישוב) – אולי לכם יהיה פתרון טוב יותר שמוצא את ההסתברות עבור $latex N,k$ כלליים?

15 תגובות על הפוסט “פרדוקס האוטובוס הצפוף

  1. יפה. במבט חטוף נראה לי שזה גם פיתרון תאורטי לפקדוקס הידידות (בתנאים מסויימים, למשל שהוספת עוקב מתפלגת אחיד): http://en.wikipedia.org/wiki/Friendship_paradox
    אם כי שם הניסיון האמפירי מראה פער גדול יותר בין ה"צפוי" למצוי והפער באמת מוסבר על ידי הטיית המיקרו-סלב (=סביר שאני אחשף ואעקוב אחרי אנשים עם יותר עוקבים), כלומר שההנחה לעיל לא נכונה.

    [הי אודי – ד"ש לכולם]

  2. דרך מחשבה נוספת: כשאוטובוס צפוף, הרבה אנשים חווים אותו צפוף, כשהאוטובוס מרווח, מעט אנשים חווים אותו מרווח. כלומר, אם כל בן אדם מקבל כערך את כמות האנשים שאיתו על האוטובוס (כולל הוא עצמו) וסוכמים הכל יחד, המינימום הוא רק כשהם מחולקים ל10 10 ו10. האין זה מראה שהתופעה הזאת קורית? (הערך שהבן אדם חווה הוא הצפיפות…)

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

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

  4. האינטואיציה לפרדוקס מבחינתי זה שיש חוסר סימטריה ממש בין להיות על האוטובוס הכי עמוס ממש לבין להיות לדוגמה על האוטובוס הכי פחות עמוס ממש. כדי להיות על האוטובוס הכי פחות עמוס ממש חייבים שיהיו מתחת ל10 נוסעים (כלומר כל מספר בין 0 ל9) אבל על העמוס ביותר כל מספר בין 11 ל30 יכול להתאים.

  5. האם בביטוי הזוועתי לא אמור להופיע 29! בכל מקום שבו מופיע 30!, והחזקה של ה-1/3 אמורה אף היא להיות 29?
    הרי מדובר ב-29 אנשים בהקשר זה, לא ב-30

  6. נראה לי שכן ושזו טעות של חוסר תשומת לב שלי. יתוקן (אחרי שאחשוב על זה)

  7. האם אפשר לומר שהסטיה מהממוצע נובעת מאימוץ נקודת המבט של *מישהו*? כלומר, "במבט על" אובייקטיבי ברור שהיינו רואים 0.33.

  8. תוצאה יפה. הראת פה שחוקי מרפי (טוב, לפחות גירסה מרוככת קצת שלהם) הם אשכרה חוקים מתמטיים! מגניב :)

  9. הסבר אפשרי זה שה"רצון החופשי" של לבחור אוטובוס מסויים , לעומת הגרלה רנדומלית של האוטובוס משנה את התוצאה.

  10. לא התייחסת למקרה בו יש שני אוטובוסים "עמוסים ביותר", לדוגמא חלוקה של 14,14,2.
    ליתר דיוק: בהתחלה אמרת שאז אין אוטובוס "עמוס ביותר", ואח"כ בחישובים המתימטיים התעלמת מהאפשרות הזאת.

  11. לא הבנתי –
    נניח שחוץ מבוב נוסע גם bob' (בוב פריים).
    הוא גם ירגיש שהוא (בתוחלת) באוטובוס הכי צפוף, לא?
    זה יהיה נכון לכל אחד מN הפועלים –
    בסתירה לכך שזה נכון…
    כי על כל פעם שבוב ובוב' נוסעים באוטובוס הכי צפוף, יש כ 2N/3 אנשים שנוסעים באוטובוס לא הכי צפוף.

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

  12. הנקודה היא שאין סימטריה. אם כבר יצא שיש אוטובוס "הכי צפוף", יהיו בו יותר מאשר שליש מהפועלים – בדיוק בגלל שהוא הכי צפוף. ככל שאוטובוס יותר צפוף, כך יש עליו יותר אנשים שמרגישים את הצפיפות הזו.

  13. לא התיחסת למקרה שבו יש שני אוטובוסים עם מספר קטן של נוסעים לעומת אוטובוס אחד עם מספר רב של נוסעים. במקרה כזה ההסתברות לבחור את האוטובוס הצפוף יורדת ל 1/3 בלבד

כתיבת תגובה

האימייל לא יוצג באתר.