נסיכת המדעים

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

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

הבוקר דווח כי הדודג'רס חזרו עם הצעה חדשה: שוב 45 מליון דולר לשנתיים, אך באופן שהשחקן יקבל סכום גדול יותר בשנת 2009 לעומת הסכום שהיה אמור לקבל בהצעה הראשונית. בעידן שבו הריבית קרובה ל-0 זה לא משהו, אבל עדיין מדובר בשיפור לעומת ההצעה הקודמת. עד כה לא דחה רמירז את ההצעה. האם העובדה שאימוני האביב כבר החלו בשבוע שעבר והדודג'רס כבר שיחקו אתמול את משחק הידידות הראשון שלהם גורמת לכוכב העל וסוכן העל שלו ללחוץ על הגז קצת יותר בעדינות? אמשיך לעקוב ולדווח.

עדכון: הבוקר (27.2.2009) דחה רמירז גם את ההצעה הזו.

עדכון מאוחר (שבת 7.3.2009): בתאריך 4.3.2009 חתמו רמירז והדודג'רס על חוזה חדש, לפיו רמירז ישחק בשנתיים הבאות בשורות הדודג'רס ויקבל תמורת שירותיו 45 מליון דולר. היה שווה לחכות.

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

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

השחקן הראשי הוא סוכן העל סקוט בוראס, המייצג כמה מהכוכבים הגדולים ביותר בליגה. לפני מספר שבועות, שיחקו בוראס והתופש (catcher) ג'ייסון ואריטק את המשחק מול קבוצת הבוסטון רד-סוקס. ואריטק שיחק בבוסטון את כל הקריירה שלו עד כה, סה"כ 12 עונות מ-1997 עד 2008. בסיום שנת 2008 הסתיים החוזה שלו עם הקבוצה, והוא הפך לשחקן חופשי. בוסטון הייתה מעוניינת כי ואריטק, שהוא גם קפטן הקבוצה, ימשיך לשחק בשורותיה, והציעה לו להכנס להליך בוררות. בהליך הזה כל צד מציע הצעה. השחקן אומר כמה כסף הוא חושב שצריך לשלם לו, הקבוצה אומרת כמה כסף היא מציעה, והבורר חייב לפסוק לטובת אחד משני הצדדים. כלומר, אם הקבוצה מציע לך שכר של מליון דולר, ואתה מבקש שלושה מליון, התוצאה תהיה שתקבל מליון, או שלושה מליון. לבורר אסור לפסוק פשרה לפיה השכר יהיה איזשהו סכום ביניים. יש עוד קאטש קטן: לקבוצה אסור להציע לשחקן שכר נמוך מהשכר שקיבל בעונה הקודמת. כיוון שואריטק הרוויח בשנת 2008 כ-10.4 מליון דולר, המשמעות של הסכמה לבוררות מבחינתו הייתה הבטחת שכר של 10.4 מליון דולר לפחות בשנת 2009. ואריטק, כנראה בעצת סוכנו בוראס, רצה ללכת על גדול. הוא קיווה כי יצליח לקבל בקבוצה אחרת חוזה שמן יותר, למשך כמה שנים. הוא סירב להצעת הבוררות, ופנה לפתוח במשא ומתן עם קבוצות אחרות. אבל הקבוצות האחרות לא עמדו בתור. מתברר כי תופש בן 37 שסיים את עונת 2008 עם סטטיסטיקה בינונית מינוס אינו סחורה מבוקשת בשוק. בסופו של דבר, חתם ואריטק על חוזה לשנתיים עם קבוצתו משכבר הימים, הבוסטון רד-סוקס. חוזה זה מבטיח לו כי במשך השנתיים הבאות ירוויח בסך הכל 8 מליון דולר.

