תודעה כוזבת

הרהורי זנב ארוך – שני כדורים, שק אחד: שלב ההוכחה

29 באוג', 2010

זנב ארוך, כריס אנדרסון, מתמטיקה, קליי שירקי

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

הוכחה 1 – אינדוקציה

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

נניח כי כבר הוכחנו את הטענה שלנו עבור שליפה של $n$ כדורים ונראה כי מהנחה זו נובע שההנחה תקפה גם עבור שליפה של $n+1$ כדורים.

תזכורת: הטענה היא כי לאחר שליפה של $n$ כדורים על-פי התהליך שתואר בפוסט הקודם, ההסתברות כי $k$ מהם הינם אדומים ו- $n-k$ מתוכם הינם כחולים היא בדיוק $\frac{1}{n+1}$ ללא תלות בערכו של $k$ .

תזכורת נוספת: בפוסט הקודם, הראינו במפורש כי התוצאה הזו נכונה עבור $n=1,2, 3$ כך שההנחה ממנה אנחנו יוצאים אינה בעייתית (למעשה לא היה צורך לעסוק כלל במקרים ה”מורכבים” יותר של $n=2, 3$ כדי שההוכחה באינדוקציה תעבוד, אבל תפקידם, החשוב, היה לשכנע אותנו שהתוצאה שהתקבלה היא אכן הגיונית).

נשאל את עצמנו, אם כן, מה היא ההסתברות לכך שלאחר שליפה של $n+1$ כדורים נקבל כי $k$ מתוכם הינם אדומים ו- $n+1-k$ מתוכם הינם כחולים. לצורך כך נסמן את ההסתברות כי $k$ כדורים מתוך $n$ שנשלפו הינם אדומים כ- $P_n(k)$ .

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

האפשרות שלאחר $n+1$ שליפות נקבל $n+1$ כדורים אדומים היא מכפלת ההסתברויות לקבל כדור אדום בכל אחת מהשליפות בהינתן שכל השליפות הקודמות הניבו כדור אדום. לאחר כל שליפה כזו גדל מספר הכדורים הכולל ב-1, וכך גם מספר הכדורים האדומים (כאשר בשליפה הראשונה יש שני כדורים ואחד מהם אדום). נקבל אם כך את התוצאה

$P_{n+1}(k=n+1)=\frac{1}{2}\times\frac{2}{3}\times\ldots\frac{k}{n+2}=\frac{1}{n+2}$ .

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

כעת נבחן את האפשרות המורכבת יותר של $k$ כדורים אדומים ו- $n+1-k$ כדורים כחולים. יש שתי אפשרויות לקבל תוצאה כזו וההסתברות לקבל אותה הוא סכומן של שתי ההסתברויות האלה. נבחן במפורש את שתי האפשרויות האלה, הראשונה היא ההסתברות לכך שלאחר $n$ שליפות קיבלנו $k$ כדורים אדומים, ובשליפה ה- $n+1$ קיבלנו כדור כחול. עבור השליפה האחרונה יש בשק $n+2$ כדורים, כאשר $k+1$ מהם הינם אדומים. כלומר

$P_1=P_n(k)\times\frac{n+2-k-1}{n+2}$ .

המקרה השני שיניב את אותה תוצאה הוא זה שבו לאחר השליפה ה- $n$ קיבלנו $k-1$ כדורים אדומים, ובשליפה ה- $n+1$ קיבלנו כדור אדום נוסף. במקרה זה בשליפה האחרונה שוב יש $n+2$ כדורים בשק, והפעם $k$ מתוכם הם אדומים. ההסתברות במקרה זה נתונה על-ידי

$P_2=P_n(k-1)\times\frac{k}{n+2}$ .

ההסתברות הכוללת, סכום שתי ההסתברויות האלה הינה.

$P_{n+1}(k)=P_1+P_2=P_n(k)\times\frac{n-k+1}{n+2}+P_n(k-1)\times\frac{k}{n+2}$ .

אולם הנחת האינדוקציה שלנו אומרת כי $P_n(k)=P_n(k-1)=\frac{1}{n+1}$ ולכן נקבל

$P_{n+1}(k)=\frac{1}{n+1}\times\frac{n-k+1+k}{n+2}=\frac{1}{n+2}$ .

וזו, בדיוק, התוצאה שאותה ביקשנו להוכיח.

מש"ל.

שתי הערות לסיום:

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

Get Shareaholic

פורסם על ידי שחר ביום יום ראשון, 29 באוגוסט, 2010 ובשעה 12:55 שייך לנושאים: זנב ארוך, כריס אנדרסון, מתמטיקה, קליי שירקי. ניתן לעקוב אחרי התגובות דרך RSS 2.0. ניתן להגיב, או לשלוח טרקבק מאתרך.

2 תגובות ל“הרהורי זנב ארוך – שני כדורים, שק אחד: שלב ההוכחה”

מאת itamar_b:
29 באוגוסט, 2010 בשעה 15:14

תקרא לי בפוסט הבא

[להגיב לתגובה זו]
מאת תודעה כוזבת » ארכיון הבלוג » הרהורי זנב ארוך – N כדורים, שק אחד:
3 בספטמבר, 2010 בשעה 13:26

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

הרהורי זנב ארוך – שני כדורים, שק אחד: שלב ההוכחה

2 תגובות ל“הרהורי זנב ארוך – שני כדורים, שק אחד: שלב ההוכחה”

השארת תגובה

עד לבית הלקוח

קבועים

תגובות אחרונות

ארכיון

ההם

קישורים