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

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

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

מה גדול כוחה, ונאמר ר'אמן.

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

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

נתחיל בלהגיד מה כן. כאשר יש לנו סדרה של \( 2n \) הטלות מטבע (מטבע הוגן, כלומר הסתברות 50-50 לקבלת עץ או פלי), התוחלת של מספר ההטלות שיצאו עץ היא \( n \). בדיוק \( n \). אבל מה זה אומר, בעצם? תוחלת היא בסך הכל ממוצע משוקלל - אנחנו כופלים 1 בהסתברות שבסדרה של \( 2n \) הטלות מטבע יצא עץ בדיוק פעם אחת, מחברים לזה את 2 כפול ההסתברות שיצא עץ פעמיים, מחברים לזה את 3 כפול ההסתברות שיצא עץ שלוש פעמים, וכן הלאה. לא קשה לראות כאן משיקולי סימטריה שהתוחלת חייבת לצאת \( n \) (כי סכום תוחלת מספר ההטלות שבהן יוצא עץ עם תוחלת מספר ההטלות שבהן יוצא פלי צריכה לצאת שווה לסכום ההטלות הכולל). עם זאת, זה לא אומר שכאשר נטיל מטבע \( 2n \) פעמים, יצא לנו עץ בדיוק \( n \) פעמים!

אחד מהמשפטים שמאפשר לנו להשתמש בתוחלת כדי לומר משהו מהותי על הבעיה ההסתברותית שלנו הוא חוק המספרים הגדולים, שבגרסה החזקה יותר שלו, כשהיא מותאמת לסיטואציה הספציפית שלנו, אומר שהמספר הממוצע של ההטלות שנפלו על עץ (כלומר, מספר ההטלות שיצאו עץ חלקי מספר ההטלות הקודם) שואף לתוחלת של עץ בהטלה בודדת (שהיא \( \frac{1}{2} \)) בהסתברות 1. במילים אחרות, כמעט בכל סדרת הטלות אפשרית, ככל ש-\( n \) גדול יותר, כך כמות הפעמים שיצא “עץ” בסדרה של \( 2n \) ההטלות תהיה קרובה יותר ל-\( n \), אבל צריך להיות זהירים עם ה”קרוב יותר” הזה. אם יש 10 הטלות ומתוכן 4 יצאו עץ, האם זה טוב יותר או פחות מאשר 100 הטלות שמתוכן 48 יצאו עץ? מצד אחד, במקרה הראשון ציפינו לקבל 5 עצים וההפרש בין 4 ו-5 הוא 1, ולעומת זאת במקרה השני ההפרש בין 48 ו-50 הוא 2, כך שהמקרה השני “פחות טוב”; ומצד שני, במקרה הראשון המספר הממוצע של הטלות שנפלו על עץ הוא \( \frac{4}{10}=\frac{2}{5} \) בעוד שבמקרה השני הוא \( \frac{48}{100}=\frac{12}{25} \), וזה מספר קרוב יותר ל-\( \frac{1}{2} \) מאשר \( \frac{2}{5} \). חוק המספרים הגדולים מתייחס למקרה השני כטוב יותר מהראשון; זו משמעות “השאיפה”.

אם כן, חוק המספרים הגדולים אומר שאם נבצע \( 2n \) הגרלות ונחלק את מספר העצים שקיבלנו ב-\( 2n \), נקבל משהו קרוב לחצי, וככל ש-\( n \) יהיה יותר גדול כך רמת הקרבה הזו תגדל עוד יותר. אתם מוזמנים לנסות את זה בעצמכם בסימולציות מחשב ולהיווכח (באופן אמפירי!) שהמתמטיקה עובדת. עבור \( n \) גדול מספיק ייתכן אפילו שהמספר הממוצע שתקבלו יחרוג מרמת הדיוק שלכם ולכן ייראה לכם בדיוק כמו \( \frac{1}{2} \) (חשבו על \( 0.50000000000000001 \) כאשר המחשב שלכם לא מציג את חמש הספרות האחרונות). זה עדיין לא אומר שתקבלו בדיוק חצי, אבל שתקבלו משהו באיזור חצי, וככל ש-\( n \) יותר גדול, כך האיזור הזה יכול להיות יותר גדול.

אם כן, תשכחו מתוחלת. תשכחו מחוק המספרים הגדולים. בואו נדבר על חישוב פרקטי. נתון \( n \); מה ההסתברות שבסדרה של \( 2n \) הטלות מטבע נקבל עץ בדיוק \( n \) פעמים?

