אתמול, במסגרת טקס חלוקת תעודות שנערך בפקולטה למדעים מדוייקים באוניברסיטת תל אביב, הרצה פרופ’ נוגה אלון, חתן פרס ישראל למתמטיקה לשנת 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
תודה לכל המגיבים עד כה
כפי שציינתי, בסך הכל הבאתי את עיקרי הדברים שנשארו בזכרוני מההרצאה הזו – מעין סוג של “טלפון שבור”. אני מודה לאלעד עומר וגיל על שהרחיבו את דברי והבהירו את התמונה – גם לי.