פרדוקס המעטפות

ביום רביעי האחרון התמזל מזלי והייתי נוכח בהרצאה של פרופ’ נוגה אלון על “חשיבה הסתברותית”. אלון הוא מרצה בחסד עליון, וייתכן שזו (או אולי הפורום הספציפי שבו ניתנה ההרצאה) הסיבה לכך שהוא לא היסס להציג את הנושאים שעליהם הוא דיבר בצורה קצת יותר מורכבת מההצגה הסטנדרטית שלהם. הוא דיבר על הבעיה של מונטי הול, על אלגוריתמים הסתברותיים ודה-רנדומיזציה שלהם (הפיכתם לדטרמיניסטיים בלי שהדבר ילווה בפגיעה משמעותית בזמן הריצה), עם דגש על אלגוריתם בדיקת הראשוניות AKS (שהזכרתי את הדיווח הנלהב-יתר-על-המידה עליו ב”הארץ” בפוסט קודם, ואני מקווה להציג בצורה יותר קונקרטית בעתיד) שהושג באמצעות דה-רנדומיזציה של אלגוריתם אחר; וכמובן, בשיטה ההסתברותית (שאלון חיבר ספר עליה) שהצגתי את קצה הקרחון שלה בפוסט קודם. עם זאת, החלק שהכי עניין אותי בהרצאה ועליו אני רוצה לדבר בפוסט הזה היה פרדוקס המעטפות.

היחס שלי לפרדוקסים הוא כאל הוכחות בדרך השלילה. הם מגיעים לתוצאה אבסורדית, כן; אבל כל מה שאני מסיק מכך הוא שמשהו שגוי בדרך הסקת המסקנות או בהנחות היסוד שלהם. בפוסטים קודמים הראיתי שהפרדוקסים של זנון לא מרשימים אותי במיוחד כי הם נראים לי כמו המחשה לבלבול שנובע מהגדרות גרועות. גם הפרדוקס של ראסל לא מטריד אותי במיוחד, כי ברור לי שתורת הקבוצות הנאיבית פשוט שגויה באספקט שלה שמאפשר את הפרדוקס. פרדוקסים כמו פרדוקס השקרן או פרדוקס “המספר הטבעי הקטן ביותר שלא ניתן לתאר בפחות ממאה אותיות” לא מרשימים אותי כי ברור לי שהקושי בהם נעוץ בהגדרה שלהם של משהו בעזרת עצמו (כמו להגיד “אני מגדיר את x להיות x+1” ולהתפלא שלא קיבלת שום דבר בעל משמעות). פרדוקס יום ההולדת (שהבטחתי פוסט שעוסק בו, ואקיים) ובעיות כמו מונטי הול (שלעתים מכונה “פרדוקס”) הם בכלל לא פרדוקסים, אלא סך הכל תוצאות לא אינטואיטיביות.

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

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

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

יש שתי אפשרויות: או שבמעטפה השנייה יש סכום כפול, כלומר \( 2A \), ואז הרווחתם \( A \); או שבמעטפה השנייה יש  רק חצי מהסכום שבמעטפה שלכם, ואז הפסדתם \( \frac{1}{2}A \). סביר להניח שההסתברות שבחרתם במעטפה עם הסכום הגדול יותר היא \( \frac{1}{2} \). אם כן, האם כדאי להחליף או לא?

הדרך שבה משתמשים למדוד את כדאיות ההחלפה היא תוחלת הרווח; מעין ממוצע משוקלל של הרווח/הפסד שיכול להיווצר כתוצאה מהפעולה שלכם, כשהשיקלול הוא על פי ההסתברות של המאורע. אפשר לחשוב על תוחלת בתור הרווח הממוצע שיתקבל לאחר הרבה מאוד חזרות על המשחק; כך למשל במונטי הול, תוחלת הרווח במקרה של החלפה (אם אומרים שזכייה ברכב היא רווח 1, והפסד הוא רווח 0) היא \( \frac{2}{3} \).

חישוב התוחלת במקרה שלנו קל מאוד, והנה הוא: \( E=\frac{1}{2}A-\frac{1}{2}\cdot\frac{1}{2}A=\frac{1}{4}A \).

כלומר, תוחלת הרווח במקרה של החלפה היא חיובית. לכן כדאי להחליף.