המקרה של ואריטק לא מרתיע לקוח אחר של בוראס, החובט מני רמירז. רמירז הוא סופר-סטאר אמיתי, שבמשך 16 שנותיו בליגה הציג ממוצע חבטות מעולה של 0.316,  והשיג 527 הקפות מלאות (home runs). לאחר שהועבר באמצע העונה שעברה מבוסטון לקבוצת לוס אנג'לס דודג'רס, השיג שם ב-57 משחקים ממוצע חבטות מדהים של 0.396, ולקח את הקבוצה עד לסדרת הגמר של הנשיונל ליג, שם הפסידה הקבוצה לפילדלפיה פיליז, שהמשיכה בדהרתה לזכיה היסטורית בוורלד סרייס. שירותיו של רמירז אינם זולים. בשנת 2008 היה שכרו השנתי כמעט 19 מליון דולר. חוזהו הסתיים כעת, וקבוצת הדודג'רס, שהייתה מרוצה מאוד מביצועיו, הציעה לו חוזה חדש לשנתיים בסכום כולל של 45 מליון דולר – העלאה צנועה של כ-20% לעומת השנה הקודמת.

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

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

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

"הלירה היא לפעמים מאה ועשרים גרוש, ולפעמים יותר או פחות; וכן שונה מחירה בכל עיר ועיר: בירושלים מאה ועשרים, וביפו מאה וארבעים וכו'; וכן שאר המטבעות משתנות ומתחלפות."

אין חדש תחת השמש.

הבלוג המעניין "The list universe" (שאני קורא באופן קבוע דרך הרסס, מומלץ) מביא היום את רשימת 10 האמונות המדעיות המופרכות של העבר (או יותר נכון, את ה-top 10 של הקטגוריה הזו). ברשימה ניתן למצוא, בין היתר, את האלכימיה, התיאוריה הגיאוצנטרית (לפיה הארץ היא מרכז היקום), תיאוריית הפלוגיסטון, וכמובן, את תיאוריית הבריאה הספומטנית.

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

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

ב-Ynet הופיע ראיון עם הקומבינטור הישראלי הידוע נוגה אלון. מעניין.

מחקר שפרסם האתר CareerCast.com מדרג 200 משרות בארה"ב, מהטובה ביותר עד הגרועה ביותר. המחקר מדווח בכתבה בוול סטריט ג'ורנל, שם ניתן לצפות ב-20 המקצועות שבראש הרשימה, ו-20 המקצועות הסוגרים אותה.

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

עוד מקצועות טובים: אקטואר (מקום שני) – שזו בעצם התמחות בסטטיטיקה ליישומי ביטוח, פילוסוף (מקום 12) יותר טוב מרופא (מקום 13) אך פחות טוב מכלכלן (מקום 11), ואסטרונום (מקום 20).

מבט בתחתית הרשימה מלמד שעדיף להיות פועל איסוף זבל (מקום 194) מאשר נהג מונית (מקום 198), להיות אח או אחות לא הרבה יותר טוב (מקום 184).

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

הקדמה

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

מושג החנוכה ומושגים נלווים

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

נסים

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

נרות ואור

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

מאכלים

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

מקומות

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

קבוצות אנשים

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

אישים – המכבים מול היווני

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

 

חג שמח לכולם!

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

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

"זה תלוי", אמר א', "נניח שבמעטפה הזו יש 1000 דולר. האם במעטפה השניה יש 2000 דולר, או רק 500?". "את זה", אמר מוריס, "תדע רק אם תחליף את המעטפות".

א' ניסה לחשוב: נניח שאכן יש כאן 1000 דולר. אם במעטפה השניה יש 2000 דולר, אז הוא ירוויח 1000 דולרים נוספים, אבל אם יש בה רק 500 דולר, הוא יפסיד 500 דולר. 50% סיכוי להרוויח 1000, 50% סיכוי להפסיד 500. הוא חישב את תוחלת הרווח: חצי מאלף הם 500, חצי ממינוס חמש מאות הם מינוס 250, לכן תוחלת הרווח היא 250 דולר. "אוקי, אני מחליף", אמר. הוא החזיר את המעטפה שבידו למוריס, וקיבל את המעטפה השניה לידיו.

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

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

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

שימו לב: מוריס הכין את המעטפות מראש. אם במעטפה הראשונה יש 1000 דולר, אז ההסתברות שבמעטפה השניה יש 2000 דולר היא לא 0.5. הסכום שבמעטפה השניה אינו משתנה מקרי אלא קבוע. לכן ההסתברות הזו היא או 0, אם מוריס הכין מעטפות שבן 1000 דולר ו-500 דולר, או 1, אם מוריס הכין מעטפות שבן 1000 דולר ו-2000 דולר.

