חיפוש באתר

קישורים

עמודים

קטגוריות

ארכיב עבור 'הממ… מעניין…'

ממתינים לתוצאות הסופיות

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

יש נקודה חשובה שמשום מה מתעלמים ממנה: ההצבעה הסתיימה, ותוצאות הבחירות כבר נקבעו. רק שאנחנו עדיין לא יודעים מי ניצח כי לא סיימו לספור את כל הקולות.[1].

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

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

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

נניח שג’ו קיבל A קולות, ודונלד קיבל B קולות, ובאופן מסתורי אנחנו יודעים את הערכים המספריים של A ו-B לפני שהתחילה ספירת הקולות, ואנחנו גם יודעים כי A גדול מ-B, כלומר ג’ו ניצח. מה הסיכויים שג’ו יוביל לאורך כל תהליך ספירת הקולות?

יש מספר תרחישים אפשריים. נתחיל במקרה הכי קל: הפתק הראשון שהוצא מהקלפי הוא של דונלד. דונלד מוביל, ולכן ג’ו לא מוביל לאורך כל הספירה. הסיכוי לתרחיש הזה הוא B/(A+B).

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

מספר הקולות
שנספרו
למי ניתן הקולהיתרון של ג’ו
1דונלד1-
2דונלד2-
3דונלד3-
4ג’ו2-
5דונלד3-
6דונלד4-
7ג’ו3-
8ג’ו2-
9ג’ו1-
10ג’ו0

מה שקורה אחר כך לא ממש משנה. כל תרחיש שבו הקול הראשון הוא קול לדונלד מגיע בנקודה כלשהי לשוויון בספירה, וההסתברות לתרחיש הזה היא כאמור B/(A+B) . אפשר לתאר את התרחיש הזה בגרף הבא:

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

בואו נוסיף לגרף שלנו תרחיש אפשרי שבו ג’ו מתחיל להוביל, אבל לאחר מכן הספירה מגיעה לשוויון:

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

לכן ההסתברויות לשני סוגי התרחישים – תרחיש שבו דונלד מוביל בתחילת הספירה, ותרחיש שבו ג’ו מוביל בתחילת הספירה אך אינו מוביל לאורך כל הספירה – שוות, וכל אחת מהן שווה ל- B/(A+B). אם נחבר אותן נקבל את ההסתברות לתרחיש שבו ג’ו אינו מוביל לאורך כל הספירה, והסתברות זו שווה ל- 2B/(A+B).

מכאן קל לחשב כי ההסתברות שג’ו יוביל לאורך כל הספירה שווה ל-1 פחות ההסתברות שהוא לא יוביל לאורך כל הספירה, כלומר ל- (A+B)/(A-B).

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

אתם מוזמנים להמשיך להחזיק אצבעות למען המועמד המועדף שלכם.


הערות
  1. איזה קולות סופרים? זו שאלה אחרת שחורגת מתחומי העניין של הבלוג הזה []

לקריאה נוספת בנושאים הקשורים לנושא רשימה זו

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

הלכתם לקופת החולים וביצעתם בדיקה כלשהי. אמרו לכם שהדיוק של הבדיקה הוא 90%. מה זה אומר בעצם? איזה שאלות אתם צריכים לשאול את הרופא (או לברר עם ד”ר גוגל?) ואם אתם מחפשים בגוגל – מה בדיוק צריך לחפש?

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

הקלטת המפגש זמינה לצפיה בלינק https://www.youtube.com/watch?v=08F96yeDUzI

מקווה שתיהנו

לקריאה נוספת בנושאים הקשורים לנושא רשימה זו

למה אין 180 חברי כנסת?

הנה שאלה שמישהו שאל בקבוצת “שאלה קטנה” בפייסבוק:

וגם ציוץ מטוויטר:[1]

.

מה המשמעות של גודל הכנסת/פרלמנט

בפייסבוק מישהו ענה לשאלה בדבר מספר חברי הכנסת כי יש 120 חברי כנסת בגלל שזה היה מספר החברים בסנהדרין שפעל בימי בית שני, וזה נשמע לי הגיוני, למרות שלא מצאתי סימוכין לכך לא בויקיפדיה ולא באתר הכנסת. אבל זה לא עונה לחלק השני של השאלה. מאז קום המדינה האוכלוסייה גדלה בהרבה: מ-650 אלף בעת הכרזת המדינה לבערך מ-9 מיליון. יותר מפי 10. זה כמעט פי 14. אז אולי 120 חברי כנסת באמת לא מספיקים?

מצד שני, ראיתי גם טענות בעבר[2] לפיהן החזקה של 120 חברי כנסת זה בזבוז כסף עצום וצריך להקטין את מספר חברי הכנסת ל-70. אז כמה חברי כנסת באמת צריך? ומהן ההשלכות הפוליטיות הנגזרות מבחירה כזו או אחרת?[3]