כעת נכנס לתמונה הטיעון ה”פרדוקסלי”, שהולך כך: הרי החישוב שלעיל נכון עבור כל \( A \) חיובי, לא משנה מה ערכו. אם כן, מדוע צריך בכלל לפתוח את המעטפה? אפילו בלי לפתוח אותה אתה יודע שאתה רוצה להחליף. ואחרי שהחלפת, אותם שיקולים ממשיכים לעבוד, ולכן שוב אתה רוצה להחליף. מכאן שתמיד “משתלם” לך להחליף את המעטפה שלך, שוב ושוב ושוב עד אינסוף. ברור שמשהו שבור כאן.

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

יש עוד נימוקים לבעייתיות אבל לא איכנס אליהם כי זה שהצגתי הוא החביב עלי. השורה התחתונה היא שכדי לפתור את הבעיה המתמטית שיש כאן צריך להגדיר התפלגות כלשהי על הערכים של \( A \) שיכולים להופיע במעטפה; אבל התפלגות כזו בהכרח תספק לי, כשחקן, מידע ותוכל לרמוז לי מה עדיף לעשות. אם אפשר היה לבחור את \( A \) באקראי ובהתפלגות אחידה מבין כל המספרים הטבעיים, זה היה מחזיר אותי לסיטואציה שבה תמיד כדאי להחליף, בלי תלות בערך הספציפי של \( A \); אלא שהתפלגות אחידה שכזו אינה קיימת (תרגיל: הוכיחו). הפרדוקס בגרסה זו מתואר גם ב-Ynet, ובדרך הצגה שהיא אמנם טובה למדי והניתוח שלה לא רע בכלל, אבל השורה התחתונה - הצורך בהגדרת התפלגות על הערכים האפשריים - לא מוזכרת שם, וכמה טוקבקיסטים העירו על כך (עם זאת, את ההצגה גונבות תגובות הטוקבקיסטים שהם פחות מדוייקים מתמטית, למשל “היות ושני המעתפות זהות לחלוטין מבחינה חיצונית, לפי תורת הקוונטים הם בעצם אותו המעתפה.").

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

הרעיון הוא כזה: הערכים שיוכנסו למעטפות יהיו חזקות של 10. כלומר, או 10, או 100, או 1,000 וכן הלאה עד אינסוף. הזוג 10 ו-100 יוכנס בהסתברות 1/2; הזוג 100 ו-1,000 יוכנס בהסתברות 1/4, וכן הלאה. בניסוח פורמלי, ההסתברות של הזוג \( (10^n,10^{n+1}) \) היא \( \frac{1}{2^n} \). קל לראות שמדובר בהתפלגות חוקית (סכום ההסתברויות של כל הזוגות הוא 1). כעת נותר רק לבצע את חישוב התוחלת הישן, שעכשיו הוא מחוכם קצת יותר ואחזור עליו בשלמותו.

נניח שפתחנו את המעטפה וגילינו בפנים סכום של \( 10^n \) עבור איזה שהוא \( n \) טבעי. ברור לנו שאנו נמצאים באחד משני מקרים - או שבמעטפה השנייה יש \( 10^{n+1} \) (סכום גדול פי 10) או שיש בה \( 10^{n-1} \) (סכום קטן פי עשר). היוצא מן הכלל היחיד הוא המקרה שבו מצאנו 10 במעטפה, ואז ברור לנו שכדאי להחליף (זה פועל לטובת הפרדוקס - זכרו, הפואנטה בסוף תהיה שתמיד כדאי להחליף).

נשים לב שהסכום \( 10^n \) (אם הוא לפחות 100) מוגרל בדיוק פעמיים: פעם אחת בהסתברות \( \frac{1}{2^n} \) ואז הוא הסכום הקטן יותר; ופעם אחת בהסתברות \( \frac{1}{2^{n-1}} \) ואז הוא הסכום הגדול יותר. במילים אחרות, ההסתברות שבמעטפה השנייה יש סכום קטן פי 10 מהסכום במעטפה שלנו היא כפולה מההסתברות שבמעטפה השנייה סכום גדול יותר. אם כן, בהסתברות \( \frac{1}{3} \) נרוויח מהחלפת המעטפות, ובהסתברות \( \frac{2}{3} \) נפסיד.

בצורה פורמלית (“בצורה פורמלית” זו דרכי לומר “מי שלא מתעניין בפרטים הטכניים המתמטים, שפשוט יאמין לי ויפסח על הפסקה”) הדרך להגיע למספרים אלו היא באמצעות חישוב הסתברות מותנה; ההסתברות של המאורע “ה-\( 10^n \) שבמעטפה הוא הקטן יותר” היא \( \frac{1}{2^n} \); ההסתברות של המאורע “יש \( 10^n \) באחת המעטפות” היא סכום ההסתברויות של שני המקרים שבהם \( 10^n \) מוכנס למעטפות, דהיינו \( \frac{1}{2^n}+\frac{1}{2^{n-1}}=\frac{3}{2^n} \). כשמחלקים את ההסתברות הראשונה בשנייה, מקבלים \( \frac{1}{2^n}/\frac{3}{2^n}=\frac{1}{3} \), דהיינו ההסתברות המותנה של “ההחלפה משתלמת” היא אכן שליש.

כעת ניתן לחשב את תוחלת הרווח במקרה של החלפה. התוחלת הזו היא פשוט:

\( \frac{1}{3}\cdot 9\cdot 10^n-\frac{2}{3}\cdot 9\cdot 10^{n-1}=30\cdot 10^{n-1}-6\cdot 10^{n-1}=24\cdot 10^{n-1} \)

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

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

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

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

לצורך כך, הבה נחשב בפועל את תוחלת הרווח שלנו. לשם כך עלינו לשאול את עצמנו את השאלה הבאה: נניח שאנחנו לא מחליפים; מה ההסתברות שלנו לקבל את המעטפה שהסכום שבה הוא \( 10^n \)? התשובה לכך היא שקיימות שתי סיטואציות שבהן זה קורה: או שנבחר הזוג \( 10^n, 10^{n+1} \) בהסתברות \( \frac{1}{2^n} \) ולאחר מכן בחרנו את \( 10^n \) מבין שתי המעטפות (בהסתברות \( \frac{1}{2} \); או שנבחר הזוג \( 10^{n-1},10^n \) בהסתברות \( \frac{1}{2^{n-1}} \) ולאחר מכן בחרנו את \( 10^n \) - שוב, בהסתברות \( \frac{1}{2} \). מכאן שההסתברות הכוללת לקבל \( 10^n \) היא \( \frac{1}{2}\left(\frac{1}{2^n}+\frac{1}{2^{n-1}}\right)=\frac{1}{2}\cdot\frac{3}{2^{n}}=\frac{3}{2^{n+1}} \). היוצא מן הכלל הוא 10, שמתקבל בהסתברות 1/4 (למה?)

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

אם כן, אפשר לפנות לחישוב התוחלת של הכסף שמקבלים בסה”כ אם בוחרים באסטרטגיית אי-החלפה. על פי הגדרה, היא שווה לסכום על כל אחת מכמויות הכסף שעשויים לקבל, מוכפלת בהסתברות שכמות הכסף הזו תתקבל. פורמלית זה יוצא \( \frac{10}{4}+3\sum_{n=2}^\infty\frac{10^n}{2^{n+1}}=\frac{10}{4}+\frac{3}{2}\sum_{n=2}^\infty\left(\frac{10}{2}\right)^n \).כאן מגיעים לפאנץ’ ליין, שהוא מה שחשוב גם אם לא עקבתם אחרי החישובים - הטור הזה בכלל לא מתכנס. הסכום שלו יעבור כל מספר טבעי אם רק נסכם מספיק איברים בו. פירוש הדבר הוא שהתוחלת היא אינסופית, כלומר שאם נשחק במשחק הרבה מאוד פעמים, הזכייה “הממוצעת” שלנו תהיה אינסוף.

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

למשל, אם למשל היינו מגדירים את החיסור של אינסוף מאינסוף כאפס, היינו אוכלים אותה בגדול כשהיינו מנסים להחיל את השיטה הזו על הפרש הטורים (שסכום כל אחד מהם אינסוף) הבאים: \( \sum_{n=1}^\infty (n+1)-\sum_{n=1}^\infty n \) - ההפרש הוא מצד אחד אפס, על פי ההגדרה המטופשת שלנו ש”אינסוף פחות אינסוף הוא אפס”; ומצד שני, אם נחסר את הטורים איבר-איבר נקבל טור שסכומו עדיין אינסופי. בקיצור, בעיה.

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

למישהו יש הצעות?