השיקול ההסתברותי הנכון שעל א' היה לעשות הוא כזה: "נניח שהיו שתי מעטפות, באחת מהן 1000 דולר ובשניה 2000 דולר. יש סיכוי של 50% שאני מחזיק את המעטפה עם 1000 הדולרים (כי מוריס הושיט לי את אחת משתי המעטפות ששלף באקראי מכיסו), ולכן אם אחליף ארוויח עוד 1000 דולר. יש גם סיכוי של 50% שאני כבר מחזיק את המעטפה עם הסכום הגבוה שהוא 2000 דולר, ולכן אם אחליף אפסיד 1000 דולר. מכאן שתוחלת הרווח מהחלפת המעטפות היא 0, ולכן לא משנה (בתוחלת) אם אחליף את המעטפה או לא אחליף אותה."

מה קורה כאשר הסכום במעטפה הוא משתנה מקרי?

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

אפתח בתיאור הבעיה המוכללת כפי שהציג אותה פרופ' אלון. הרעיון הוא שהסכומים המוכנסים למעטפות לא נקבעים באופן שרירותי, אלא על ידי מנגנון הסתברותי: תחילה בוחרים מספר טבעי באופן הבא: המספר 1 נבחר בהסתברות 0.5, 2 נבחר בהסתברות 0.25, 3 נבחר בהסתברות 0.125, וכן הלאה – המספר k נבחר בהסתברות 0.5 בחזקת k. (בניסוח סטטיסטי פורמלי – המספר שנבחר הוא משתנה מקרי גיאומטרי עם פרמטר 0.5). לאחר שנבחר המספר, שנסמנו ב-m, מכניסים למעטפה אחת 10 בחזקת m דולרים, ולשניה מכניסים 10 בחזקת m+1 דולרים. למשל, אם נבחר המספר 3 מכינים שתי מעטפות, באחת מהן יהיו 1000 דולר, בשניה 10000. כעת בוחרים את אחת משתי המעטפות ונותנים אותה לשחקן, עם האופציה להחליף אותה במעטפה השניה. האם כדאי לו להחליף?

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

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

ברור שאם פותחים את המעטפה ומוצאים בה 10 דולר, הרי שבמעטפה השניה יש 100 דולר בהסתברות 1, וכדאי להחליף. מה קורה אם פותחים את המעטפה ומוצאים בה 100 דולר (ההסתברות לכך היא 3/8)? במקרה כזה יש שתי אפשרויות: או שבמעטפה השניה יש 10 דולר, או שיש בה 1000 דולר. קל לחשב (ואלכסנדרוביץ הסביר את החישוב) כי הסיכוי שבמעטפה השניה יש 10 דולר בלבד הוא 2/3 והסיכוי כי במעטפה השניה יש 1000 דולר הוא 1/3. לכן תוחלת תוספת הסכום המתקבל כתוצאה מההחלפה היא 240 דולר, וכדאי להחליף. הטיעון הזה תקף לכל סכום שנמצא במעטפה הראשונה, ולכן ניתן לסכם ולומר כי כאשר מקבלים מעטפה במשחק הזה כדאי להחליף אותה במעטפה השניה.

טוב, החלפנו את המעטפה הראשונה שקיבלנו במעטפה השניה, ועכשיו מוצע לנו להחליף שוב את המעטפות. האם כדאי להחליף שוב? התשובה שלילית. אם במעטפה הראשונה שקיבלנו לידנו היו 10 דולר, עכשיו אנחנו מחזיקים במעטפה שבה 100 דולר, ולא כדאי להחליף. ואם במעטפה הראשונה שקיבלנו לידנו הייתה חזקה גדולה מ-1 של 10, ואשאר שוב בדוגמא של 100 דולר במעטפה הראשונה שהוחלפה, הרי יש שתי אפשרויות: או שבידנו 1000 דולר ואם נחליף שוב נפסיד 900 דולר, וההסתברות לכך היא 1/3, או שבידנו 10 דולר ואם נחליף שוב את המעטפות נרוויח 90 דולר, וההסתברות לכך היא 2/3. ההחלפה השניה תוביל אותנו לתוחלת רווח שלילית של 240-, ולכן לא כדאי להחליף שוב את המעטפות. שימו לב כי הטיעון הזה תקף גם אם פותחים את המעטפה הראשונה, וגם אם לא.

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

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