אני זוכר שדובי קננגיסר התייחס פעם לנושא בבלוג המצויין והלא פעיל שלו, אבל לא הצלחתי למצוא את הקישור. ההסבר שלו, וסלחו על אי הדיוקים, הוא שמדובר בעניין של ייצוג. בעת הקמת המדינה, כל חבר כנסת ייצג בערך 5400 אזרחים[4]. כיום כל חבר כנסת מייצג 75000 אזרחים. אם היינו רוצים לשמור על אותה רמת ייצוג שהייתה בכנסת הראשונה ב-1949, היינו צריכים כמעט 1700 חברי כנסת. זה כמובן לא סביר.

דבר שני שצריך להתייחס אליו הוא הכח הפוליטי של כל חבר כנסת. כשיש 120 חברי כנסת, הכח הפוליטי של חבר כנסת בודד הוא 1/120, כלומר 0.83% מסך הכח הפוליטי. בכנסת של 180 חברים, הכם הפוליטי של כל חבר כנסת קטן יותר: 0.55%, ובכנסת של 70 חברים, הכח הפוליטי של חבר כנסת בודד גבוה באופן משמעותי: 1.4%. יש לכך השלכות כמובן: בכנסת קטנה של 70 חברים, אם חבר כנסת מחליט למשל לעזוב את מפלגתו ולחבור למפלגה אחרת, יש לכך הרבה יותר משמעות פוליטית בהשוואה לכנסת גדולה עם 180 חברים.

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

.

מה קורה בעולם?

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

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

.

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

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

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

.

מה יכול לקרות בישראל

בדקתי שני תרחישים: תרחיש בו מספר חברי הכנסת מוגדל ל-180 או מוקטן ל-70. רמת הייצוגיות והכח הפוליטי של כל חבר כנסת במצב הנוכחי ובשני התרחישים מוצגים בטבלה הבאה:

מספר חברי כנסתכח פוליטירמת ייצוגיות
701.43%128500
1200.83%75000
1800.56%50000

.

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

הנה, למשל, מפת הכנסת ה-22 אילו היו בה רק 70 חברים או 180 חברים:[8]

מפלגה/גודל הכנסת12018070
כחול לבן334819
ליכוד324719
הרשימה המשותפת13197
שס9146
יהדות התורה8135
העבודה7114
המחנה הדמוקרטי7114
ישראל ביתנו693
ימינה583

.

אבל מה שמשנה זה כמובן הגוש. הנה מפת הגושים בכנסת ה-22:[9]

גוש/ גודל הכנסת12018070
ימין548233
מרכז477027
הרשימה המשותפת13197
ישראל ביתנו693

.

וזו מפת הגושים בכנסת ה-23:[10]

גוש/ גודל הכנסת12018070
ימין588834
מרכז405923
הרשימה המשותפת15239
ישראל ביתנו7104

.

ושאלת השאלות: כמה מנדטים חסרים לגוש הימין כדי להשיג רוב בכנסת? התשובה בטבלה:

גודל הכנסתהרוב הדרושהכנסת ה-22הכנסת ה-23
1206173
1809193
703632

.

באופן לא מפתיע, בכנסת גדולה יותר חסרים לגוש הימין יותר קולות כדי להשיג רוב בכנסת. זה נכון גם עבור גוש המרכז כמובן. בכנסת ה-22 חסרו לגוש הזה 14 מנדטים כדי להשיג רוב, ואילו היו בכנסת 180 חברים היו חסרים לגוש זה 21 מנדטים.

כאשר תוצאות הבחירות צמודות ההבדל עשוי להיות משמעותי. אילו היו בכנסת הזו רק 70 חברי כנסת, אז גוש הימין היה צריך “להעביר” אליו רק 2 חברי כנסת מחוץ לגוש במקום שלושה.[11] לעומת זאת, אם היו בכנסת 180 חברים, המצב היה זהה מבחינת מספר הקולות החסרים לגוש הימין כדי להשיג רוב.


הערות
  1. כן, מישהו חסם אותי []
  2. אין לי הפניות. אני מסתמך על זכרוני. []
  3. אני נמנע בכוונה מדיון בהשלכות הכספיות במסגרת הפוסט. מי שמעוניין מוזמן לדון בכך בתגובות. []
  4. החישוב: 650000/120 []
  5. או שתיהן, כמו שנהוג למשל בגרמניה []
  6. כגון סנאט ובית הנבחרים במדינות ארצות הברית []
  7. הותרתי את ישראל ביתנו מחוץ לגוש הימין ואת הרשימה המשותפת מחוץ לגוש המרכז/שמאל, למרות שמקומן אמור להיות בשני הגושים האלה, בהתאמה []
  8. קוד R לחישובי המנדטים []
  9. הותרתי את ישראל ביתנו מחוץ לגוש הימין ואת הרשימה המשותפת מחוץ לגוש המרכז/שמאל, למרות שמקומן אמור להיות בשני הגושים האלה, בהתאמה []
  10. כן, אני יודע שגוש המרכז בכנסת הזו זה לא מה שהיה פעם []
  11. בסוף הם הצליחו להעביר כמעט 20, אבל זה סיפור אחר. []

לקריאה נוספת בנושאים הקשורים לנושא רשימה זו