זו דוגמה למשתנה מקרי בינומי שכבר הזכרתי בבלוג בעבר. החישוב הוא פשוט למדי: בגלל שההסתברות לעץ היא \( \frac{1}{2} \), וגם ההסתברות לפלי היא \( \frac{1}{2} \), אז לכל סדרה שהיא של עץ ופלי, ההסתברות שתתקבל בדיוק הסדרה הזו היא \( \frac{1}{2^{2n}} \) (\( \frac{1}{2} \) עבור הסיכוי לקבל בהטלה הראשונה את האיבר הראשון בסדרה, כפול \( \frac{1}{2} \) עבור הסיכוי לקבל בהטלה השניה את האיבר השני בסדרה וכן הלאה). נשאלת רק השאלה - כמה סדרות מאורך \( 2n \) שכוללת בדיוק \( n \) פעמים עץ קיימות? גם זה קל: אנחנו צריכים לבחור \( n \) מקומות עבור עץ, ולכן התוצאה היא \( {2n \choose n} \) (מי שלא מכיר את הסימונים הללו מוזמן לקרוא את הבלוג על משתנים בינומיים, או את הפוסטים שלי על קומבינטוריקה). שימו לב ש-\( {2n \choose n} \) הוא מקדם הבינום הגדול ביותר מבין כל אלו שיש להם \( 2n \) למעלה, כך שההסתברות לקבל \( n \) פעמים עץ היא אכן הגדולה מכל ההסתברויות לקבל מספר ספציפי של פעמים עץ; עם זאת, זה עדיין לא אומר שהיא גדולה בפני עצמה, רק שהיא גדולה מכל היתר (והמספר של “היתר” הולך וגדל).

אם כן, ההסתברות היא \( {2n \choose n}2^{-2n} \). האם זו הסתברות קטנה? גדולה? מה קורה כש-\( n \) שואף לאינסוף, האם ההסתברות שואפת ל-1? ל-0? ל-\( \frac{37}{100} \)? לא ברור איך בדיוק לתקוף את הבעיה הזו במפורש כי אין לנו נוסחה מפורשת נחמדה ל-\( {2n \choose n} \). מה שאנחנו כן יכולים לעשות הוא ללכת על פי ההגדרה של הסימון של מקדמי הבינום, \( {2n \choose n}=\frac{\left(2n\right)!}{\left(n!\right)^{2}} \), אבל איך מתקדמים מכאן? אין לנו נוסחה סגורה יפה עבור עצרת…

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

\( n!\approx\sqrt{2\pi n}\left(\frac{n}{e}\right)^{n} \)

מה \( \approx \) אומר? פורמלית, שאם נחלק את שני הביטויים הללו ונשאיף את \( n \) לאינסוף, נקבל 1, כלומר \( \lim_{n\to\infty}\frac{n!}{\sqrt{2\pi n}\left(\frac{n}{e}\right)^{n}}=1 \). איך לעזאזל מוכיחים דבר כזה, ועוד יותר לעזאזל מאיפה \( \pi \) החליט לדחוף את עצמו לעניין - זה דורש עבודה כלשהי; אני לא מכיר הוכחה לנוסחה שהיא גם אלמנטרית (לא משתמשת בידע מתמטי קודם שהוא לא טריוויאלי) וגם פשוטה. אני מקווה בעתיד להראות הוכחה בבלוג, ובינתיים בואו נראה מה זה אומר על הבעיה שלנו.

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

\( {2n \choose n}=\frac{\left(2n\right)!}{\left(n!\right)^{2}}\approx\frac{\sqrt{2\pi2n}\left(2n/e\right)^{2n}}{\sqrt{\left(2\pi n\right)^{2}}\left(n/e\right)^{2n}}=\frac{2\sqrt{\pi n}}{2\pi n}\cdot\frac{2^{2n}\cdot n^{2n}}{n^{2n}}=\frac{2^{2n}}{\sqrt{\pi n}} \)

אני מקווה שהמעברים לא היו מהירים יותר מדי, אבל באמת שאין כאן שום דבר מלבד חשבון סטנדרטי. המסקנה? \( {2n \choose n}2^{-2n}\approx\frac{1}{\sqrt{\pi n}} \). בפרט, מכיוון ש-\( \lim_{n\to\infty}\frac{1}{\sqrt{\pi n}}=0 \) זה אומר ש-\( \lim_{n\to\infty}{2n \choose n}2^{-2n}=0 \), כלומר אפשר לשכוח מכך שנתקבע על סיכוי של 37 אחוז לקבל חצי-חצי; ככל ש-\( n \) גדול יותר, כך הסיכוי שלנו לקבל חצי-חצי ילך ויתקרב לאפס. אמנם, הקצב שבו זה קורה הוא יחסית איטי (כי \( \sqrt{n} \) היא פונקציה שגדלה די לאט), אבל השורה התחתונה נותרת בעינה - באופן שהוא אולי קצת לא מתאים לאינטואיציה, ככל ש-\( n \) גדול יותר, ההסתברות קטנה יותר (למרות שהממוצע יהיה קרוב יותר לחצי).

מה המסקנה מכל זה? שמפלצת הספגטי המעופפת קיימת? שהיא לא קיימת? שצריך להיזהר גם עם טענות מתמטיות שנשמעות טוב אינטואיטיבית? אני אישית הולך עם “סטירלינג זה מגניב!”