כלומר, אם מוגרל המספר 1 מההתפלגות הגיאומטרית, נכין שתי מעטפות שבאחת מהן 1.5 דולרים (או אלפי דולרים, אם תרצו, זה לא משנה), ובשניה 2.25 דולרים, ואם יעלה המספר 5 נכין שתי מעטפות שבאחת מהן 7.59375 דולרים ובשניה 11.390625 דולרים. עכשיו נוכל לחזור על השיקול שערכנו קודם: אם במעטפה הראשונה שקיבלנו יש 1.5 דולר, כדאי להחליף כי במעטפה השניה יש בודאות סכום גבוה יותר של 2.25 דולר. לעומת זאת, אם במעטפה יש חזקה של 1.5 הגדולה מ-1, נניח 2.25, הרי שהחלפה תוביל לרווח של 1.25 דולר (3.375 פחות 2.25) בהסתברות 1/3, ולהפסד של 0.75 (2.25 פחות 1.5) בהסתברות 2/3. שקלול הרווח וההפסד על פי ההסתברויות מגלה כי החלפה תוביל להפסד של 0.125, ולכן לא כדאי להחליף.

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

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

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

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

פורסם לראשונה באתר "רשימות" בתאריך 11 באוגוסט 2008 שם התקבלו 11 תגובות

גדי אלכסנדרוביץ'  [אתר]  בתאריך 8/11/2008 11:12:09 PM

תגובה (שפרסמתי גם בבלוג שלי)

היי יוסי. ראשית, אתה יותר ממוזמן לקרוא לי "גדי" בבלוג שלך. אין כל צורך באלכסנדרוביץ הזה. שנית, לכבוד הוא לי שאתה טורח לקרוא את הבלוג שלי, לא כל שכן להגיב לו בפוסטים משלך. שלישית, תודה על זווית הראייה הנוספת שלך על הבעיה – בהחלט לא ניסיתי לתקוף אותה מהכיוון הזה עד עתה (והייתי צריך).
כעת, לעניין עצמו – ייתכן שאני מתבלבל בחשבון שלי, אבל הרושם שאני מקבל הוא שאכן, אם אתה בוחר בתור בסיס לכפולות של הכסף משהו שהוא קטן מ-2 אתה מקבל תוחלת רווח סופית, ולכן מפיל לקרשים את טיעון ה"תוחלת אינסופית" המדובר, אבל מצד שני, גם החישוב המקורי שממנו נובע שכדאי להחליף כבר לא עובד. שיחקתי עם זה קצת כרגע וקיבלתי שהנוסחה הכללית של "תוחלת הרווח מההחלפה", כש-a הוא הבסיס שלך, היא הנוסחה הבאה:
a^(n-1)*(a^2-3a+2)/3
בפרט, שים לב שאם מציבים a=10 מקבלים את הנוסחה שקיבלתי לעיל. הנוסחה הזו לא חיובית תמיד; עבור ערכים של a שקטנים מ-2 (וגדולים מ-1) מקבלים תוחלת רווח שלילית, כך שלא כדאי להחליף. מכאן שיש שתי בעיות – אחת עם a קטן מ-2, שהיא "מנוונת" – אמנם, התוחלת לא אינסופית בה, אך גם לא כדאי להחליף ולכן אין פרדוקס, ואחת עם a גדול מ-2, שבה התוחלת אינסופית ותמיד כדאי להחליף.
לסיכום, אני לא בטוח שאני מסכים עם הטענה שלך של "בעיית המעטפות הציג פרופ' אלון לא תשתנה בצורה עקרונית אם נשנה אותה כך שתוחלת הרווח של מקבל המעטפה תהיה סופית". ייתכן שאפשר לשנות את פרמטר ההתפלגות הגאומטרית; אבל שינוי היחס בין הסכומים הוא כן בעל חשיבות, לטעמי. מצד שני, ייתכן מאוד שאני סתם מתחרבש עם המתמטיקה.

דובי  [אתר]  בתאריך 8/12/2008 3:00:25 AM

ומה אם פותחים את המעטפה השניה?

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

יוסי לוי  [אתר]  בתאריך 8/13/2008 9:30:49 AM