משפט הקופים

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

אפשר לגשת לחידה הזו בכמה צורות.

הגישה ה-“נאיבית”

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

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

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

עכשיו רק צריך לשקלל את האפשרויות בהסתברויות שלהן. כלומר לחשב את זה:

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

גישה שניה: מציאת בעיה דומה

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

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

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

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

  • שני הכדורים בסל הימני
  • שני הכדורים בסל השמאלי
  • כדור א בסל הימני וכדור ב בסל השמאלי
  • כדור א בסל השמאלי וכדור ב בסל הימני

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

אז בעצם יכולנו להקל על הקוף ולתת לא להטיל מטבע. אם יצא פלי, מה חבל. אם יצא עץ, הקוף יכול לטפס על העץ ולקטוף לעצמו בננה.

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

גישה שלישית: שרשרת מרקוב – לא להיבהל!

דיברתי כבר על שרשראות מרקוב כאשר דנתי בבעיית המטריות. שאלת הקוף היא עוד דוגמא נחמדה לשרשרת מרקוב.

ניזכר: שרשרת מרקוב היא קבוצה של מצבים, בצירוף ההסתברות לעבור ממצב למצב.

לשרשרת של הקוף יש שלושה מצבים:

  1. שני סלים ריקים. נסמן מצב זה ב-00.
  2. סל אחד ריק ובשני יש כדור. נסמן מצב זה ב-01.
  3. כדור אחד בכל סל. נסמן מצב זה ב-11.

אם הקוף במצב 00 הוא יכול לעבור רק למצב 01. יש שני סלים ריקים, הוא מקבל כדור ושם אותו באחד הסלים. זה כל מה שאפשר. ההסתברות לעבור ממצב 00 למצב 01 שווה ל-1.

אם הקוף במצב 01 יכולים לקרות שני דברים: או שהוא שם את הכדור הבא בסל שכבר יש בו כדור. בסל יש שני כדורים, מרוקנים אותו, והקוף חוזר למצב 00. זה קורה בהסתברות חצי. הדבר השני שיכול לקרות הוא שהקוף ישים את הכדור בסל הריק, יגיע למצב 11, יקבל בננה, והמשחק נגמר. גם זה יכול לקרות בהסתברות חצי.

אם הקוף במצב 11 הוא כבר לא מתעניין בנו, כי יש לו בננה. ההסתברות לעבור ממצב 11 למצב 00 או 01 היא 0. המצב הבא, אם נתעקש, יהיה שוב 11. כלומר, ממצב 11 עוברים למצב 11 בהסתברות 1.

הנה תיאור ציורי של השרשרת:

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

איך כל זה עוזר לנו?

נניח שממוצע מספר הצעדים/כדורים מ-00 ל-11 הוא X.

כפי שראינו קודם, X שווה ל-2 בהסתברות 0.5.

אבל אם בשני הצעדים הראשונים שלו הקוף יצא מ-00 וגם חזר לשם, אז ממוצע מספר הצעדים שנותרו לו מעכשיו הוא גם כן X! וזאת מכיוון שמצבו עכשיו, לאחר שני צעדים לא שונה מהמצב ההתחלתי. כלומר, ממוצע מספר הצעדים אם אנחנו יודעים שהוא כבר עשה סיבוב אחד של 00 ל-01 ל-00 הוא 2+X. ההסתברות שזה יקרה גם כן שווה לחצי. ולכן

פתרון המשוואה הזו הוא X=4.

משפט הקופים

המסקנה מתוך כל הדיון הזה: אם תתנו לקוף לתקתק מספיק זמן על מכונת כתיבה הוא ידפיס את כל כתבי שייקספיר.

רגע? מה?

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

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

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

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

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

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


הערות
  1. מכירים את הסיפור על המתמטיקאי והפיזיקאי שנתבקשו להרתיח מים בקומקום? []
  2. אני מקווה []

לקריאה נוספת בנושאים הקשורים לנושא רשימה זו

עוד שימוש מפתיע לרנדומיזציה: קבלת החלטות

לפני שבוע, הצייצן eSivion העלה סקר לא שגרתי בטוויטר, בו ביקש מהמשיבים להצביע כך התפלגות התשובות לסקר תהיה 10% לתשובה א, 20% לתשובה ב, 30% לתשובה ג ו-40% לתשובה ד:

הניסוי הצליח![1]

איך עושים את זה, או יותר נכון, איך הציבור הצליח לעשות את זה?

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

 

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

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

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

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

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


הערות
  1. אם כי מבחן כי בריבוע מראה כי ההתפלגות של ההצבעות שונה באופן מובהק סטטיסטית מההתפלגות לה קיווה אי-שיוויון []
  2. כמו שקרה בסרטו של אלפרד היצ’קוק זרים הרכבת []
  3. אני מפשט קצת את הדברים []
  4. גם ככה הסכוי לחבוט נמוך למדי. החובטים הממש טובים מצליחים לחבוט בכדור בכ-30% מהפעמים []

לקריאה נוספת בנושאים הקשורים לנושא רשימה זו