חידה פוליטית

[jaXon]

חידה פוליטית

הנה משהו שהעלתי בראש, חישבתי, ואני מעוניין להשוות תוצאות. נניח מצב דמיוני לחלוטין שכל 120 חברי הכנסת נוכחים בכנסת. הם מתיישבים באקראי ב 120 המושבים. נגדיר "חילוף" מצב שבו A יושב בכסא של B ו B בכסא של A. 1) כמה חילופים יהיו בממוצע? (תוצאה מפתיעה) 2) מה הסיכוי שבכלל קיים חילוף כלשהו? ומה קורה בפרלמנט עם N נציגים? למה ההסתברות שואפת?

 

[freedom rider]

התשובה שלי

נגדיר משתנה מקרי Xij שערכו שווה ל-1 אם היה חילוך בין i לבין j, וערכו 0 בכל מקרה אחר. אם X הוא מספר החילופים הכללי, אז X שווה לסכום של Xij על פני כל זוגות ה-ij האפשריים. אם יש N חברי כנסת, אז יש (C(N,2 זוגות כאלה. התוחלת של X היא כמובן סכום התוחלות של כל ה-Xij, ומכיוון שלכל ה-Xij אותה התפלגות, אז התוחלת של X (מספר החילופים הממוצע) שווה ל-(C(N,2 פעמים התוחלת של X12. ואילו התוחלת של X12 עצמה שווה להסתברות ש-1=X12. נחשב הסתברות זו בעזרת קצת קומבינטוריקה: יש !N אפשרויות להושיב את כל החברים באופן כלשהו, ורק !(N-2) אפשרויות להושיב את החברים כך שיש חילוף בין 1 ל-2. לכן

P(X12=1)=[(N-2)!]/N! EX=C(N,2)*P(X12=1)=[N!/(2!(N-2)!]*[(N-2)!]/N!=1/2​

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

1-exp(-0.5)=0.393​

 

[איליה.]

אבל כאשר N שואף לאינסוף...

ההסתברות שיהיה חילוף אחד לפחות צריכה לשאוף ל-1.

 

[jaXon]

דווקא לא

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

 

[איליה.]

יכול להיות שמספר החילופים הממוצע

הוא 0.393*N, אבל לא יכול להיות שההסתברות שיהיה חילוף היא כזאת! תחשבו בהגיון, זה חייב לשאוף ל-1 כאשר N שואף לאינסוף. מה הסיכוי שלא יהיה אף חילוף? שואף ל-0.

 

[איליה.]

הממ, סליחה, טעות שלי.

 

[jaXon]

מגניב!

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

 

[freedom rider]

אתה מכיר את החידה עם המעטפות?

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

 

[jaXon]

מכיר אבל לא בגרסה המקאברית ../images/Emo13.gif

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

 

[freedom rider]

כן, זה מאוד דומה

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

 

[freedom rider]

דרך אגב

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

והשיטה היא אותה שיטה שבה השתמשתי לשאלה שלך. גם את בבעיית ימי ההולדת אפשר לטפל בצורה כזו.