תגובה לגדי

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

דובי  [אתר]  בתאריך 8/13/2008 8:20:02 PM

ללא נושא

אני עדיין לא מבין איך זה שהסכומים נקבעים בצורה מקרית משנה משהו – הם נקבעו, ועכשיו הם במעטפות, וזהו. אין שתי אופציות למה שיש במעטפה השניה, יש רק אופציה אחת. זה שאנחנו לא יודעים מה הסכום לא משנה את זה.
אני חושב שהבעיה היא שאנחנו מקבלים את ההנחה שבמעטפה שלנו יש את ה-X, ולכן במעטפה השניה יש או 0.1*X או 10X. אבל זה לא נכון. יש שתי מעטפות, אחת מהן מכילה X, ואחת מהן מכילה 10X. אנחנו מחזיקים באחת מהן (בהסתברות של חצי) – אנחנו לא יודעים איזה, ולכן אין סיבה להחליף אף פעם: התוחלת של ההחלפה היא 0. יש רק מצב אחד שבו פתיחת אחת המעטפות מוסיפה לנו מידע – כשהיא מכילה 10 (כלומר, את המינימום) – ואז אנחנו יודעים שהמעטפה השניה עדיפה. זהו, בכל שאר המקרים, כמו שאומרת האינטואיציה שלנו, להחלפה אין משמעות.

יוסי לוי  [אתר]  בתאריך 8/14/2008 8:24:51 AM

תשובות לדובי

1) זה לא ממש משנה איזו מעטפה פותחים – זו שאצלך או זו שאצל מוריס, זה רק משנה את הכיוון של שיקולי ההחלפה.
2) בתגובה השניה שלך אתה נופל בכשל ידוע: זה שיש שתי תוצאות אפשריות, זה לא אומר שלכל תוצאה הסתברות שווה. האם ירד מחר שלג בירושלים (היום 14 באוגוסט, להזכירך)? או שכן, או שלא, כמובן, אבל הסיכוי שמחר ירד שלג בירושלים הוא ממש לא 50%. איך אתה יודע את זה? יש לך קצת אינפורמציה על מזג האויר בירושלים. גם כאן, אם אתה יודע את המנגנון לפיו נקבעו הסכומים שבמעטפות, אתה יכול לנצל את האינפורמציה הזו (על ידי שימוש במשפט בייס.
דוגמא קצת יותר מסובכת המדגימה את הכשל הזה – התעלמות מאינפורמציה המאפשרת להעריך מחדש את ההסתברויות – היא בעיית שלושת הדלתות (הידועה גם כבעיית מונטי הול), עליה כתבתי כאן בעבר:

דובי  [אתר]  בתאריך 8/14/2008 4:05:58 PM

ללא נושא

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

יוסי לוי  [אתר]  בתאריך 8/17/2008 8:29:46 AM

דובי – הסבר קצר על הסתברות מותה

אם פתחת מעטפה ויש בה 1000 שקלים (שער הדולר נמוך, אה?), אז יש אחת משתי אפשרויות: או שהמספר שעלה בגורל בשלב הראשון היה 2, או שהוא היה 3. מאחר ו-2 עולה בהסתברות גבוהה כפליים מההסתברות של שבה עולה 3 (רבע מול שמינית), הרי שגם ההסתברות המותנה של 2 (כלומר ההסתברות ש-2 עלה כאשר אתה כבר יודע כי המספר שעלה הוא 2 או 3) גדולה כפליים מההסתברות המותנה של 3. ההסתברות המותנה של כל המספרים האחרים היא 0 (למשל, אם אתה יודע כי המספר שעלה בגורל הוא 2 או 3, אז ההסתברות כי 4 עלה בגורל היא אפס), ולכן ההסתברות המותנה של 2 היא 2/3, שזה כפליים מההסתברות המותנה של 3 השווה לשליש.

יוסי לוי  [אתר]  בתאריך 8/17/2008 8:34:59 AM

דובי – הסבר אלטרנטיבי

הסבר אלטרנטיבי מדוע במקרה של 1000 שקלים במעטפה, ההסתברות המותנה של 100 שקלים במעטפה השניה היא 2/3:
בוא נניח שאתה עושה את התרגיל הזה מליון פעמים. בערך ברבע מהמקרים תגריל 2 ותכין מעטפות עם 100 שקלים ו-1000 שקלים, ובערך בשמינית מהמקרים תגריל 3 ותכין מעטפות עם 1000 שקלים ו-10000 שקלים. בשאר המקרים תקבל משהו אחר. עכשיו תזרוק את כל המקרים האחרים – תשאר עם 250000 זוגות של 100-1000 (בערך) ו-125000 זוגות של 1000-10000. עכשיו מתוך 375000 זוגות המעטפות האלה תבחר באופן מקרי זוג אחד. מה הסיכוי שייבחר זוג של 100-1000? בערך 250000 חלקי 375000 כלומר 2/3

דובי  [אתר]  בתאריך 8/17/2008 4:08:00 PM

ללא נושא

יוסי, באמת שאין ולא הייתה לי שום בעיה להבין למה הסיכוי לזוג מספרים 100-1000 היא 2/3 לעומת הסיכוי לזוג המספרים 1000-10000 בהנתן שאחד מהם הוא 1000. מה שאני עדיין לא מצליח להבין זה איך זה שכשאני פותח את המעטפה שלי כדאי לי להחליף, אבל אם אני פותח את המעטפה שלא בחרתי בה, לא כדאי לי להחליף.

יוסי לוי  [אתר]  בתאריך 8/17/2008 4:30:22 PM

אוקיי

אתה לוקח מעטפה, ופותחים את המעטפה השניה. יש בה 1000 דולרים קנדיים. לכן, בהסתברות 2/3 יש במעטפה שלך 100 דולר, ואם תחליף תרוויח 900 דולר, ובהסתברות 1/3 יש במעטפה שלך 10000 דולר, ואם תחליף תפסיד 9000 דולר. שקלל את הרווחים בהסתברויות, ותקבל כי תוחלת הרווח מההחלפה במקרה זה היא מינוס 2400 דולר, ולכן לא כדאי להחליף.

אותו 1  בתאריך 8/27/2008 1:40:38 PM

אבל אבל אבל

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

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

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

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

הפרדיגמה הראשונה היא מה שאלון כינה: "Randomization -Derandomization". הרעיון הוא לתקוף בעיה דטרמיניסטית באמצעות אלגוריתם הסתברותי (כלומר, אלגוריתם הנותן תשובה נכונה לבעיה בהסתברות מסויימת, ואך יש הסתברות חיובית כי התשובה שהאלגוריתם נתן אינה נכונה). לאחר מכן, ניתן (אולי) לקחת את האלגוריתם הההסתברותי ו"לשפצר" אותו באופן שיהפוך לדטרמינסטי. הוא נתן שתי דוגמאות. דוגמא אחת היא אלגוריתם הסתברותי לקביעה האם מספר טבעי נתון הוא ראשוני או פריק, שפיתחו Agrawal ושותפיו. מספר שנים לאחר מכן, פרסמו Agrawal ושותפיו אלגוריתם דטרמינסטי יעיל לקביעת הראשוניות/פריקות של מספרים טבעיים, המבוסס על עקרונותיו של האלגוריתם ההסתברותי. אלון טוען כי הדרך לאלגוריתם הדטרמינסטי הייתה חייבת לעבור באלגוריתם ההסתברותי שקדם לא, ולא ניתן היה לבצע ישירות את הקפיצה המחשבתית אל האלגוריתם הדטרמינסטי. דוגמא נוספת שנתן אלון היא בעיה בתורת הגרפים עליה עבד עם מספר שותפים (קביעה האם גרף מכיל מסלול באורך נתון) שעברה תהליך דומה – אלגוריתם הסתברותי תחילה, ולאחר מכן אלגוריתם דטרמיניסטי שהוא שכלול של האלגוריתם ההסתברותי.

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

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

פורסם לראשונה באתר "רשימות" בתאריך 6 במאי 2008  שם התקבלו 8 תגובות

עומר  בתאריך 5/6/2008 6:06:57 PM

אם ההסתברות

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

אלעד-וו  בתאריך 5/6/2008 7:52:46 PM

כתבת היטב

עומר: הנח שמס' הכדורים בעולם סופי.

עומר  בתאריך 5/6/2008 8:44:38 PM

אלעד-

אפילו במקרה זה – יתכנו מרחבי הסתברות שבהם למאורעות לא ריקים יש סיכוי אפס; השיטה ההסתברותית טוענת רק את הכיוון "הסתברות >0 גוררת מאורע לא ריק".

אלעד-וו  בתאריך 5/6/2008 8:54:28 PM

עומר, אתה מתקטנן

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

אלעד-וו  בתאריך 5/6/2008 8:55:19 PM

פוסט מצויין

כתבת מצויין ומדוייק.
הנה מספר תיקונים קטנים:
1. האלגוריתם הרנדומי לבדיקת ראשוניות הוא של מיכאל רבין (ישראלי, אגב) ולא של Agrawal)
2. כתבת "אלון טוען כי הדרך לאלגוריתם הד טרמינסטי הייתה חייבת לעבור באלגוריתם ההסתברותי שקדם לא, ולא ניתן היה לבצע ישירות את הקפיצה המחשבתית אל האלגוריתם הדטרמינסטי.".
הייתי מחליף את הביטויים "לא ניתן" ו"הייתה חייבת" במשהו יותר שמרני. הייתי כותב "היה מאד קשה קונספטואלית להגיע לאלגוריתם הדטרמיניסטי בלי למצוא קודם את האלגוריתם הרנדומי" או משהו בסגנון. תמיד ייתכן שמישהו ימצא ישירות את האלגוריתם הדטרמיניסטי, אבל הדרך היחידה שידועה לקבל אלדוריתם דטרמיניסטי לבעיה הזאת עברה (בראיה היסטורית) דרך האלג' הרנדומי.
3. כתבת "המטרה שלו, כפי שהבנתי מאוחר יותר, הייתה להצביע על כך שחשיבה במונחים הסתברותיים אינה טריויאלית, ויותר מכך, האינטואיציה לא תמיד "עובדת" כשדנים בהסתברות.".
לא הייתי כותב "לא תמיד עובדת". מישהו שאינו בקיא במתימטיקה יכול לחשוב שזו פילוסופיה, ושלא תמיד 1 ועוד 1 שווה 2. הייתי במקום זה אומר שכשחושבים במונחים הסתברותיים קל להתבלבל ולעשות טעויות. למשל, קל להתבלבל כשמתעסקים עם הסתברויות מותנות.
4. לבסוף, בנוגע לשיטה ההסתברותית, הבנתי למה החלפת את הדוגמה שנוגה נתן בדוגמה אחרת. (אם יותר לי לנחש, נוגה הראה חסם תחתון למספרי רמזי?). אבל הדוגמה שנתת לטעמי לא ממש קולעת — אין בה מספיק מה"אופי" של השיטה ההסתברותית. שתי דוגמאות מצויינות (אבל, כמו שאמרת, לא טריוויאליות) ניתנות במאמר וויקיפדיה שכבר קישרת אליו: http://en.wikipedia.org/wiki/Probabilistic_method
דוגמה נוספת לשימוש בשיטה ההסתברותית היא להוכיח שיש אוסף של מליון תתי קבוצות של המספרים בין 1 ל-1000
, כך שהחיתוך בין כל שתי קבוצות באוסף הוא בגודל לכל היותר 600. קשה מאד לבנות כזה אוסף, אבל קל להוכיח שקיים כזה אוסף: בוחרים את הקבוצות באקראי, ומוכיחים בעזרת יוניון-באונד שבהסתברות גדולה מאפס הוא מקיים את התכונות הנדרשות. זו דוגמה שחביבה על טימוטי גאוארס, ונידונה במאמר (הפופולרי) המעננין שלו "שתי התרבויות של המתימטיקה" שניתן לקריאה כאן:
http://www.dpmms.cam.ac.uk/~wtg10/2cultures.pdf
תודה על הפוסט. תמיד תענוג לשמוע הרצאות של נוגה, ואפילו לשמוע על הרצאות של נוגה. 🙂

עומר  בתאריך 5/7/2008 9:21:14 AM

אלעד וו-

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

גיל  [אתר]  בתאריך 5/8/2008 8:03:51 AM

בהקשר הזה חשוב לציין

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

יוסי לוי  [אתר]  בתאריך 5/11/2008 7:36:57 AM

תודה לכל המגיבים עד כה

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