מי מפחד מ-n עצרת?

(גרסת תרגיל לחלק מהפוסט הזה תוכלו למצוא במסמך ה-PDF הזה.)

1. הקדמה

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

n! \sim (\frac{n}{e})^{n}\sqrt{2\pi n}

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

התוצאה הזו נקראת 'קירוב סטירלינג' (Stirling's approximation), על שמו של מתמטיקאי סקוטי שהוכיח את התוצאה ב-1730 בספרו המשפיע "Methodus differentialis" (אומנם כתוב בלטינית, אבל יש שמועות שבעמוד 135 תוכלו למצוא את המשפט). למעשה הוא רק מצא את הקבוע \sqrt{2\pi}; היה זה דה מואבר הצרפתי (שהיה מבוגר ב-25 שנים מחברו סטירלינג) שהראה ש-n!\sim C(\frac{n}{e})^{n}\sqrt{n} עבור איזשהו קבוע C . דה מואבר היה צריך את הקירוב הזה כשחקר את תורת ההסתברות, שהייתה בחיתוליה באותה תקופה (דה מואבר הוא אחד מאבות תורת ההסתברות). ניתן דוגמאות לקשר בין הסתברות וקירוב סטירלינג.

חלק מהדברים המפתיעים בקירוב הם ההופעה של e ו-\pi בהקשר שהוא (כביכול) קומבינטורי ודיסקרטי במהותו – בפונקציית העצרת נתקלים לראשונה בלימודי קומבינטוריקה וסטטיסטיקה – n! היא כמות התמורות (פרמוטציות) על n איברים. במאמר זה נראה איך מגיעים לקירוב זה (נעשה זאת בשלבים) ובין השאר נראה שהופעתם של e ו-\pi היא תופעה שכיחה בקירובים של ביטוים קומבינטוריים.

לרוב נוהגים להשתמש בתואר הראשון בתוצאה זו ללא הוכחה, לדוגמא: בקורס בסיסי באלגוריתמים מראים שתחת הנחות מסויימות, אלגוריתם מיון של n מספרים דורש לפחות \log_{2}(n!) פעולות. נשאלת השאלה, מה הוא סדר הגודל הזה במונחים מוכרים? מנוסחת סטירלינג מקבלים ש-\log_{2}(n!)=n\log_{2}(n/e)+\frac{1}{2}\log_{2}(2\pi n)=\theta(n\ln n), ואפשר להשיג חסם תחתון זה באמצעות, לדוגמא, מיון מיזוג (merge sort). זו דוגמה לא מוצלחת, כי אפשר להראות ש-\ln(n!)=\theta(n\ln n) בקלות בלי קירוב סטירלינג, וגם נעשה זאת. אל דאגה – נציג גם דוגמאות בהן נעשה שימוש בכל חוזק הקירוב.

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

\ln n!=n\ln(n)-n+\frac{\ln n}{2}+\frac{\ln2\pi}{2}+o(1)

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

• אנחנו מכירים משפטים ותוצאות על סכומים. יש לנו אינטואיציה לסכומים, ופחות למכפלות.

• בהרבה מקרים, כולל המקרה הזה, סכומים אפשר לקרב ע"י אינטגרלים.

• במקרה הספציפי שלנו, e נעלם – זה מראה שהצורת הסכום של הקירוב היא טבעית יותר, וה-e נוצר כשהופכים את הסכום חזרה למכפלה.

n! גדל בצורה ממש מהירה שקצת קשה לתפוס. הסכום הנ"ל מודד את הקצב הזה במונחים קצת יותר ברורים, מונחים של ספרות – \ln n! שווה (אחרי עיגול) לכמות הספרות שיש ל-n! בבסיס e . בגלל שלא ברור מה זה בדיוק בסיס e, אפשר לחלק את התוצאה ב-\ln 10 ולקבל לוג בבסיס 10. זה נותן עוד פירוש  לקירוב סטירלינג: כמות הספרות ב-n! בבסיס 10 שווה ל-1+\lfloor\frac{(n+\frac{1}{2})\ln n-n+\ln\sqrt{2\pi}}{\ln10}\rfloor, עד כדי שגיאה שדועכת באינסוף.

מהלך העניינים יהיה כזה:

• נפתח בקירוב הפשוט \ln(n!)=\theta(n\ln n),

• אח"כ נתקדם ל-\ln(n!)=n\ln n+O(n),

• ומשם ל-\ln(n!)=n\ln n-n+O(\ln n).

זה לא הכל. אח"כ נדון בשיקולים הסתברותיים (ריגורוזים יותר ופחות) לכך שהשגיאה O(\ln n) חייבת להיות למעשה \frac{\ln n}{2}+O(1), ואף נסביר את מקור הקבוע \sqrt{2\pi}.

לאחר מכן ננקוט בגישה אינטגרלית שתפתור את הבעיה במלואה, שמקורה מאנליזה נומרית. בין השאר נדבר על אינטגרציה נומרית ועל נוסחה כללית על שם אוילר ומקלורן שמוצא את השגיאה המדויקת בבעיות קירוב מסוג \sum_{i=1}^{n}f(i)\approx \int f(t) dt.

נמשיך בפיתרון נוסף שקשור לאינטגרל. ספציפית, נשתמש בפונקציית גמא (שבין השאר מכלילה את העצרת גם לערכים לא טבעיים) כדי להציג את n! בתור אינטגרל מהצורה \int e^{nf(t)} dt, כפול ביטוי עם התנהגות פשוטה. עם האינטגרל נתמודד בעזרת שיטת לפלס.

לסיום נשתכלל ונחשב אינטגרלים מרוכבים. נמציא שיטה כללית, שיטת Hayman, שמאפשרת לחלץ מידע אסימפטוטי על סדרה מתוך הפונקציה יוצרת שלה. השיטה הזו היא כלי אדיר שמבוסס על שיטת לפלס, וניתן כמה דוגמאות נוספות לשימושיה. כדי להבין את n! מפעילים אותה על e^x=\sum \frac{x^n}{n!}.

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

2. צעדי תינוק

1. חסם עליון

כאמור, לא נקפוץ ישר לקירוב הסופי. נתחיל בגישושים, כדי לקבל איזושהי אינטואיציה.
ראשית, מההגדרה, n! היא מכפלה של n גורמים שכל אחד מהם הוא לכל היותר n, כלומר n! \le n^n.

2. חסם תחתון באינדוקציה

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

n! \ge (\frac{n}{2})^{\frac{n}{2}-1}

אם ניקח לוגריתם של 2 האי-שיוויונות שלנו בינתיים, נקבל:

n \ln n \ge \ln (n!) > (\frac{n}{2}-1) \ln(\frac{n}{2})

שילוב שני האגפים מראה ש-\ln n!=\theta(n\ln n). אנחנו מתקרבים להבנת האיבר העיקרי בקירוב, שהוא n\ln n. בדרך הנוכחית, אם נחליף את \frac{1}{2} בקבוע אחר (נגיד, נזרוק שליש מהאיברים, או רבע, וכו'), אפשר לקבל \ln n!\ge(1-c)n\ln n+O(n) כאשר c>0 קרוב לאפס כרצוננו. זה נחמד, אבל לא מספיק טוב כדי להראות ש-\ln n!-n\ln n=o(n\ln n).

ננסה להשתמש באינדוקציה – נסתכל על המנה של n! ב-(\lfloor \frac{n}{2} \rfloor)! (למעשה, על הלוג שלה):

\ln(n!)-\ln(\lfloor\frac{n}{2}\rfloor!) = \ln(\prod_{i>\lfloor\frac{n}{2}\rfloor}^{n}i)

את \lceil\frac{n}{2}\rceil המספרים שמוכפלים באגף ימין אפשר לזווג – להכפיל את הראשון באחרון, השני בלפני אחרון, השלישי בשלישי מהסוף, וכו'. כל זוג נותן מכפלה של לפחות \frac{n^{2}}{2} (ודאו שאכן כך), וכך נקבל:

\ln(\prod_{i>\lfloor\frac{n}{2}\rfloor}^{n}i)\ge(\frac{n}{4}-1)\ln(\frac{n^{2}}{2})\ge\frac{n}{2}\ln n+O(n)

ולכן \ln(n!)\ge\ln(\lfloor\frac{n}{2}\rfloor!)+\frac{n}{2}\ln n+O(n)ואי-שיוויון זה מאפשר להוכיח באינדוקציה ש-\ln(n!)\ge n\ln n+O(n) – אתן לכם להשלים את הפרטים.

דרך אינקוטיבית נוספת, ואולי טבעית יותר, תוצג בתרגילים.

3. חסם תחתון עם טורים

הטריק המעניין הבא נותן את אותה התוצאה בדרך אחרת לחלוטין. ניזכר בטור של האקספוננט: e^{x}=\sum_{k\ge0}\frac{x^{k}}{k!}. בפרט, עבור x חיובי מקבלים e^{x}>\frac{x^{k}}{k!} לכל k\ge 0.
נציב x=k=n ונקבל e^{n}>\frac{n^{n}}{n!}, כלומר n!>(\frac{n}{e})^{n}, ובכתיב לוגריתמי: \ln n!>n\ln n-n.

הערה 1: אפשר לשפר זאת טיפה – נשים לב שלמעשה e^{x}>\frac{x^{n}}{n!}+\frac{x^{n-1}}{(n-1)!}. אם מציבים x=n מקבלים e^{n}>2\frac{n^{n}}{n!}\implies n!>2(\frac{n}{e})^{n}.
קשה לקבל משהו טוב יותר, כי האיברים המקסימליים בסדרה \{\frac{n^{k}}{k!}\}_{k\ge0} נמצאים ב-k=n,n-1 (כדי לוודא זאת, נסמן f(k)=\frac{n^{k}}{k!} על הקבוצה \mathbb{N}_{0} ונחקור את המנה של 2 ערכים עוקבים, \frac{f(k+1)}{f(k)}=\frac{n}{k+1}). בתרגיל 1 נשפר זאת עוד, משמעותית.

הערה 2: אם אתם לא מאמינים בטורי חזקות, תצטרכו להשתמש באינדוקציה כדי לקבל את הגרירה x>0 \implies e^{x}>\frac{x^{n}}{n!}, באופן הבא:
נסמן f_n(x) = e^x - \frac{x^n}{n!}. המקרה n=0 מיידי כי e^x > e^0 = 1.
במעבר מ-n ל-n+1 נשים לב ש-(f_{n+1})' = f_n, ומהנחת האינדוקציה נקבל ש-f_{n+1} עולה בחצי החיובי של ציר x. בגלל ש-f_{n+1}(0)=1-0>0, נובע ש-f_{n+1} חיובית עבור x>0.

4. סיכום הידע עד כה

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

\ln n! = n\ln n+O(n)

ובכתיב כפלי: n!=n^{n}e^{O(n)}. כלומר השלמנו את הקירוב עד כדי פקטור מעריכי. יאי!

5. תרגילים

תרגיל 1 (הוכחה אינדוקטיבית שונה – בסגנון Merge Sort)

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

א. הראו שההפרש \ln n! - 2\ln (\frac{n}{2})! שווה \ln \binom{n}{n/2}.

ב. הראו ש-\binom{n}{n/2} הוא האיבר הגדול ביותר בשורה ה-n של משולש פסקל, ולכן הוא לפחות \frac{2^n}{n+1}.

ג. הסיקו \ln n! - 2\ln (\frac{n}{2})! \ge n\ln 2 + O(\ln n).

ד. הראו, באינדוקציה או עם משפט המאסטר, ש-\ln n!-2 \ln (\frac{n}{2})! = n + O(\ln n) גורר \ln n! \ge n\ln n + O(n).

הערה 3: יתכן וכבר ראיתם דבר כזה – בחישוב הסיבוכיות של Merge Sort מגיעים לאותה נוסחת נסיגה.

תרגיל 2 (שיפור לחסם התחתון באמצעות טורים)

א. הראו ש-e^{x}>\sum_{i=0}^{n}\frac{x^{i}}{i!} לכל x חיובי. הציבו x=n וקבלו n!>(\frac{n}{e})^{n}\sum_{k=1}^{n}\prod_{i=0}^{k-1}(1-\frac{i}{n}). נוותר על חלק מהאיברים בסכום כי רובם זניחים, ספציפית על אלו שמתאימים ל-k>\sqrt{n}+1.

ב. לאחר שזרקנו חלק מהאיברים, בואו נסתכל על האיבר האחרון שנותר בסכום: \prod_{i=0}^{\lfloor \sqrt{n} \rfloor}(1-\frac{i}{n}). הוא האיבר הקטן ביותר (כל איבר קטן מקודמו). הראו שהוא חסום מלמטה ע"י (1-\frac{1}{\sqrt{n}})^{\sqrt{n}}, ביטוי ששואף ל-e^{-1} (מהגדרת e), ובפרט חסום מלמטה ע"י קבוע אבסולוטי C. (קרדיט לתום.)

הערה 4: המשמעות הקומבינטורית של הסעיף הזה היא שהקירוב הגס \binom{n}{k}\approx \frac{n^{k}}{k!} הוא סבבה עבור k=O(\sqrt{n}):

 1 \ge \binom{n}{k}/\frac{n^{k}}{k!}=\prod_{i=0}^{k}(1-\frac{i}{n})\ge(1-\frac{1}{O(\sqrt{n})})^{O(\sqrt{n})} \to e^{-1}

הערה 5: אפשר לשפר את הקבוע e^{-1} אם לוקחים לוגריתם של המכפלה ומשתמשים בקירוב טיילור מסדר שני של \ln(1-x) סביב x=0. הוא יוצא באיזור e^{-0.5}.

ג. הראו ש-n!>C(\frac{n}{e})^{n}\sqrt{n} , או: \ln n!>n\ln n-n+\frac{\ln n}{2}+O(1).

ד. אתגר: הראו ש-\sum_{k=1}^{n}\prod_{i=0}^{k-1}(1-\frac{i}{n}) אסימפטוטי ל-\sqrt{n\pi/2}.

3. אינטגרציה נומרית, ניסיון ראשון

1. ניסוח מחדש של הבעיה

נמשיך. הקירוב המלא הוא \ln n!=n\ln n-n+\frac{\ln n}{2}+\frac{\ln(2\pi)}{2}+o(1), אז עכשיו הגיע תורו של המחובר -n, כלומר צריך להבין למה השגיאה O(n) היא בעצם -n+O(\ln n).

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

\sum_{i=1}^{n}\ln i = n\ln n-n+\frac{\ln n}{2}+\frac{\ln2\pi}{2}+o(1)

הבעיה של קירוב סכומים מהצורה \sum_{i=1}^{n}f(i) כאשר f פונקציה גזירה "מספיק פעמים" נחקרה לא מעט, ויש לה פיתרון כללי ומדויק שנדבר עליו מאוחר יותר. בגדול, ננסה להחליף את הסכום באינטגרל.

2. דוגמת הטור ההרמוני, וכלל המלבן

נציג דוגמא שרואים בחדו"א, והיא קירוב המספר ההרמוני ה-n-י: H_{n}=\sum_{i=1}^{n}\frac{1}{i}. ידוע שהטור \lim_{n\to\infty}H_{n} מתבדר וש-H_{n} "מתנהג" כמו \ln n. לרוב מראים זאת כך:

H_{n} = 1+\sum_{k=2}^{n}\frac{1}{k} \approx 1+\int_{1}^{n}\frac{dx}{x} = 1+\ln n-\ln1 = \ln n+1

כאשר נעשה שימוש בקירוב הכללי f(i)\approx \int_{i-1}^{i}f(x)dx. גיאומטרית, זה נראה כמו בגרף המצורף.

600px-RightRiemann2.svg

כלל המלבן – קירוב אינטגרל ע"י מלבנים שגובהם נקבע ע"י ערך הפונקציה בקצה הקטע. במקרה זה, הקצה הימני.

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

3. השגיאה במקרה של הטור ההרמוני

נשאלת השאלה: מה השגיאה, כלומר כמה טוב הקירוב \frac{1}{n}\approx \int_{n-1}^{n}\frac{dx}{x}?
כדי להעריך את השגיאה, נשתמש במונוטוניות \frac{1}{x}:

\frac{1}{n-1}\ge\int_{n-1}^{n}\frac{dx}{x}\ge\frac{1}{n} \implies

\frac{1}{n-1} - \frac{1}{n} \ge\int_{n-1}^{n}\frac{dx}{x} - \frac{1}{n} \ge 0

זה מראה שהשגיאה בקירוב H_n נמצאת בין 0 ל-\sum_{i=2}^{n}(\frac{1}{i}-\frac{1}{i-1})=\frac{1}{n}-1, ומקבלים:

\ln n+\frac{1}{n}\le H_{n}\le\ln n+1

4. המקרה שלנו – כלל המלבן עבור הלוגריתם הטבעי

בדומה, אפשר לעשות אותו דבר עבור \sum_{i=1}^{n}\ln i:

\ln(n!) = \ln1+\sum_{i=2}^{n}\ln i = \sum_{i=2}^{n}\ln i \approx \int_{1}^{n}\ln x dx

נשתמש בכך ש-\int\ln x dx=x\ln x-x (עובדה שמתגלה ע"י אינטגרציה בחלקים), ואז:

\ln(n!) \approx (x \ln x -x )|_{x=1}^{x=n} = n\ln n - n-(1\ln1 -1) = n\ln n-n+1

וקיבלנו כמו שרצינו את הגורם הנחשק -n, אם כי צריך עדיין להראות שהשגיאה היא o(n).
נשים לב שמהמונוטוניות של \ln n מקבלים \ln i\ge\int_{i-1}^{i}\ln xdx\ge\ln(i-1), כלומר השגיאה \sum_{i=2}^{n}\ln i-\int_{1}^{n}\ln xdx חסומה בין 0 ל-\sum_{i=2}^{n}(\ln i-\ln(i-1))=\ln n, ז"א:

n\ln n-n+1+\ln n\ge\ln n! \ge n\ln n-n+1

ובאופן יותר תמציתי:

\ln n! = n\ln n-n+O(\ln n)

יש!

מסקנת ביניים היא שהגורם (\frac{n}{e})^{n} בקירוב סטירלינג נובע מהאינטגרל של \ln x בין 1 ל-n\ln\sqrt{2\pi n}+o(1) תצא השגיאה בין האינטגרל לסכום.

5. המקרה הכללי של כלל המלבן

באופן כללי, אם f מונוטונית ורציפה עם פונקציה קדומה F, אז מקבלים מכלל המלבן את הקירוב הבא:

\sum_{i=1}^{n}f(i)=F(n)+O(\max\{1,f(n)\})

זה קירוב גרוע ואפשר לשפרו רבות – וכך נעשה בפרק 5.

6.ניסוח שונה של התוצאה

את הקירוב האחרון שהשגנו, \ln n! = n\ln n-n+O(\ln n), אפשר להוכיח בדרך שונה שמחביאה את הגיאומטריה אבל היא כיפית. ננסח אותו בתור e(\frac{n}{e})^{n} \le n!\le en(\frac{n}{e})^{n}.

נניח את אי-שיוויון העזר הבא שחוסם את הקבוע e, ובהמשך נסבירו:

(1+\frac{1}{n})^{n}<e<(1+\frac{1}{n})^{n+1}

אפשר להוכיח ממנו באינדוקציה ישירה את הקירוב שמצאנו ל-n!. עבור n=1 זה שקול ל-1\le 1 \le 1. במעבר האינדוקציה, צריך להראות ש:

\frac{(n+1/e)^{n+1}}{(n/e)^{n}} \le \frac{(n+1)!}{n!}\le\frac{n+1}{n}\frac{((n+1)/e)^{n+1}}{(n/e)^{n}}

מה שהופך ל-(1+\frac{1}{n})^{n}\le e\le(1+\frac{1}{n})^{n+1} לאחר העברת אגפים מתאימה, וזה אי-שיוויון העזר. \blacksquare

עכשיו ההסבר לאי-שיוויון העזר. אני טוען שבהוכחה הזו, בעצם, אין דבר חדש: במעבר האינדוקציה, אנחנו משתמשים באי-שיוויון \frac{(n+1)^{n+1}}{n^{n}e} < n+1 < \frac{(n+1)^{n+2}}{en^{n+1}}, ששקול לאי-שיוויון העזר אחרי העברת אגפים. הפעלת לוגריתם מראה שזה בעצם \ln n < \int_{n}^{n+1}\ln xdx\ <\ln(n+1)האי-שיוויון הבסיסי שהשתמשנו בו בכלל המלבן עבור פונקציה מונוטונית עולה.

בכל אופן, נראה איך מגיעים לאי-שיוויון העזר בדרך מעט שונה. ההגדרה של e היא הגבול \lim_{n\to\infty}(1+\frac{1}{n})^{n}. לכן 2 הביטוים (1+\frac{1}{n})^{n},(1+\frac{1}{n})^{n+1}  שואפים ל-e. מסתבר שהסדרה (1+\frac{1}{n})^{n} עולה ל-e (מה שמסביר את אגף שמאל של האי-שיוויון) ושהסדרה (1+\frac{1}{n})^{n+1} יורדת אליו (מה שמסביר את אגף ימין).
ההוכחה לכך ישירה, ונדגים אותה על הסדרה העולה. נפתח את (1+\frac{1}{n})^{n}<(1+\frac{1}{n+1})^{n+1} עם הבינום של ניוטון ואז מספיק להשוות איבר-איבר:

\binom{n}{k}n^{-k}<\binom{n+1}{k}(n+1)^{-k}

כלומר:

\prod_{i=1}^{k-1}(1-\frac{i}{n})<\prod_{i=1}^{k-1}(1-\frac{i}{n+1})

וזה אי-שיוויון טריוויאלי. (המונוטוניות של (1+\frac{1}{n})^{n+1} מתקבלת באופן דומה.)

7. תרגילים

תרגיל 1 (פוטנאם 1996, שאלה B2)

הראו שלכל n שלם חיובי מתקיים:

(\frac{2n-1}{e})^{\frac{2n-1}{2}}<1\cdot3\cdot5\cdot\cdots\cdot(2n-1)<(\frac{2n+1}{e})^{\frac{2n+1}{2}}

4. (מתקדם – רשות) דוגמאות מעולם ההילוכים המקריים ו"הוכחה"

1. מבוא מהיר להילוכים מקריים

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

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

הדוגמא הסטנדרטית היא הילוך שיכור על ציר המספרים השלמים \mathbb{Z}: השיכור מתחיל בנקודה 0, וכל דקה מחליט באקראי ובאופן בלתי תלוי בהחלטותיו הקודמות האם ללכת ימינה צעד אחד (מ-n ל-n-1) או שמאלה (ל-n+1).

הכללה היא טבעית היא הסריג ה-d-מימדי, \mathbb{Z}^{d} – השיכור מתחיל בראשית \vec{0}, וכל דקה הולך באחד מ-2d הכיוונים \pm e_{i}=(0,\cdots,0,\underbrace{\pm1}_{i},0,\cdots,0),1\le i\le d באקראי – כל אחד בהסתברות שווה של \frac{1}{2d}, כיאה לשיכור הוגן.

פורמלית אפשר לכתוב זאת כך: \{S_{n}\}_{n\ge0} היא סדרה של משתנים מקריים שמייצגים את מיקום השיכור בדקה ה-n. מתקיים S_{0}=\vec{0},S_{n+1}=S_{n}+X_{n+1} כאשר \{X_{n}\}_{n\ge0} היא סדרה של משתנים מקריים בת"ל שווי התפלגות שמקבלים את 2d הכיוונים השונים בהסתברות אחידה.

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

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

משפט פוליה: הילוך שיכור על \mathbb{Z}^{d} יחזור לראשית בהסתברות 1 אמ"מ d=1 או d=2.

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

ממשפט פוליה אפשר להסיק עוד לא מעט, כפי שמראה הטענה הבאה:

טענה: יהי S_{n} הילוך מקרי על גרף קשיר לא-מכוון G שמתחיל בנקודה 0 שתיקרא הראשית. אזי שלושת התנאים הבאים שקולים:

• P(\exists n\ge1:S_{n}=0)=1 (ההילוך בהכרח חוזר מתישהו לראשית)

• P(S_{n}=0\text{ for infinitely many }n)=1 (ההילוך בהכרח חוזר אינסוף פעמים לראשית)

• E\#\text{\{Number of visits to }\vec{0}\}=\sum_{n\ge1}P(S_{n}=0)=\infty (תוחלת מספר החזרות של ההילוך לראשית היא אינסופית)

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

השקילות בין התנאי הראשון לתנאי השלישי גם מנצלת את אותו חוסר זיכרון: נסמן ב-p את הסתברות החזרה לראשית. מספר החזרות לראשית הוא משתנה גיאומטרי \text{Geo}(1-p) – ההסתברות לחזור לראשית k פעמים בדיוק היא p^k(1-p). התוחלת שלו היא \frac{1}{1-p}, כלומר היא מתבדרת אמ"מ p=1\blacksquare

ההילוך נקרא "נשנה" אם השיכור מצופה לחזור לנקודת ההתחלה אינסוף פעמים במהלך מסעו האינסופי. אחרת הוא נקרא "חולף". מהטענה וממשפט פוליה, מקבלים שהילוכים על \mathbb{Z}, \mathbb{Z}^{2} הם נשנים (הילוכים חד-מימדיים ודו-מימדיים), והילוכים ממימד גבוה יותר הם חולפים.

2. דוגמא א' – הילוך שיכור חד-מימדי

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

מה ההסתברות שהילוך שיכור חד-מימדי יחזור לאפס אחרי n צעדים? נסמן ב-S_n את המיקום שלו אחרי n צעדים. ל-S_{n} ול-n אותה זוגיות, לכן S_{n} יכול להתאפס רק בזמנים זוגיים.
כדי שהוא יחזור לאפס אחרי 2n צעדים, צריך שחצי מהצעדים יהיו ימינה וחצי שמאלה. סה"כ יש \binom{2n}{n} אפשרויות לכך וכל אחת קורה בהסתברות שווה של 2^{-2n}, ולכן:

 P(S_{2n}=0)=2^{-2n}\binom{2n}{n}

נשתמש בקירוב סטרילינג כדי להבין הסתברות זו, אבל נציג את הקירוב בצורה קצת אחרת, והיא: n!\sim (\frac{n}{e})^{n}f(n), כאשר f(n)=\sqrt{2\pi n} (נשתמש בהצגה זו גם בהמשך). השורה התחתונה של הפרק הקודם הייתה: e \le f(n) \le n.

ההסתברות נהיית:

\begin{array}{lcl} 2^{-2n}\binom{2n}{n} &=& 2^{-2n}\frac{(2n)!}{n!^{2}} \\  &\sim& 2^{-2n}(\frac{2n}{e})^{2n}(\frac{e}{n})^{2n}\frac{f(2n)}{f(n)^{2}} \\  &\sim& \frac{f(2n)}{f(n)^{2}} \end{array}

אנחנו יודעים ממשפט פוליה שההילוך נשנה. האם נוכל להוכיח זאת?
זה שקול לכך שהטור \sum_{n\ge 0}P(S_{2n}=0) מתבדר, מה ששקול להתבדרות של \sum_{n \ge 1} \frac{f(2n)}{f(n)^2} ממבחן ההשוואה.

נניח בשביל הדוגמא הזו, ובשביל הדוגמאות הבאות, ש-f(n) = C \cdot n^{\alpha} (אף שלא הוכחנו זאת), אז האיבר הכללי בטור הנ"ל פרופורציוני ל-n^{-\alpha}, ולכן התבדרות שקולה ל-\alpha\le1.
בגלל שהוכחנו כבר e \le f(n) \le n, אפשר להניח 0 \le \alpha \le 1, מה שמוכיח את משפט פוליה במקרה החד-מימדי!
(השקר הוא כאמור ההנחה f(n) = C \cdot n^{\alpha}, שלא הצדקנו.)

בהינתן קירוב סטירלינג, f(n)=\sqrt{2\pi n}, כלומר \alpha=0.5, ובפרט הטור שאיברו הכללי P(S_{2n}=0)\approx \frac{1}{\sqrt{\pi n}} אכן מתבדר. למעשה, הוכחנו את משפט פוליה במקרה החד-מימדי בהינתן קירוב סטירלינג!

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

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

3. דוגמא ב' – הילוך שיכור דו-מימדי

נסמן ב-S_{n,2} את המיקום של הילוך שיכור דו-מימדי לאחר n צעדים. אם נסובב את \mathbb{Z}^{2} ב-45^{\circ} מעלות, אפשר להיווכח שהילוך שיכור זה שקול לשני הילוכים שיכורים חד-מימדיים בלתי תלויים, פשוט ע"י הטלת ההילוך לציר x ולציר y. בפרט, P(S_{2n,2}=\vec{0})=P(S_{2n}=0)^{2}\sim(\frac{f(2n)}{f(n)^{2}})^{2}.

אם נניח את קירוב סטירלינג, אז f(n)=\sqrt{2\pi n}, והסתברות זו אסימפטוטית ל-\frac{1}{\pi n}. בפרט, הטור \sum_{n\ge0} P(S_{n,2}=\vec{0}) מתבדר (הוא "פרופורציוני" לטור ההרמוני), והילוך שיכור דו-מימדי הוא נשנה. הוכחנו את משפט פוליה במקרה הדו-מימדי בהינתן קירוב סטירלינג!

נחזור לניסיון שלנו להוכיח קירוב סטירלינג ממשפט פוליה. אם נניח ש-f(n) היא מהצורה Cn^{\alpha} אז כדי שהטור הרלוונטי יתבדר, נדרש: \alpha\le 0.5.

4. דוגמא ג' – הילוך שיכור תלת-מימדי

אפשר לקבל חסם תחתון ל-\alpha באמצעות ניתוח המקרה התלת-מימדי, שהוא יותר מסובך. נסמן ב-S_{n,3} את המיקום של הילוך שיכור תלת-מימדי לאחר n צעדים.
כרגיל, אפשר לחזור לראשית רק אחרי מספר זוגי של צעדים, לכן נחשב את ההסתברות להגיע לראשית אחרי 2n צעדים:

P(S_{2n,3}=\vec{0}) = 6^{-2n}\sum_{i+j+k=n}\binom{2n}{i,i,j,j,k,k} = 2^{-2n}\binom{2n}{n}\sum_{i+j+k=n}(3^{-n}\binom{n}{i,j,k})^{2}

בגלל ש-\sum_{i+j+k=n}3^{-n}\binom{n}{i,j,k}=(\frac{1}{3}+\frac{1}{3}+\frac{1}{3})^{n}=1, אפשר לחסום את הסכום האחרון מלמעלה ע"י \max_{i+j+k=n}3^{-n}\binom{n}{i,j,k}=3^{-n}\binom{n}{n/3,n/3,n/3}\sim\frac{f(n)}{f{}^{3}(n/3)}.
(חסם זה הדוק עד כדי קבוע כפלי ונראה זאת בפרק 8 בפוסט).

אם נניח ש-f(n) = Cn^{\alpha}, מקבלים שהאיבר הכללי של הטור \sum_{n\ge0}P(S_{2n,3}=\vec{0}) אסימפטוטי ל-\frac{D}{n^{3\alpha}}. מקירוב סטירלינג, \alpha =0.5 והטור מתכנס. הטור הזה היה מתכנס כל עוד \alpha > \frac{1}{3}.

בינתיים הראנו שקירוב סטירלינג המלא גורר את משפט פוליה, ושמשפט פוליה ביחד עם הנחה מסויימת גורר ש-\frac{1}{3}+o(1) < \frac{\ln f(n)}{\ln n}\le\frac{1}{2}+o(1).

5. קריטריון Nash-Williams

עכשיו אגיד כמה מילים על הוכחה של משפט פוליה בלי (כמעט) אנליזה. המתמטיקאי Nash-Williams נתן קריטריון מספיק (אך לא הכרחי) לכך שהילוך מקרי על גרף לא מכוון G (נגיד \mathbb{Z}^{d}) יהיה נשנה. כדי להסביר את הקריטריון, נגדיר מושג: "קבוצת חתך ביחס לקודקוד a" היא אוסף של צלעות בגרף, כך שכל מסלול אינסופי ופשוט (מסלול שלא חותך את עצמו) בגרף שמתחיל ב-a חייב להיחתך איתה.

עוד שנייה ניתן דוגמאות, אבל ראשית ננסח את הקריטריון: נניח שמצאנו אוסף \{A_{n}\}_{n\ge1} של קבוצות חתך (ביחס לאותו קודקוד) שהן זרות בזוגות. אם \sum_{n\ge1}|A_{n}|^{-1} מתבדר, אז הילוך מקרי על G הוא נשנה.

נדגים זאת על \mathbb{Z},\mathbb{Z}^{2}:

ב-\mathbb{Z}, נבחר קבוצות חתך ביחס ל-0 באופן הבא: A_{n}=\{(-n+1,-n),(n-1,n)\}. כל מסלול אינסופי שמתחיל באפס ולא חותך את עצמו, חייב מתישהו לעבור דרך הצלע שמחברת את n-1 עם n (אם המסלול הולך לאינסוף) או דרך הצלע שמחברת את -(n-1) עם -n (אם הוא הולך למינוס אינסוף). הקבוצות הללו זרות, והטור \sum_{n\ge1}|A_{n}|^{-1}=\sum_{n\ge1}2 מתבדר, לכן לפי הקריטריון, הילוך מקרי על \mathbb{Z} הוא נשנה.

ב-\mathbb{\mathbb{Z}}^{2} נבחר קבוצות חתך ביחס ל-0 באופן הבא: A_{n} תהיה אוסף הצלעות המחברות את הקודקודים במרחק n צעדים מהראשית עם הקודקודים במרחק n+1 מהראשית. (זה גם מה שעשינו במקרה החד-מימדי.)

כל מסלול אינסופי שמתחיל באפס ולא חותך את עצמו, חייב מתישהו לעבור דרך A_{n}. הקבוצות הללו זרות בהגדרה, וגודלן |A_{n}|=8n+4. הטור המתאים, \sum_{n\ge1}|A_{n}|^{-1}=\sum_{n\ge1}\frac{1}{8n+4}, מתבדר. לכן הילוך מקרי על \mathbb{Z}^{2} הוא גם כן נשנה.

ההוכחה של Nash-Williams מסתמכת על אנלוגיות מתחום המעגלים החשמליים, ואפשר לקרוא אותה כאן.

עבור \mathbb{Z}^{3}, אם נבחר קבוצות חתך באופן דומה, נגלה שהן בגודל ריבועי ב-n, ולכן הטור המתאים מתכנס. אני לא מכיר דרך אלגנטית להראות שהילוך על \mathbb{Z}^{3} חולף בלי אנליזה, אבל אפשר לעשות את האנליזה הזו גם ללא קירוב סטירלינג אם רוצים מספיק, כמו שתיראו בתרגיל 8.

6. דוגמא ד' – מרחק מהראשית

נמשיך לנסות להוכיח את קירוב סטירלינג מכיוון הסתברותי, הפעם עם שיקול קצת יותר מתקדם. נחזור להילוך שיכור חד-מימדי, והפעם נתעניין במרחק (בערך מוחלט) אליו מגיע השיכור בתוחלת אחרי n צעדים: E|S_{n}|. כמו כל דבר מעניין, אפשר לחשב ביטוי זה בשתי דרכים.

מצד אחד, S_n הוא סכום של n משתנים בלתי-תלויים \{X_{i}\}_{i=1}^{n} שכולם מתפלגים באופן הבא: X_{i}=\begin{cases} 1 & \Pr=0.5\\ -1 & \Pr=0.5 \end{cases}התוחלת ES_{n} היא בבירור אפס, אבל גם את השונות אפשר לחשב, כסכום השונויות:

\text{Var}(S_{n})=\sum_{i=1}^{n}\text{Var}(X_{i})=n

כלומר E|S_{n}|^{2}=n. אפשר לנחש מכאן שנקבל תוצאה מהצורה E|S_{n}|\sim C\sqrt{n}, ואכן כך.

אם נפעיל את משפט הגבול המרכזי על הסדרה \{ X_i \}_{i \ge 1}, נקבל ש- \frac{S_{n}}{\sqrt{n}}\to N(0,1). לכן נצפה שיתקיים:

\begin{array}{lcl} E|\frac{S_{n}}{\sqrt{n}}| &\to& E|N(0,1)| \\  &=& \frac{1}{\sqrt{2\pi}}\int_{\mathbb{R}}|x|e^{-x^{2}/2}dx \\  &=& \frac{2}{\sqrt{2\pi}}\int_{0}^{\infty}xe^{-x^{2}/2}dx \\  &=& \frac{2}{\sqrt{2\pi}}(-e^{-x^{2/2}})|_{0}^{\infty} \\  &=& \frac{2}{\sqrt{2\pi}} \end{array}

כלומר E|S_{n}|\sim\sqrt{\frac{2}{\pi}n}. הגרירה E|\frac{S_{n}}{\sqrt{n}}|\to E|N(0,1)| נכונה לחלוטין אבל לא טריוויאלית. נחזור אליה בפרק 7 בהמשך הפוסט (ואף נכליל אותה).

מצד שני, אפשר לעשות חישוב ישיר אך מחוכם:

\begin{array}{lcl} E|S_{n}| &=& \sum_{k=0}^{n/2} P(|S_{n}|=n-2k)(n-2k) \\  &=& 2^{-n}\sum_{k=0}^{n/2}(\binom{n}{k}+\binom{n}{n-k})(n-2k) \\  &=& 2^{1-n}\sum_{k=0}^{n/2}((n-k)\binom{n}{n-k}-k\binom{n}{k}) \\  &=& 2^{1-n}\sum_{k=0}^{n/2}(n\binom{n-1}{n-k-1}-n\binom{n-1}{k-1}) \\  &=& 2^{1-n}n\sum_{k=0}^{n/2}(\binom{n-1}{k}-\binom{n-1}{k-1}) \end{array}

והסכום טלסקופי ומצטמצם ל-2^{1-n}n\binom{n-1}{\lfloor\frac{n-1}{2}\rfloor}. למען הנוחות נתמקד במקרה ש-n אי-זוגי, בו הסכום יוצא אסימפטוטי ל-n\frac{f(n-1)}{f^{2}(\frac{n-1}{2})}. אם f(n)\sim Cn^{\alpha}, מקבלים ש-E|S_{n}|\sim\frac{4^{\alpha}}{C}n^{1-\alpha}.

אם נשווה לתוצאה שקיבלו בדרך הראשונה, נקבל \frac{4^{\alpha}}{C}n^{0.5-\alpha}\sim\frac{2}{\sqrt{2\pi}}, כלומר \alpha=0.5,C=\sqrt{2\pi}. קיבלנו שתחת ההנחה ש-f(n) מהצורה Cn^{\alpha} אז בהכרח f(n)=\sqrt{2\pi n}, כמו בקירוב סטירלינג. בפרט, מקבלים שהגורם \sqrt{n} מגיע מסטיית התקן של S_{n} בה אנחנו מנרמלים, ו-\sqrt{2\pi} מגיע מההתפלגות הנורמלית. ואו!

7. תרגילים

תרגיל 1 (תכונה של גרף נשנה)

נניח שהילוך שיכור על גרף G הוא נשנה, כלומר אם הוא מתחיל באיזשהו קודקוד הוא יחזור אליו אינסוף פעמים. הוכיחו שמתקיים משהו חזק יותר: לכל זוג קודקודים בגרף, x,y \in V(G), מתקיים: אם ההילוך מתחיל ב-x הוא יגיע אינסוף פעמים ל-y.

תרגיל 2 (מפגש של 2 הילוכים מקריים)

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

תרגיל 3 (עיקרון השיקוף)

הראו, בצורה קומבינטורית, שההסתברות לחזור לראשית בהילוך חד-מימדי באחד מ-2n הצעדים הראשונים היא 1-\frac{\binom{2n}{n}}{2^{2n}}. (רמז: עיקרון השיקוף.)
הסתמכו על משפט פוליה כדי להראות שההסתברות שואפת ל-1. הסיקו שאם f(n) \sim Cn^{\alpha} אז \alpha חיובי.

תרגיל 4 (הוכחה אלטרנטיבית לנשנות במימדים 1 ו-2)

הראו ש-\frac{1}{2^{2n}}\binom{2n}{n}=\prod_{i=1}^{n}(1-\frac{1}{2i}). הוכיחו באינדוקציה ש-\prod_{i=1}^{n}(1-\frac{1}{2i})\ge\sqrt{\frac{5}{16n+4}} והוכיחו ללא סטירלינג את משפט פוליה עבור הילוכים מקריים חד-מימדיים ודו-מימדיים.

תרגיל 5 (אופטימליות של קבוצות חתך)

נניח שהגרף G הוא עץ לא מכוון, ו-a הוא שורש. הראו שאוסף קבוצות החתך הזרות "צלעות המחברות קודקודים במרחק n מהשורש עם קודקודים במרחק n+1" הן אופטימליות, במובן שהן נותנות טור מקסימלי.

תרגיל 6 (הילוך על \mathbb{Z}^{3} הוא חולף, ללא סטירלינג)

א. הראו ש-k^{-nk}\frac{(nk)!}{n!^{k}}=\prod_{j=1}^{k-1}\prod_{i=1}^{n}(1-\frac{j}{ki}). השתמשו ב-x>0\implies 1-x<e^{-x} כדי להראות שהביטוי האחרון קטן מ-e^{-H_{n}(\frac{k-1}{2})} שקטן מ-n^{-(\frac{k-1}{2})}. השתמשו במקרים k=2,3 כדי להראות ש-\sum_{n\ge 0}P (S_{2n,3}=\vec{0}) מתכנס, כלומר הילוך תלת-מימדי הוא הילוך חולף.

ב. (רשות) הראו שלכל 0<c<1 יש קבועים a,b>0 כך ש-\prod_{i=1}^{n} (1-\frac{c}{i}) \ge (an+b)^{-c} לכל n \ge 1. הסיקו שקיימים קבועים a,b>0 (אחרים) כך ש-k^{-nk}\frac{(nk)!}{n!^{k}} \ge (an+b)^{-(k-1)/2}.

ג. (רשות) ודאו שבעזרת קירוב סטירלינג מקבלים: k^{-nk}\frac{(nk)!}{n!^{k}} \sim n^{\frac{1-k}{2}} (2\pi)^{\frac{1-k}{2}} \sqrt{k}.

5. אינטגרציה נומרית, ניסיון שני

1. מבוא

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

בניסיון הקודם קירבנו פונקציה בעזרת אינטגרל. באנליזה נומרית עושים את ההיפך, ומסתבר שזה יעזור לנו בכל זאת: מנסים להביע אינטגרל באמצעות ערכים בודדים של האינטגרנד (הפונקציה לה עושים אינטגרציה), כך שהשגיאה תהיה מינימלית.
בקירוב הקודם, השתמשנו בנקודת קצה של קטע האינטגרציה: \int_{a}^{b}f(x)dx \approx f(b)(b-a). עבור פולינומים ממעלה 0 (קבועים), הקירוב הזה מדוייק ממש (שגיאה היא 0), אבל כבר עבור פולינום ממעלה 1 (פונקציה לינארית), הקירוב "טועה". נציג 2 כללים טובים בהרבה, ובתרגילים נספר על "מכונה" שמייצרת עוד כאלה.

2. כלל נקודת האמצע

הכלל הוא:

\int_{a}^{b}f(x)dx \approx f(\frac{a+b}{2})(b-a)

כלל זה הוא בעצם שיפור של כלל נקודת הקצה שראינו קודם. במקום לבחור נקודה בקצה הקטע, נבחר נקודה באמצע הקטע. זה במיוחד הגיוני במקרה שלנו, בו הפונקציה f(x) = \ln x מונוטונית. את הגובה של הנקודה נכפיל באורך הקטע.

כלל נקודת האמצע

נחשב במדויק מה סדר גודל השגיאה בכלל זה (זה יהיה קצת טכני). ראשית, נשים לב לכך שהכלל מדויק לחלוטין לפונקציות לינאריות ולא רק לפונקציות קבועות (מספיק לוודא עבור f(x)=1,x). כדי להבין את השגיאה, נעשה פיתוח טיילור מסדר 1 של f סביב \frac{a+b}{2}, ועליו נפעיל את הכלל. הפיתוח הוא:

f(x) = f(\frac{a+b}{2})+(x-\frac{a+b}{2})f'(\frac{a+b}{2})+\frac{(x-\frac{a+b}{2})^{2}}{2}f''(\xi_{x})

עבור איזשהו \xi_{x}\in[a,b]. הגורם הראשון, אחרי אינטגרציה, הוא הערך שמתקבל מכלל נקודת האמצע. הגורם השני יתאפס אחרי האינטגרציה והגורם השלישי הוא השגיאה:

\begin{array}{lcl} \int_{a}^{b}f(x)dx &=& \int_{a}^{b}f(\frac{a+b}{2})dx+f'(\frac{a+b}{2})\int_{a}^{b}(x-\frac{a+b}{2})dx+\int_{a}^{b}\frac{(x-\frac{a+b}{2})^{2}}{2}f''(\xi_{x})dx\\  &=& f(\frac{a+b}{2})(b-a)+0+\int_{a}^{b}\frac{(x-\frac{a+b}{2})^{2}}{2}f''(\xi_{x})dx \end{array}

ניזכר במשפט הערך הממוצע של קושי – עבור פונקציות רציפות f,g כך ש-g לא משנה סימן בקטע [a,b], קיים x בקטע כך ש-

\int_{a}^{b}f(t)g(t)dt=f(x)\int_{a}^{b}g(t)dt

ננצל את זה ש-\frac{(x-\frac{a+b}{2})^{2}}{2} חיובית בקטע [a,b] ונפעיל את המשפט על האינטגרל האחרון, שהוא בדיוק השגיאה שלנו:

\begin{array}{lcl}\text{Error} &=& \int_{a}^{b}\frac{(x-\frac{a+b}{2})^{2}}{2}f''(\xi_{x})dx \\  &=& f''(\xi)\int_{a}^{b}\frac{(x-\frac{a+b}{2})^{2}}{2}dx \\  &=& f''(\xi)\frac{(b-a)^{3}}{24} \end{array}

עבור איזשהו \xi בקטע [a,b]. זו השגיאה בכלל נקודת האמצע. \blacksquare

כדי לקרב סכום כמו \sum_{i=1}^{n} f(i), נחליף כל מחובר f(i) באינטגרל \int_{i-\frac{1}{2}}^{i+\frac{1}{2}} f(x) dx בעזרת כלל נקודת האמצע, נסכום, ונקבל:

\int_{\frac{1}{2}}^{\frac{n+1}{2}}f(x)dx \approx \sum_{i=1}^{n}f(i)

במקרה f(x)=\frac{1}{x}, נקבל ש-H_{n} \approx\ln(\frac{n+1}{2})-\ln(\frac{1}{2})=\ln(n+1), והשגיאה היא \frac{1}{12}\sum_{k=1}^{n}\xi_{k}^{-3} כאשר \xi_{k}\in[k-\frac{1}{2},k+\frac{1}{2}], והיא מתכנסת לקבוע.

במקרה שלנו, f(x)=\ln x נקבל ש-\ln(n!) \approx \int_{\frac{1}{2}}^{\frac{n+1}{2}}\ln xdx=(x\ln x-x)|_{1/2}^{(n+1)/2}. מחשבים ומקבלים:

\begin{array}{lcl} \ln(n!) &\approx & (n+\frac{1}{2})\ln(n+\frac{1}{2})-n \\  &=& (n+\frac{1}{2})\ln n-n+(n+\frac{1}{2})\ln(1+\frac{1}{2n}) \\  &=& (n+\frac{1}{2})\ln n-n+\frac{n+\frac{1}{2}}{2n}\ln(1+\frac{1}{2n})^{2n} \\  &=& (n+\frac{1}{2})\ln n-n+\frac{1}{2}+o(1) \end{array}

בואו נחשב את השגיאה, שמתכנסת לקבוע:

\text{Error} = -\frac{1}{24}\sum_{k=1}^{n}f''(\xi_{k}) = \frac{1}{24}\sum_{k=1}^{n}\xi_{k}^{-2}= \frac{1}{24}\sum_{k=1}^{\infty}\xi_{k}^{-2} +o(1)

כאשר \xi_{k}\in[k-\frac{1}{2},k+\frac{1}{2}]. כך קיבלנו בקלות כמעט את כל הקירוב! רק הקבוע \frac{\ln2\pi}{2} חסר, אבל אנחנו יודעים אותו מהנימוק עם ההתפלגות הנורמלית מסוף פרק 4, או מדרכים אחרות שיבואו בהמשך.

3. כלל הטרפז

נציג כעת כלל אחר, כלל הטרפז, אותו נמשיך ונכליל בהמשך:

\int_{a}^{b}f(x)dx \approx \frac{b-a}{2}(f(b)+f(a))

כלל זה כבר משתמש בשתי נקודות – למעשה הוא עושה אינטרפולציה לינארית לפונקציה דרך 2 נקודות הקצה שלה (ובפרט הוא מדויק לחלוטין לפולינומים עד מעלה 1). שמו בא מהציור הבא:

כלל הטרפז

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

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

\int1dx=x-\frac{a+b}{2}
\int(x-\frac{a+b}{2})dx=\frac{(x-\frac{a+b}{2})^{2}}{2}-\frac{(b-a)^{2}}{8}

הפונקציה הקדומה \frac{(x-\frac{a+b}{2})^{2}}{2}-\frac{(b-a)^{2}}{8} נבחרה במיוחד כך שתתאפס על הקצוות x=a,b. נראה איך זה עוזר:

\begin{array}{lcl} \int_{a}^{b}f(x)dx &=& (x-\frac{a+b}{2})f(x)|_{a}^{b}-\int_{a}^{b}(x-\frac{a+b}{2})f'(x)dx\\  &=& \frac{b-a}{2}(f(b)+f(a))-\int_{a}^{b}(x-\frac{a+b}{2})f'(x)dx \end{array}

הגורם הראשון הוא הקירוב, והשני הוא השגיאה:

\begin{array}{lcl} -\text{Error} &=& \int_{a}^{b}(x-\frac{a+b}{2})f'(x)dx \\  &=& (\frac{(x-\frac{a+b}{2})^{2}}{2}-\frac{(b-a)^{2}}{8})f'(x)|_{a}^{b}-\int_{a}^{b}(\frac{(x-\frac{a+b}{2})^{2}}{2}-\frac{(b-a)^{2}}{8})f''(x)dx \\  &=& \int_{a}^{b}-(\frac{(x-\frac{a+b}{2})^{2}}{2}-\frac{(b-a)^{2}}{8})f''(x)dx \end{array}

בגלל ש--(\frac{(x-\frac{a+b}{2})^{2}}{2}-\frac{(b-a)^{2}}{8}) לא משנה סימן ב-[a,b], משפט הערך הממוצע של קושי נותן:

\text{Error} = f''(\xi)\int_{a}^{b}(\frac{(x-\frac{a+b}{2})^{2}}{2}-\frac{(b-a)^{2}}{8})f''(x) = -\frac{f''(\xi)}{12}(b-a)^{3}

עבור איזשהו \xi \in [a,b]. זו השגיאה בכלל הטרפז. \blacksquare

עבור a=i,b=i+1 נקבל: \int_{i}^{i+1}f(x)dx\approx\frac{f(i+1)+f(i)}{2}. נסכום על i=1,2,\cdots,n-1 ונקבל:

\sum_{i=1}^{n}f(i) \approx \frac{f(1)+f(n)}{2}+\int_{1}^{n}f(x)dx

במקרה f(x)=\frac{1}{x} מקבלים ש-H_{n}\approx \frac{1+\frac{1}{n}}{2}+\ln n. השגיאה היא:

\text{Error} = -\frac{1}{6}\sum_{k=1}^{n-1}\xi_{k}^{-3}

כאשר \xi_{k}\in[k,k+1].

במקרה f(x)=\ln x מקבלים ש-\ln(n!)\approx \frac{\ln n}{2}+(n\ln n-n-(1\ln1-1))=\frac{\ln n}{2}+n\ln n-n+1, והשגיאה מתכנסת לקבוע:

\text{Error} = \frac{1}{12}\sum_{k=1}^{n-1}\xi_{k}^{-2}

כאשר \xi_{k}\in[k,k+1]. אז שוב קיבלנו את כל הקירוב מלבד הקבוע. 

4. תרגילים

תרגיל 1 (כלל סימפסון)

נבחן את כלל האינטגרציה הנומרית הבא: \int_{a}^{b} f(x) dx \approx (b-a)\frac{f(a) + 4f(\frac{a+b}{2}) + f(b)}{6}. הראו שהוא מדויק לכל פולינום עד מעלה 3 (כולל), ולמעשה השגיאה היא: -\frac{(b-a)^5}{2880}f^{(4)}(\xi) עבור איזשהו \xi \in [a,b].

תרגיל 2 (נוסחאות Newton-Cotes)

נניח ואנחנו רוצים להמציא כלל אינטגרציה. נרצה שהוא יהיה מהצורה הבאה:

\int_{a}^{b} f(x) dx \approx \sum_{i=0}^{n} w_i f(a + i \frac{b-a}{n})

כאשר n קבוע ו-w_i משקולות קבועות.

א. איך נמצא משקולות כך שהכלל יהיה מדויק לפולינומים עד מעלה n לפחות?

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

ג. המקרה n=1 הוא כלל הטרפז, ו-n=2 הוא כלל סימפסון. פתחו את הכללים המתאימים ל-n=3 ו-n=4, וודאו שהם מדויקים עד מעלה 3 ו-5 בהתאמה.

ד. נוסיף את האילוץ w_0 = w_n = 0. כלל כזה נקרא 'כלל פתוח', והמשקולות נבחרים כך שהכלל יהיה מדויק עד מעלה n-2. הראו שכאשר n זוגי, מקבלים כלל מדויק עד מעלה n-1. הראו שבמקרה n=2 מקבלים את כלל נקודת האמצע.

6. נוסחת אוילר-מקלורן

1. פיתוח נוסחת אוילר-מקלורן

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

ראינו שעבור מספרים שלמים a<b, האינטגרל I=\int_{a}^{b}f(x)dx מקרב את הסכום S=\sum_{i=a}^{b-1}\frac{1}{2}(f(i)+f(i+1))=\frac{1}{2}(f(a)+f(b))+\sum_{a<i<b}f(i). נוסחת הסכום של אוילר-מקלורן מאפשרת להבין את השגיאה בין האינטגרל לסכום הרבה יותר טוב, ספציפית היא מובעת בתור סכום סופי ואינטגרל:

\begin{array}{lcl} S-I &=& \sum_{k=2}^{p}\frac{B_{k}}{k!}(f^{(k-1)}(b)-f^{(k-1)}(a))+R_{p} \\  R_{p} &=& (-1)^{p+1}\int_{a}^{b}f^{(p)}(x)\frac{B_{p}(x-\lfloor x\rfloor)}{p!}dx \end{array}

כאשר \{ B_k\}_{k \ge 1} היא סדרה קסומה של מספרים הנקראים 'מספרי ברנולי', ו-\{ B_k(x)\}_{k \ge 1} הם פולינומי ברנולי. לא נגדיר אותם כעת – ההגדרה הרקורסיבית להם צצה באופן טבעי במהלך ההוכחה. נשים לב ש-x - \lfloor x \rfloor היא פונקצייה בעלת מחזור באורך 1.

נעיר שכש-p שואף לאינסוף ומתקיימים התנאים כך ש-R_p שואף לאפס, מקבלים הצגה של השגיאה בתור טור:

\sum_{k=2}^{\infty}\frac{B_{k}}{k!}(f^{(k-1)}(b)-f^{(k-1)}(a))

מעתה נעשה לנו את החיים קלים ונניח ש-a=0,b=1, כי הנוסחה הכללית מוכחת באמצעות פירוק  [a,b] לקטעים סמוכים באורך 1. עבור a=0,b=1, הביטוי x-\lfloor x\rfloor הופך ל-x.

ראינו בפרק הקודם ש-S-I=\int_{0}^{1}(x-\frac{1}{2})f'(x)dx (כמסקנה מכלל הטרפז), ועשינו זאת עם אינטגרציה בחלקים:

\begin{array}{lcl} I &=& \int_{0}^{1}f(x)dx \\  &=& (x-\frac{1}{2})f(x)|_{0}^{1}-\int_{0}^{1}(x-\frac{1}{2})f'(x)dx\\  &=& \frac{1}{2}(f(1)+f(0))-\int_{0}^{1}(x-\frac{1}{2})f'(x)dx \\  &=& S-\int_{0}^{1}(x-\frac{1}{2})f'(x)dx  \end{array}

זאת נוסחת אוילר-מקלורן עבור p=1, כי B_{1}(x)=x-\frac{1}{2}.
כדי להראות את הנוסחה באינדוקציה, צריך להוכיח:

R_{p} = R_{p+1}+\frac{B_{p+1}}{(p+1)!}(f^{(p)}(1)-f^{(p)}(0))

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

לדוגמא, B_{2}(x)=C+\int_{0}^{x}2(t-\frac{1}{2})dt=C+x^{2}-x. האינטגרל בין 0 ל-1 הוא \frac{1}{3}-\frac{1}{2}+C=C-\frac{1}{6}, ולכן B_{2}(x)=x^{2}-x+\frac{1}{6}. כעת:

\int_{0}^{1}f^{(p)}(x)\frac{B_{p}(x)}{p!}dx =( \frac{B_{p+1}(x)}{(p+1)!}f^{(p)}(x))|_{0}^{1}-\int_{0}^{1}\frac{B_{p+1}(x)}{(p+1)!}f^{(p+1)}(x) dx

ובשפת ה-R_p-ים, זה שקול ל:

(-1)^{p+1}R_{p} =\frac{1}{(p+1)!} (B_{p+1}(1)f^{(p)}(1) - B_{p+1}(0)f^{(p)}(0)) +R_{p+1}(-1)^{p+1}

ולאחר הכפלה ב-(-1)^{p+1} אנחנו מקבלים את מה שהיינו צריכים, בהנחה ש-B_{p+1}(0)=B_{p+1}(1)=B_{p+1}(-1)^{p+1}. איך מראים זאת?

• אפשר להראות באינדוקציה ש-B_{n}(x)=B_{n}(1-x)(-1)^{n} עבור n\ge1: עבור n=1 זה נכון, ובצעד האינדוקציה נשים לב שלשתי הפונקציות יש אותו אינטגרל בין 0 ל-1 משיקולי סימטריה (ואינטגרל זה כאמור הוא 0), ואותה נגזרת (מהנחת האינדוקציה), לכן הן שוות.

• נציב x=0 ונקבל B_{n}(0)=B_{n}(1)(-1)^{n}. עבור n זוגי, אכן קיבלנו ש-B_{n}(0)=B_{n}(1), כמו שרצינו. עבור n אי-זוגי אפשר להראות ש-B_{n}(0)=0 ושוב הטענה נכונה (הראו זאת, או הסתכלו בתרגיל בסוף הפרק).

\blacksquare

משהוכחנו ש-B_{n}(0)=B_{n}(1) עבור n\ge 2, את מספרי ברנולי נוכל פשוט להגדיר בתור B_{n}=B_{n}(0)(-1)^{n}, ועבור n=1 הסימן הפוך: B_{1}=-\frac{1}{2}.

בגלל שערכים אי-זוגיים של מספרי ברנולי מתאפסים, חצי מהאיברים בסכום \sum_{k=2}^{p}\frac{B_{k}}{k!}(f^{(k-1)}(b)-f^{(k-1)}(a)) מתאפסים. לכן תמיד עדיף לקחת p=2k+1 מאשר p=2k, כי כך מחליפים את R_{2k} ב-R_{2k+1} בחינם:

S-I = \sum_{i=2,4,\cdots,2k}\frac{B_{i}}{i!}(f^{(i-1)}(b)-f^{(i-1)}(a))+R_{2k+1}

2. שימוש במקרה שלנו

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

נבחר f(x)=\ln x,a=1,b=n. מתקיים f^{(k)}(x)=\frac{(-1)^{k-1}(k-1)!}{x^{k}}, ונקבל:

\ln(n!)-((n+\frac{1}{2})\ln n-(n-1)) = \sum_{i=2,4,\cdots,2k}\frac{B_{i}}{i(i-1)}(n^{1-i}-1)+R_{2k+1}

אם נבחר k=1 לדוגמא, נקבל באגף ימין \frac{1}{12}(\frac{1}{n}-1)+R_{3}. נחסום את R_3. בגלל ש-B_{3}(x-\lfloor x\rfloor) חסום ע"י קבוע, ו-\int_{n}^{\infty}x^{-3}dx=O(n^{-2}), נובע ש-

R_{3}=\frac{1}{3}\int_{1}^{n}x^{-3}B_{3}(x-\lfloor x\rfloor)dx = C+O(n^{-2})

וסה"כ קיבלנו:

\ln n! = n\ln n-n+\frac{\ln n}{2}+C+\frac{1}{12n}+O(n^{-2})

כלומר n!=(\frac{n}{e})^{n}\sqrt{2\pi n}(1+\frac{1}{12n}+O(n^{-2})) (כי e^x = 1+x+O(x^2)).

אפשר להמשיך את החישוב עם עוד ערכים של k ולקבל:

\ln n! = n\ln n-n+\frac{\ln n}{2}+C+\frac{1}{12n}-\frac{1}{360n^{3}}+\frac{1}{1260n^{5}} + O(n^{-7})

(ניתן להראות ש-R_{2p+1} = C + O(n^{-2k-1}).)

בפרק הבא נראה ריגורוזית למה C=\frac{\ln2\pi}{2}.

3. שימוש קלאסי – סכום חזקות

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

S_m(n) = \sum_{i=1}^{n} i^m = \sum_{i=0}^{n} i^m

נפעיל את הנוסחה על הפונקציה f(x)=x^m והקטע [0,n]. כאשר p=1 (כלל הטרפז) מקבלים:

S_m(n) = \frac{0^m + n^m}{2} + \sum_{i=0}^{n-1} \frac{f(i)+f(i+1)}{2} = \frac{n^m}{2} + \int_{0}^{n} x^m dx + \int_{0}^{n} B_1(x-\lfloor x \rfloor) mx^{m-1} dx

נשים לב ש-B_2'=2B_1 וש-B_2(0)=B_2(1), ולכן ע"י אינטגרציה בחלקים מקבלים שהאינטגרל האחרון הוא:

-\frac{1}{2}\int_{0}^{n} B_2(x-\lfloor x \rfloor) m(m-1)x^{m-2} dx

בגלל ש-B_2(x-\lfloor x \rfloor) חסומה, זה אומר שהאינטגרל הוא O(n^{m-1}). לכן מקבלים שהסכום הוא:

S_m(n) = \frac{n^{m+1}}{m+1} + \frac{n^m}{2} + O(n^{m-1})

עם p=m+1 אפשר להבין את השגיאה לגמרי – הנגזרות ה-m+1 והילך מתאפסות, ולכן מקבלים קירוב מושלם מהצורה הבאה:

 S_m(n) = \int_{0}^{n} x^m dx + \frac{f(n)+f(0)}{2} + \sum_{k=2}^{m+1} \frac{B_k}{k!} (f^{(k-1)}(n) - f^{(k-1)}(0))

אפשר לפשט הצגה זו רבות – ראשית, לא צריך את האיבר האחרון המתאים ל-k=m+1, כי הנגזרת ה-m-ית קבועה. בגלל שהנגזרות של f ב-x=0 מסדר קטן מ-m מתאפסות, אפשר לוותר על הגורם f^{(k-1)}(0). בנוסף, אפשר לחשב מפורשות את הגורם f^{(k-1)}(n):

f^{(k-1)}(n) = \frac{m!}{(m-k+1)!} n^{m-k+1} = \binom{m+1}{k} \frac{k!}{m+1} n^{m-k+1}

ולכן הסכום נהיה:

S_m(n) = \frac{n^{m+1}}{m+1} + \frac{n^m}{2} + \frac{1}{m+1} \sum_{k=2}^{m} B_k \binom{m+1}{k} n^{m-k+1}

בפרט הוכחנו ש-S_m(n) פולינום ממעלה m+1.

יש כמה תכונות שכדאי לשים לב אליהן בנוסחה של S_m(n):

  • חצי מהגורמים בנוסחה הם 0, כי B_k = 0 כאשר k אי-זוגי גדול מ-1. לכן אם m זוגי, כמעט כל המונומים הם ממעלה אי-זוגית, ולהיפך. בפרט, הפולינום המתקבל מתחלק ב-n.
  • למקדמים \{ \frac{B_{2k} \binom{m+1}{2k} }{m+1} \}_{k=1}^{\lfloor m/2 \rfloor} יש סימנים מתחלפים.

נדגים את החישוב של S_2(n):

S_2(n) = \frac{n^3}{3} + \frac{n^2}{2} + B_2n = \frac{n^3}{3} + \frac{n^2}{2} + \frac{n}{6} = \frac{n(n+1)(2n+1)}{6}

ודוגמא יותר מסובכת:

S_6(n) = \frac{n^7}{7} + \frac{n^6}{2} + 3B_2 n^5 + 5B_4n^3 + B_6 n = \frac{n^7}{7} + \frac{n^6}{2} + \frac{1}{2} n^5 -\frac{1}{6} n^3 +\frac{1}{42} n

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

S_m(n) = \sum_{i=0}^{m} S(m,i)i! \binom{n+1}{i+1}

כאשר המספרים S(n,k) נקראים 'מספרי סטירלינג מהסוג השני', על שם אותו סטירלינג מקירוב סטירלינג.

4. תרגילים

תרגיל 1 (חסם אבסולוטי ל-n!)

הראו ש-C + \frac{1}{12n+1} < \ln(n!) - ((n+\frac{1}{2})\ln n -n) < C + \frac{1}{12n}, כאשר C הוא לוג של הקבוע של סטירלינג (\frac{\ln (2\pi)}{2}).

במילים אחרות, n! = (\frac{n}{e})^{n} \sqrt{2\pi n} e^{\lambda_n} כאשר \frac{1}{12n+1} < \lambda_n < \frac{1}{12n}.

תרגיל 13 (מספרי ברנולי)

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

מספרי ברנולי מוגדרים ע"י B_0=1 ונוסחת הנסיגה \sum_{k=0}^{m} \binom{m+1}{k}B_k = 0.

פולינומי ברנולי מוגדרים ע"י B_n(x) = \sum_{k=0}^{n} \binom{n}{k} B_{n-k}x^k.

(אתם צריכים לוודא ש-B_{n+1}'(x) = (n+1)B_n(x), \int_{0}^{1} B_n(x) dx = 0 וש-B_n(0)=B_n(1) = (-1)^n B_n. רמז: הפונקציה היוצרת האקספוננציאלית של מספרי ברנולי היא הפונקציה ה"כמעט-זוגית" \frac{t}{e^t-1}.)

ב. הראו של-\{B_{2k} \}_{k \ge 1} יש סימנים מתחלפים.

7. חישוב הקבוע

1. תזכורת

כלל הטרפז (או אוילר-מקלורן) נתן לנו את הזהות הבאה באינטגרציה בחלקים:

\sum_{i=1}^{n} f(i) =\frac{1}{2}(f(1)+f(n))+ \int_{1}^{n} f(x)dx + \int_{1}^{n} (x-\lfloor x \rfloor - \frac{1}{2}) f'(x) dx

אם נציב f(x) = \frac{1}{x} נקבל:

\sum_{k=1}^{n}\frac{1}{k}=\ln n+\frac{1}{2n}+\frac{1}{2}-\int_{1}^{n}\frac{(x-\lfloor x\rfloor)-\frac{1}{2}}{x^{2}}dx

כלומר \lim_{n\to\infty}H_{n}-\ln n=\frac{1}{2}-\int_{1}^{\infty}\frac{\{x\}-\frac{1}{2}}{x^{2}}dx. קבוע זה נקרא קבוע אוילר-מסקרוני ומסומן \gamma. ערכו הוא בקירוב 0.5772, כלומר \int_{1}^{\infty}\frac{\{x\}-\frac{1}{2}}{x^{2}}dx\approx-0.0772. לא ידוע האם הקבוע הזה רציונלי או אי-רציונלי.

בדומה, אם נציב f(x) = \ln x בכלל הטרפז נקבל את הזהות:

\ln(n!)=\sum_{i=1}^{n}\ln i=n\ln n-n+\frac{\ln n}{2}+1+\int_{1}^{n}\frac{(x-\lfloor x\rfloor)-\frac{1}{2}}{x}dx

כלומר \lim_{n\to\infty}\ln(n!)-(n\ln n-n+\frac{\ln n}{2})=1+\int_{1}^{\infty}\frac{\{x\}-\frac{1}{2}}{x}dx. מסטירלינג אנחנו יודעים שגבול זה הוא \frac{\ln(2\pi)}{2}\approx 0.9189, ולכן האינטגרל הוא בקירוב -0.081.

מטרתנו בחלק זה היא להוכיח שאכן הקבוע בסטירלינג הוא \frac{\ln(2\pi)}{2}.

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

E|S_{n}|\approx\frac{2\sqrt{n}}{\sqrt{2\pi}}

שתי ההנחות היו אלו:

1. n! \sim (\frac{n}{e})^n f(n) כאשר f(n) = Cn^{\alpha} – עכשיו אנחנו בוגרים יותר ויודעים שזה נכון עם \alpha = \frac{1}{2}.

2. אם \frac{S_n}{\sqrt{n}} מתכנס בהתפלגות ל-N(0,1) אז E|\frac{S_{n}}{\sqrt{n}}|\to E|N(0,1)|. נסביר את נכונות הגבול הזה בהמשך הפרק הנוכחי.

אבל קודם – היסטוריה:

2. דה מואבר

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

The Doctorine of Chances: Or, A Method of Calculating the Probability of Events in Play

2^{-n}\binom{n}{\frac{n}{2}+k\sqrt{\frac{n}{4}}}\sim\sqrt{\frac{2}{\pi n}}e^{-k^{2}/2}

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

תרגיל 14: בתרגיל זה הסתמכו על קירוב סטירלינג במלואו. הגדירו H(p)=p\log_{\frac{1}{2}}p+(1-p)\log_{\frac{1}{2}}(1-p) – האנטרופיה של מטבע עם סיכוי p לעץ ו-q=1-p לפלי.

א. יהי p קבוע בין 0 ל-1, ו-m=(p+o(1))n. הראו ש-\log_{2}\binom{n}{m}\sim n(H(p)+o(1)).

ב. עבור p=\frac{1}{2} שפרו זאת באופן הבא: אם m=\frac{n}{2}+k\sqrt{\frac{n}{4}},k=o(n^{2/3}), הראו ש-

\binom{n}{m}=(\sqrt{\frac{2}{\pi}}+o(1))\frac{2^{n}}{\sqrt{n}}\exp(-\frac{k^{2}}{2})

כלומר, המקדם הבינומי הוא (בקירוב) גאוסיאן. (זה המשפט של דה מואבר.)

ג. כעת הניחו רק n!\sim C(\frac{n}{e})^{n}\sqrt{n}. הראו ש-\binom{n}{m}=(\frac{2}{C}+o(1))\frac{2^{n}}{\sqrt{n}}\exp(-\frac{k^{2}}{2}). השתמשו בכך ש-\int_{-\infty}^{\infty}e^{-x^{2}/2}dx=\sqrt{2\pi} כדי להסיק ש-C=\sqrt{2\pi}. (קרדיט לנועם.)

3. אינטגרבליות יוניפורמית וחישוב ריגורוזי

כדי להסביר למה E|\frac{S_{n}}{\sqrt{n}}|\to E|N(0,1)|, אין מנוס מלדבר על אינטגרביליות יוניפורמית.

משפחת משתנים מקריים \{X_{i}\}_{i\in I} שמקיימת \forall\varepsilon>0\exists k>0\forall i\in I:E|X_{i}|\cdot1_{|X_{i}|>k}<\varepsilon, תיקרא "אינטגרבילית יוניפורמית". ניסוח קצת פחות מרתיע: \lim_{k \to \infty} \sup_{i\in I} E|X_i|\cdot 1_{|X_i| > k}.

השימושיות של המושג הזה תהיה ברורה מהמשפט הבא:

משפט: התכנסות בהסתברות + אינטגרביליות יוניפורמית גוררת התכנסות בתוחלת. ובסימונים: אם \lim_{n \to \infty} P(|X_n - X| \ge \varepsilon) = 0 לכל \varepsilon חיובי, ובנוסף  \{ X_i \}_{i=1}^{\infty} אינטגרבילית יוניפורמית, אז: \lim_{n \to \infty} E|X_n - X| = 0.

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

למה: תהי \{X_i \}_{i \in I} סדרת מ"מ עם מומנט שני סופי וקבוע M. אז \{X_i \}_{i \in I} אינטגרבילית יוניפורמית. הוכחה: ההוכחה תהיה בניחוח אי-שיוויון צ'בישב. נראה שיש חסם עליון על E|X_i| \cdot 1_{|X_i| > a} שלא תלוי ב-i:

E|X_i | \cdot 1_{|X_i| > a} \le \frac{1}{a} E|X_i|^2 \cdot 1_{|X_i|>a} \le \frac{E|X_i|^2}{a} = \frac{M}{a}

וחסם זה שואף לאפס כש-a \to \infty. \blacksquare.

תהי \{X_i\}_{i \ge 1} סדרת משתנים מקריים בלתי-תלויים שמגיעים מאותה התפלגות עם תוחלת סופית \mu ושונות סופית \sigma^2. המשתנים Y_n = \frac{\sum_{i=1}^{n} X_i - n \mu}{\sqrt{n}\sigma} בעלי תוחלת 0 ושונות 1, וממשפט הגבול המרכזי הם שואפים בהתפלגות ל-N(0,1).

לשאיפה בהתפלגות יש שני איפיונים שקולים (השקילות מושארת כתרגיל לקורא):

1. פונקציית הצפיפות המצטברת של Y_n שואפת נקודתית לפונקציית הצפיפות של התפלגות נורמלית, כלומר P(Y_n \le k)\to\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{k}e^{-x^{2}/2}dx.

2. לכל פונקציה רציפה וחסומה f מתקיים E f(Y_n) \to Ef(N(0,1)).

האיפיון השני נראה מבטיח – היינו רוצים פשוט להשתמש בו עם הפונקציה f(x)=|x|. היא אומנם רציפה אך היא לא חסומה. אל דאגה – אפשר להתגבר על כך!

משפט: E|Y_i| \to E|N(0,1)|הוכחה: נשתמש בטריק המוכר מתורת המידה – נגדיר את חברתה החסומה והרציפה של f, שהיא f_{M}(x)=\min\{|x|,M\}. מתקיים, מהאיפיון השני:

Ef_{M}(Y_n) \to Ef_{M}(N(0,1))

כמעט סיימנו. נשתמש באי-שיוויון המשולש כדי להעריך את ההפרש בין Ef(Y_n) ל-Ef(N(0,1)):

|Ef(Y_n)-Ef(N(0,1))| \le |Ef(Y_n)-Ef_{M}(Y_n)| + |Ef_{M}(Y_n)-Ef_{M}(N(0,1))| + |Ef_{M}(N(0,1))-Ef(N(0,1))|

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

הביטוי הראשון חסום ע"י E|Y_n| \cdot1_{|Y_n|\ge M}. מהלמה, \{Y_i \}_{i \ge 1} אינטגרבילית יוניפורמית, והביטוי שואף לאפס כשבוחרים M גדול מספיק.

נשאר לנו לטפל רק בביטוי השלישי. הוא דועך, לדוגמא בזכות משפט ההתכנסות המונוטונית של לבג. \blacksquare

אם נפעיל את המשפט על משתנים שבאים מההתפלגות \begin{cases} -1 & P=0.5 \\ 1 & P=0.5 \end{cases}, נקבל ש-E|\frac{S_n}{\sqrt{n}}| \to E|N(0,1)|, כמו שרצינו.

4. תרגילים

אתן שלושה תרגילים המפרטים הוכחות נוספות לכך שהקבוע הוא \sqrt{2\pi}. שני התרגילים הראשונים הם טכנים ופחות אינטואיטיביים, השלישי מעניין יותר.

תרגיל 1 (מכפלת Wallis)

מכפלת Wallis היא הגבול הבא: \prod_{n\ge1}\frac{(2n)(2n)}{(2n-1)(2n+1)}=\frac{\pi}{2}. ניתן לכם לפתח 2 הוכחות לכך – הראשונה לא ריגורוזית, והשנייה כן.

1. א. ודאו שהאפסים של הפונקציה \frac{\sin x}{x} הם המספרים מהצורה \{ n\pi \}_{n\in\mathbb{Z}-0} , וב-x=1 היא מקבלת 1.

ב. כתבו אותה בתור מכפלה באופן הבא (זה החלק הלא מנומק במלואו):

\frac{\sin x}{x}=\prod_{n\in\mathbb{Z}-\{0\}}(1-\frac{x}{\pi n})

זווגו אפסים סימטריים ביחס לאפס כדי לקבל \frac{\sin x}{x}=\prod_{n\ge1}(1-\frac{x^{2}}{\pi^{2}n^{2}}).

ג. הציבו x=\frac{\pi}{2} והסיקו את הגבול.

ועכשיו ההוכחה הריגורוזית.

2. א. נסמן I(n)=\int_{0}^{\pi}\sin^{n}x dx. שימו לב ש-I(n) סדרה יורדת.

ב. הראו באינטגרציה בחלקים ש-I(2n)=\pi\prod_{k=1}^{n}\frac{2k-1}{2k} ו-I(2n+1)=2\prod_{k=1}^{n}\frac{2k}{2k+1}.

ג. חשבו את הגבול \lim_{n}\frac{I(2n)}{I(2n+1)} בשתי דרכים – דרך אחת היא באמצעות המונוטוניות והשיוויון \frac{I(2n-1)}{I(2n+1)}=\frac{2n+1}{2n}. הדרך השנייה היא להביע אותו בתור מכפלה – פשוט תציבו את הנוסחאות מסעיף ב. הסיקו את הערך של מכפלת Wallis.

תרגיל 2 (חישוב הקבוע ע"י מניפולציות אלגבריות)

א. הראו ש-

2^{-2n}\binom{2n}{n}=\frac{\prod_{i=1}^{n}(2i-1)}{\prod_{i=1}^{n}(2i)}=\frac{1}{2n}\prod_{j=1}^{n-1}(1+\frac{1}{2j})=\frac{\prod_{j=1}^{n}(1-\frac{1}{4j^{2}})}{\prod_{j=1}^{n}(1+\frac{1}{2j})}

מעניין להראות באמצעות ההצגות הללו ש-\frac{C_1}{\sqrt{n}}\le2^{-2n}\binom{2n}{n}\le\frac{C_2}{\sqrt{n}}. אומנם אנחנו כבר יודעים את זה אבל עבדנו קשה לשם כך.

ב. נסמן:

 s_{n}=(\frac{1}{2}\frac{3}{2}\frac{3}{4}\frac{5}{4}\cdots\frac{2n-3}{2n-2}\frac{2n-1}{2n-2})\frac{2n-1}{2n}\frac{1}{2n}

שימו לב לתכונות (2^{-2n}\binom{2n}{n})^{2}=s_{n} , s_{n+1}=s_{n}\frac{(2n+1)^{2}}{(2n+2)^{2}}.

ג. הסיקו ש-2ns_{n} סדרה עולה וש-(2n+1)s_{n} יורדת. הראו ש-\lim s_{n}=0 אבל \lim ns_{n} מתכנס לגבול חיובי L.

ד. הסיקו כי \sqrt{\frac{L}{(n+0.5)}}\le2^{-2n}\binom{2n}{n}\le\sqrt{\frac{L}{n}}. נותר להראות ש-L=\frac{1}{\pi}. זה שקול ל-\prod_{n\ge1}\frac{(2n)(2n)}{(2n-1)(2n+1)}=\frac{\pi}{2} – מכפלת Wallis.

תרגיל 3 (חישוב הקבוע באמצעות שארית טיילור)

דן רומיק פירסם הוכחה שמתיימרת להיות ההוכחה הקצרה ביותר לקירוב סטירלינג. (זה לא נכון – ראו לדוגמא את ההוכחה הקצרצרה הזו.) הוא מפרק את ההוכחה לשני חלקים  – חלק ראשון הוא להראות ש-n! \sim C (\frac{n}{e})^n \sqrt{n} עבור איזשהו קבוע חיובי C (הוא עושה זאת עם כלל הטרפז, כמונו). החלק השני הוא לחשב את הקבוע, והוא עושה זאת בדרך מקורית שהפכה לתרגיל הזה:

א. תהי f פונקציה ממשית גזירה (n+1) פעמים. הוכיחו, באמצעות אינטגרציה בחלקים, את הנוסחה הבאה לשארית של קירוב טיילור של f ב-0:

f(x) - \sum_{i=0}^{n} \frac{f^{(i)}(0)}{i!}x^i = \frac{1}{n!} \int_{0}^{x} f^{(n+1)}(t) (x-t)^n dt

ב. נסמן את השארית ב-R_n(x). נבחר את הפונקציה f(x) = (1+x)^{2n+1}. חשבו את \frac{R_n(1)}{2^{2n+1}} בשתי דרכים שונות (ישירות ובאמצעות הסעיף הקודם) והסיקו ש-C = \sqrt{2\pi}.

8. שיטת לפלס

1. מבוא

לפלס המציא ב-1774 שיטה כללית לקירוב פונקציות מהצורה h(t)=\int_{a}^{b}e^{tf(x)}g(x)dx עבור t גדול, כאשר f גזירה פעמיים (לפחות).
הרעיון הוא שכאשר t שואף לאינסוף, רוב הערך של h מתקבל סביב הנקודות בהן f מקבלת מקסימום גלובאלי. באיזור נקודות אלו אפשר לקרב את f(x) ע"י פונקציה ריבועית סביב נקודת המקסימום. אם x_0 נקודה כזו, הקירוב נראה כך:

f(x)=f(x_{0})+f'(x_{0})(x-x_{0})+\frac{f''(x_{0})}{2}(x-x_{0})^{2}+o((x-x_{0})^{2})

נשים לב ש-f'(x_{0})=0 כי x_{0} נקודת מקסימום, וש-f''(x_{0})<0 מאותה סיבה, ואינטואיטיבית עשינו רדוקציה לבעיה \int e^{-Ctx^{2}}g(x)dx עבור C<0 . בשביל לפתור אותה אפשר להשתמש בנוסחאות של המומנטים של התפלגות נורמלית:

\int_{\mathbb{R}}e^{-x^{2}/2}x^{k}dx=\sqrt{2\pi}\cdot\begin{cases} 0 & 2\nmid k\\ (k-1)(k-3)\cdots3\cdot1 & 2|k \end{cases}

2. שימוש עבור פונקציית גמא

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

נגדיר את פונקציית גמא: \Gamma(x)=\int_{0}^{\infty}e^{-t}t^{x-1}dt. אינטגרציה בחלקים מראה ש-\Gamma(x+1)=x\Gamma(x), לכן באינדוקציה: \Gamma(n+1)=n!\Gamma(1)=n!. אם נקרב את \Gamma(n+1), בעצם נקרב את n!. על כן נתנפל על האינטגרל תכף ומיד:

\Gamma(n+1) = \int_{0}^{\infty}e^{-x}x^{n}dx = \int_{0}^{\infty}e^{-x+n\ln x}dx

נגזור את h(x)=-x+n\ln x ונקבל ש-h'(x)=-1+\frac{n}{x}, כלומר h מקבלת מקסימום גלובאלי ב-x=n. לשם נוחות החישובים בהמשך, נזיז את הפונקציה כך שהמקסימום יתקבל ב-0:

\Gamma(n+1) = \int_{-n}^{\infty}e^{-x-n+n\ln(x+n)}dx = e^{-n}\int_{-n}^{\infty}e^{-x+n\ln(x+n)}dx

בשביל להפעיל את שיטת לפלס אנחנו צריכים שבאינטגרנד תהיה חזקה n-ית של פונקציה, לכן נציב x=ny:

\Gamma(n+1) = ne^{-n}\int_{-1}^{\infty}e^{-ny+n\ln n+n\ln(1+y)}dy = n^{n+1}e^{-n}\int_{-1}^{\infty}e^{n(-y+\ln(1+y))}dy

הפונקציה f(y)=-y+\ln(1+y) מתאפסת ב-0, וכך גם נגזרתה, והיא מקבלת שם מקסימום גלובאלי. פיתוח טיילור מראה ש-f(y)=-\frac{1}{2}y^{2}+o(y^{2}). זה מתאים לשיטת לפלס – נרצה לעשות את הדבר הבא:

\begin{array}{lcl} \int_{-1}^{\infty}e^{nf(y)}dy & \sim & \int_{-1}^{\infty}e^{-\frac{n}{2}y^{2}}dy \\  \left[ y=t/\sqrt{n} \right] &=& \frac{1}{\sqrt{n}}\int_{-\sqrt{n}}^{\infty}e^{-t^{2}/2}dt \\  & \sim & \frac{1}{\sqrt{n}}\int_{\mathbb{R}}e^{-t^{2}/2}dt \\  & = & \frac{1}{\sqrt{n}}\sqrt{2\pi} \end{array}

ולקבל:

\begin{array}{lcl} n! &=& \Gamma(n+1) \\  & = & n^{n+1}e^{-n}\int_{-1}^{\infty}e^{nf(y)}dy \\  & \sim & n^{n+1}e^{-n}\sqrt{\frac{2\pi}{n}} \\  & = & (\frac{n}{e})^{n}\sqrt{2\pi n} \end{array}

נותר להצדיק את המעבר \int_{-1}^{\infty}e^{nf(y)}dy\sim\sqrt{\frac{2\pi}{n}}, אבל קודם נמשיך לקצור פירות.

נשים לב שהקירוב הזה נכון גם לערכים לא שלמים של n – קירבנו את פונקציית גמא (פונקציה במשתנה ממשי), וזה עניין שימושי כי היא מופיעה בהרבה מקומות, כמו במשוואה הפונקציונאלית של פונקציית זטא.

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

את מה שהוכחנו עבור f ספציפית אפשר להכליל באופן הבא:

\int_{\mathbb{R}} e^{tf(x)}dx \sim e^{tf(0)} \sqrt{\frac{2\pi}{-tf''(0)}}

כאשר t שואף לאינסוף. מה שנדרש מ-f זה (רשימת מכולת לפניכם): שהיא תקבל מקסימום גלובאלי ב-0, תהיה גזירה בסביבת 0 וגזירה פעמיים ב-0 וערך הנגזרת שם יהיה שלילי, ושיהיו קיימים b,c חיוביים כך ש-f(x) \le -b כאשר |x| \ge c (דרישה שמתקיימת אוטומטית אם f הולכת למינוס אינסוף כש-|x| \to \infty).

3. הצדקה מתמטית

כדי להצדיק את המעבר \int_{-1}^{\infty}e^{nf(y)}dy\sim\sqrt{\frac{2\pi}{n}} נצטרך להכניס אפסילונטיקה. יהי \varepsilon>0 קטן. אבחר \delta\in(0,1) קטן מספיק כך ש-|f(y)-(-\frac{1}{2}y^{2})|<\varepsilon y^{2} עבור -\delta\le y \le \delta.

כעת אפרק את האינטגרל \int_{-1}^{\infty}e^{nf(y)}dy לשני חלקים:

\int_{-1}^{\infty}e^{nf(y)}dy=\int_{-\delta}^{\delta}+(\int_{\delta}^{\infty}+\int_{-1}^{-\delta})

החלק הראשון יהיה משמעותי והשני זניח.

1. בגלל ש-f יורדת ב-[0,\infty), מתקיים:

\int_{\delta}^{\infty}\le e^{(n-1)f(\delta)}\int_{\delta}^{\infty}e^{f(y)}dy\le e^{(n-1)f(\delta)}\int_{0}^{\infty}e^{f(y)}dy=O(e^{nf(\delta)/2})

חלק זה דועך מעריכית כי f שלילית עבור \delta>0.

בדומה:

\int_{-1}^{-\delta}\le e^{(n-1)f(-\delta)}\int_{-1}^{-\delta}e^{f(y)}dy\le e^{(n-1)f(-\delta)}\int_{0}^{\infty}e^{f(y)}dy=O(e^{nf(-\delta)/2})

סה"כ: \int_{-1}^{-\delta}+\int_{\delta}^{\infty}=O(e^{nC_{\delta}}),C_{\delta}<0.

2. מבחירת \delta, מתקיים:

\int_{-\delta}^{\delta}e^{-\frac{n}{2}y^{2}(1+2\varepsilon)}dy\le\int_{-\delta}^{\delta}\le\int_{-\delta}^{\delta}e^{-\frac{n}{2}y^{2}(1-2\varepsilon)}dy

שני האינטגרלים האלה הם מסדר גודל לפחות \frac{C}{\sqrt{n}} (אפשר לראות זאת למשל ע"י שינוי משתנים y'=\sqrt{n}y), ולכן החלק \int_{\delta}^{\infty}+\int_{-1}^{-\delta} אכן זניח. עכשיו נעשה את זה פורמלית.

3. מתקיים, עבור n גדול מספיק:

\begin{array}{lcl}\int_{-1}^{\infty}e^{nf(y)}dy &\le & \int_{-\delta}^{\delta}e^{-\frac{n}{2}y^{2}(1-2\varepsilon)}dy+O(e^{nC_{\delta}}) \\  \left[ z = y\sqrt{n(1-2\varepsilon)} \right] &=& \frac{1}{\sqrt{n(1-2\varepsilon)}}\int_{-\sqrt{n}\sqrt{1-2\varepsilon}\delta}^{\sqrt{n}\sqrt{1-2\varepsilon}\delta}e^{-z^{2}/2}dz+O(e^{nC_{\delta}}) \\  & \le &\frac{\sqrt{2\pi}}{\sqrt{n(1-2\varepsilon)}}+O(e^{nC_{\delta}}) \end{array}

נבחר \varepsilon שתלוי ב-n ושואף ל-0 כש-n\to\infty, אבל נגביל את הקצב שלו כך ש--C_{\delta} \ge \frac{2}{3}\frac{\ln n}{n} (הדרישה הזו נותנת את השיוויון e^{nC_{\delta}}=o(\frac{1}{\sqrt{n}}).) השתכנעו בקיומו של כזה \varepsilon – חשבו על -C_{\delta} כפונקציה מונוטונית ורציפה ב-\varepsilon ששואפת לאפס מלמעלה כש-\varepsilon שואף לשם.

כך נקבל: \limsup\int_{-1}^{\infty}e^{nf(y)}dy/\sqrt{\frac{2\pi}{n}}\le1.

נחשב חסם תחתון כעת:

\begin{array}{lcl} \int_{-1}^{\infty}e^{nf(y)}dy \ge \int_{-\delta}^{\delta} \\  & \ge & \int_{-\delta}^{\delta}e^{-\frac{n}{2}y^{2}(1+2\varepsilon)}dy \\  \left[ z = \sqrt{n(1+2\varepsilon)}y \right] & = & \frac{1}{\sqrt{n(1+2\varepsilon)}}\int_{-\sqrt{n}\sqrt{1+2\varepsilon}\delta}^{\sqrt{n}\sqrt{1+2\varepsilon}\delta}e^{-z^{2}/2}dz \\  & \ge & \frac{1}{\sqrt{n(1+2\varepsilon)}}\int_{-\sqrt{n}\delta}^{\sqrt{n}\delta}e^{-z^{2}/2}dz \end{array}

גם פה, נבחר \varepsilon שתלוי ב-n ושואף ל-0 כש-n\to\infty, אבל נגביל אותו כך ש-\sqrt{n}\delta\to\infty. (שוב, השתכנעו בקיומו של כזה \varepsilon.) נקבל: \liminf\int_{-1}^{\infty}e^{nf(y)}dy/\sqrt{\frac{2\pi}{n}}\ge1

סה"כ קיבלנו ש-\int_{-1}^{\infty}e^{nf(y)}dy/\sqrt{\frac{2\pi}{n}} שואף ל-1. \blacksquare

4. דוגמא מרובת משתנים

אין סיבה שאותו רעיון לא יעבוד למקרה הרב-מימדי. אצטט את התוצאה הכללית ללא הוכחה, כי הרעיונות לא חדשים: תהי F(t) = \int_{C} e^{tf(x_1, \cdots,x_n)} dx_1 \cdots dx_n פונקציה שאנחנו מעוניינים לקרב (C לצורך העניין תיבה המכילה את הראשית). נניח ש-f מתאפסת בראשית ושזה מקסימום גלובאלי שלה, ושהיא גזירה פעמיים וברציפות בסביבת הראשית. לכן נוכל לקרב את f בסביבת הראשית ע"י קירוב ריבועי: f = -\frac{1}{2} \sum_{1 \le i,j \le n} a_{i,j} x_i x_j + o(\sum x_i^2) (כאשר a_{i,j} = a_{j,i} = -\frac{\partial^2 f}{\partial x_1 \partial x_2} (\vec{0}) אם i \neq j). נסמן את המטריצה של ה-a_{i,j} ב-A ונדרוש ממנה להיות מוגדרת חיובית.

תחת תנאים סבירים אלו,

F(t) \sim t^{-\frac{n}{2}} \int_{\mathbb{R}^{n}} e^{-\frac{1}{2} \sum a_{i,j} x_i x_j} dx_1 \cdots dx_n

למה שווה אינטגרל זה? (2\pi)^{n/2} (\det A)^{-1/2}. איך רואים זאת? עבור A אלכסונית זה מיידי. אחרת – מלכסנים את A (אפשרי כי היא סימטרית).

בואו נראה שימוש יפה. בפרק 4 חישבנו את ההסתברות של הילוך שיכור על \mathbb{Z}^{3} לחזור לראשית אחרי 2n צעדים, וקיבלנו 2^{-2n}\binom{2n}{n}\sum_{i+j+k=n}(3^{-n}\binom{n}{i,j,k})^{2}. חסמנו ביטוי זה מלמעלה ע"י \frac{C}{n^{1.5}} וטענו שזה הדוק (כלומר, שקיים חסם תחתון דומה). עכשיו הזמן להוכיח את זה (למעשה, נחקור בעיה זו עבור מימד כללי), עם פונקציות יוצרות ושיטת לפלס רב-מימדית. נעשה זאת בכמה שלבים – השניים הראשונים יהיו לכתוב את הההסתברות בתור אינטגרל, והארבעה האחרונים יהיו לחקור את האינטגרנד מבחינת נקודות קיצון ולהפעיל על האינטגרל את את שיטת לפלס. כרגיל, אתן לכם לוודא חלק מהפרטים, או שתאלצו להאמין לי (לרוב החלטה לא חכמה).

1. נגדיר פולינום לורן (פולינום עם חזקות שליליות):

f(x_{1},\cdots,x_{d})=\frac{1}{2d}(\sum_{j=1}^{d}x_{j}+\sum_{j=1}^{d}x_{j}^{-1})

המקדם החופשי של f^{2n} הוא בדיוק ההסתברות שהילוך מקרי על \mathbb{Z}^{d} שמתחיל בראשית יחזור לראשית בזמן 2n.

2. כשמציבים x_{j}=e^{iy_{j}} מקבלים את הפולינום הטריגונומטרי g(y_{1},\cdots,y_{d})=\frac{1}{d}\sum_{j=1}^{d}\cos(y_{j}). אנחנו רוצים את המקדם החופשי של g^{2n}, שלשמחתנו אפשר להביעו בעזרת האינטגרל (\frac{1}{2\pi})^{d}\int_{[-\pi,\pi]^{d}}g^{2n}dy_{1}dy_{2}\cdots dy_{d}. למה? כי \frac{1}{2\pi} \int_{-\pi}^{\pi} e^{ik\theta} d\theta = \delta_{k,0}.

3. ל-g^{2n} יש 3 נקודות מקסימום גלובאלי ב-[-\pi,\pi]^{d}, בהן היא מקבלת את הערך 1: (0,\cdots,0),(-\pi,\cdots,-\pi),(\pi,\cdots,\pi), ונצפה שהמשקל העיקרי של האינטגרל יהיה סביבן. הבעיה היא שהנקודות (-\pi,\cdots,-\pi),(\pi,\cdots,\pi) הן נקודות קצה של הקבוצה שלנו, וזה מסבך הכל. נעשה את הטריק הפשוט הבא: נחליף את הקבוצה עליה עושים אינטגרציה בהזזה שלה ב-(\frac{\pi}{2},\cdots,\frac{\pi}{2}), כלומר ב-[-\frac{\pi}{2},\frac{3\pi}{2}]^{d}. האינטגרל לא משתנה כי g^{2n} מחזורית בכל קואורדינטה עם מחזור \pi. מה שכן משתנה הוא נקודות המקסימום – במקום 3 יש רק 2, כי (-\pi,\cdots,-\pi) "התאחדה" עם (\pi,\cdots,\pi). שתי הנקודות, \vec{0} ו-(\pi,\cdots,\pi) הן כעת נקודות פנימיות, מעולה.

4. נשים לב ש-g^{2n} אינווריאנטית להזזה ב-(\pi,\cdots,\pi), ולכן התרומה של 2 נקודות הקיצון היא זהה.

5. בשביל להפעיל את שיטת לפלס על g^{2n} = e^{2n \ln g}, נרצה להבין מה הוא קירוב טיילור של \ln g סביב הראשית. אפשר להבין אותו בעזרת כמה מניפולציות נחמדות:

g(y)=\frac{1}{d}\sum(1-2\sin^{2}(\frac{y_{i}}{2}))\sim1-\frac{||y||^{2}}{2d}\sim e^{-||y||^{2}/2d}

6. משיטת לפלס מקבלים שכאשר n \to \infty מתקיים:

P(S_{2n}=0) \sim 2(\frac{d}{4\pi n})^{d/2}

עבור d=3 מקבלים את הטענה הלא מוכחת שלנו לגבי הילוך תלת-מימדי. \blacksquare

הערה 7: אם נכתוב את התוצאה בתור (\frac{1}{2})^{d-1}(\frac{d}{n\pi})^{d/2}, אפשר לתת לה הסבר היוריסטי. נניח שהלכנו בהילוך מקרי 2n צעדים. מחוק המספרים הגדולים, רוב הסיכויים שהלכנו בערך אותה כמות צעדים בכל ציר, כלומר \frac{2n}{d} צעדים בציר ה-i . כדי שנגיע לאפס בסוף, הכרחי שכמות הצעדים בכל ציר תהיה זוגית. זה קורה בהסתברות (\frac{1}{2})^{d-1} – ההסתברות ללכת מספר זוגי של צעדים בציר מסויים היא \frac{1}{2}, ואם זה נכון ל-d-1 צירים מתוך d, זה נכון גם בציר האחרון (כי מספר הצעדים הכולל הוא זוגי). נותר להסביר את (\frac{d}{n\pi})^{d/2}, וגם זה אפשרי.

הבנו כבר שיש לנו בעצם d הילוכים מקרים חד-מימדיים באורך זוגי מסדר גודל \frac{2n}{d}. ראינו שהסיכוי שהילוך כזה יחזור לראשית בסוף הוא \sqrt{\frac{1}{\pi(n/d)}}. נעלה את זה בחזקת d ונקבל את הגורם הלא מוסבר.

5. תרגילים

תרגיל 1 (סכום מתחלף)

חשבו קירוב אסימפטוטי לסכום מהפוסט הקודם: S(s,n)=\sum_{k=0}^{2n}(-1)^{k+n}\binom{2n}{k}^{s}. נניח ש-s \ge 2.

1. הראו שסכום זה הוא המקדם החופשי בפולינום לורן הבא:

(-1)^{n}\prod_{i=1}^{s-1}(1+z_{i})^{2n}(1-(z_{1}\cdots z_{s-1})^{-1})^{2n}

2. הציבו z_{j}=\exp(2i\phi_{j}) והראו שהוא שווה לאינטגרל הבא:

2^{2ns}\pi^{1-s}\int_{[-\pi/2,\pi/2]^{s-1}}(\cos\phi_{1}\cdots\cos\phi_{s-1}\sin(\phi_{1}+\cdots+\phi_{s-1}))^{2n}d\phi

3. חקרו את הפונקציה G(\phi_{1},\cdots,\phi_{s-1})=\cos\phi_{1}\cdots\cos\phi_{s-1}\sin(\phi_{1}+\cdots+\phi_{s-1}). הראו של-G^2 יש שתי נקודות מקסימום גלובאליות, והן \phi_{1}=\cdots=\phi_{s-1}=\pm\frac{\pi}{2s}. היא שווה בהן ל-\cos(\frac{\pi}{2s})^{2s}.

4. חקרו את האינטגרל באיזור הנקודה החיובית: \vec{m}=(\frac{\pi}{2s},\cdots,\frac{\pi}{2s}) (בנקודה השנייה זה זהה). אם תחשבו קירוב טיילור ריבועי של \ln(G/G(\vec{m})) סביב \vec{m} תגלו שאין גורם חופשי (כי חילקנו ב-G(\vec{m})) ואין גורמים לינאריים (כי \vec{m} נקודת קיצון).

לכן מקבלים ש-G^{2n}=G^{2n}(\vec{m})\exp(2n\cdot h), כאשר h(\phi_{1}+\frac{\pi}{2s},\cdots,\phi_{s-1}+\frac{\pi}{2s})=-\frac{1}{2}\langle A\phi,\phi\rangle+o(||\phi||^{2}).

5. חשבו את התבנית הריבועית A, והראו שהיא שווה ל-\cos^{-2}(\frac{\pi}{2s})\cdot(J+I), כאשר J המטריצה שכולה אחדות. הראו ש-A מוגדרת חיובית עם דטרמיננטה s\cos^{-2(s-1)}(\frac{\pi}{2s}).

6. השתמשו בשיטת לפלס כדי לקבל:

S(s,n)\sim(2\cos(\frac{\pi}{2s}))^{2ns+s-1}2^{2-s}(\pi n)^{\frac{1}{2}(1-s)}s^{-\frac{1}{2}}

כאשר s \ge 2 קבוע ו-n שואף לאינסוף.

7. ודאו ש-S(3,n)\sim\binom{3n}{n,n,n}, וש-S(4,n) לא אסימפטוטי ל-\binom{4n}{n,n,n,n}.

9. (מתקדם – רשות) שיטת היימן

1. קירוב סטירלינג דרך נוסחת קושי ושיטת לפלס

לפעמים אפשר לחלץ אינפורמציה על סדרה a_n באמצעות הפונקציה היוצרת שלה. הפונקציה היוצרת של n! בעלת רדיוס התכנסות אפס, אבל הפונקציה היוצרת של \frac{1}{n!} היא e^x – פונקציה שמתכנסת בכל המישור המרוכב ("פונקציה שלמה"). נשתמש בה.

אם F(z)=\sum_{i\ge0}a_{i}z^{i} בעלת רדיוס התכנסות R, מקבלים מנוסחת קושי:

a_{k}=\frac{1}{2\pi i}\int_{C}\frac{F(z)}{z^{k+1}}dz

כאשר האינטגרציה היא על מעגל בעל רדיוס r (קטן מ-R) סביב הראשית במישור המרוכב.
זה נובע מכך ש:

\int_{C}z^{k}dz = \begin{cases} 0 & k\neq-1\\ 2\pi i & k=-1 \end{cases}

תוצאה זו נקראת "משפט השארית" (הוא יותר כללי אבל שקול), ואפשר להוכיחה באמצעות חישוב ישיר ע"י הפרמטריזציה z=re^{i\theta}. כאשר F(z)=e^{z} מקבלים:

\begin{array}{lcl} \frac{1}{n!} &=& \frac{1}{2\pi i}\int_{C}\frac{e^{z}dz}{z^{n+1}} \\  &=& \frac{1}{2\pi r^n}\int_{-\pi}^{\pi}e^{re^{i\theta} - in\theta} d\theta \end{array}

אפשר להשתמש באי-שיוויון המשולש כדי לקבל חסם תחתון על n!|e^{re^{i\theta} - in\theta}| =e^{r \cos\theta} \le e^{r}, ולכן \frac{1}{n!}\le\frac{1}{2\pi r^n}\int_{-\pi}^{\pi}e^r d\theta=\frac{e^{r}}{r^{n}}, כלומר n!\ge\frac{r^{n}}{e^{r}}. ה-r שממקסם את המנה הוא r=n, ומקבלים חסם שקיבלנו כבר (בדרך מאוד דומה): n!\ge(\frac{n}{e})^{n}.

עם אנליזה עדינה יותר אפשר לחשב לקרב את האינטגרל בצורה מדויקת בהרבה. נחזור לשיוויון |e^{re^{i\theta}}|=e^{r\cos\theta}. הוא בעצם אומר שהחלק העיקרי של האינטגרל מתקבל כש-\cos\theta קרוב ל-1.

אפשר לפרמל זאת ע"י פירוק האינטגרל, בדומה לשיטת לפלס: אחד עבור הסביבה |\theta|\le\delta (החלק העיקרי, ובו אפשר להשתמש בקירוב טיילור מסדר שני) ושני עבור השאר, והוא יהיה זניח אקספוננציאלית לעומת החלק הראשון. קודם נחשב את החלק העיקרי, ואז נראה שהשאר זניח כמו שטענתי. הנימוקים יהיו מעט קלים יותר משיטת לפלס, כי כל הפונקציות יהיו אנליטיות, ובפרט גזירות ברציפות 3 פעמים, מה שמאפשר לכתוב את השגיאה בקירוב טיילור מסדר שני בתור O(x^3) במקום o(x^2).

נבחר r=n. למה? כי כך המקדם של \theta בטור f(\theta) = re^{i\theta} - in\theta  יתאפס ונקבל מצב דומה לשיטת לפלס. מקבלים:

\begin{array}{lcl} \frac{1}{n!} &=& \frac{1}{2\pi}\int_{-\pi}^{\pi}\frac{e^{ne^{i\theta}}d\theta}{n^{n}e^{in\theta}} \\  &= & \frac{1}{2\pi n^{n}} (\int_{-\delta}^{\delta}e^{n(e^{i\theta}-i\theta)}d\theta + (\int_{-\pi}^{-\delta}e^{n(e^{i\theta}-i\theta)}d\theta+ \int_{\delta}^{\pi}e^{n(e^{i\theta}-i\theta)}d\theta)) \end{array}

נטפל קודם באינטגרל הראשון. מתקיים ש-e^{i\theta}-i\theta=1-\frac{\theta^{2}}{2}+O(\theta^{3}). כדי להחליף את e^{n(e^{i\theta}-i\theta)}=e^{n(1-\frac{\theta^{2}}{2}+O(\theta^{3}))} ב-e^{n(1-\frac{\theta^{2}}{2})}, צריך ש-n\theta^{3} ידעך, כלומר \delta=o(n^{-1/3}). תחת הנחה זו,

\begin{array}{lcl} \int_{-\delta}^{\delta} e^{n(e^{i\theta} - i\theta)} d\theta & = &  \int_{-\delta}^{\delta} e^{n(1-\frac{\theta^{2}}{2})} e^{o(1)} d\theta \\  & \sim & e^n \int_{-\delta}^{\delta} e^{-(\sqrt{n}\theta)^{2}/2} d\theta \\  & = & \frac{e^n}{\sqrt{n}} \int_{-\sqrt{n}\delta}^{\sqrt{n}\delta} e^{-z^{2}/2} dz \end{array}

אם \sqrt{n}\delta שואף לאינסוף, אז:

\begin{array}{lcl} \int_{-\sqrt{n}\delta}^{\sqrt{n}\delta}e^{-\theta^{2}/2}d\theta & \sim & \int_{-\infty}^{\infty}e^{-\theta^{2}/2}d\theta \\  &=& \sqrt{2\pi} \end{array}

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

n! \sim 2\pi n^n \frac{\sqrt{n}}{e^n} \frac{1}{\sqrt{2 \pi}} = (\frac{n}{e})^n \sqrt{2\pi n}

איך מראים זאת? ראינו שהאינטגרל הראשון אסימפטוטי ל-\frac{e^n}{\sqrt{n}} כפול קבוע. מחוץ לקטע [-\delta, \delta] יש לנו את החסם המעריכי  העליון e^{n \cos \delta} על האינטגרנד, ולכן 2 האינטגרלים האחרונים חסומים מלמעלה ע"י 2(\pi - \delta)e^{n \cos \delta}, כלומר O(e^{n} e^{-n(1-\cos \delta)} ). אנחנו רוצים ש-e^{-n(1-\cos \delta)} = o(\frac{1}{\sqrt{n}}). נשתמש באי-שיוויון 1- \cos \delta \ge 0.2 \delta^2 שמתקיים ב-[-\pi, \pi], ונדרוש משהו חזק בהרבה, פשוט כי אפשר: n\delta^2 \ge n^{0.1}.

איזה דלתא נבחר בפועל? \delta=n^{-5/12} לדוגמא, כי כך יתקיימו כל האילוצים שדרשנו. \blacksquare

2. המקרה הכללי

Hayman הכליל את האנליזה שעשינו כך שהיא תעבוד לכמה שיותר פונקציות. אפרט על חלק מהתוצאות שהוא פירסם ב-1956 במאמר מקיף שנקרא "A Generalisation of Stirling's Formula".

נניח ש-f(z) = \sum a_i z^i פונקציה אנליטית עם רדיוס התכנסות R (אולי אינסוף) ואנחנו רוצים לחלץ מידע אסימפטוטי על המקדמים. נתחיל עם אינטגרל שנובע מנוסחת קושי, כמו שעשינו בסטירלינג:

a_n = \frac{1}{2\pi r^n} \int_{-\pi}^{\pi} \frac{f(re^{i \theta})}{e^{ni\theta}} d\theta

כדי לעשות אנליזה אנלוגית לאנליזה הקודמת, נמצא g כך ש-f=e^g (לרוב f תהיה נתונה בצורה זו מלכתחילה). לפעמים g מוגדרת עד כדי כפולה של 2\pi i ואין עם זה בעיה, כי אנחנו מסתכלים על e^g. נקבל:

a_n = \frac{1}{2\pi r^n} \int_{-\pi}^{\pi} e^{g(re^{i \theta})-ni\theta} d\theta

עכשיו נרצה לפתח את g(re^{i \theta}) כטור טיילור של \theta, ולבחור r כך שהגורם הלינארי בפיתוח יתבטל עם n i \theta (כמו שקודם בחרנו r =n). מפורשות:

g(re^{i \theta}) = g(r) + ia(r)\theta - \frac{b(r)}{2} \theta^2 + O(\theta^3)

כאשר:

a(r) = \frac{d(g(re^{i \theta}))}{d\theta} = \frac{d(\ln f(re^{i \theta}))}{d\theta} = ir\frac{f'(r)}{f(r)}

b(r) = -\frac{d^2(g(re^{i \theta}))}{d^2 \theta} = -\frac{d^2(\ln f(re^{i \theta}))}{d\theta} = r \frac{f f' + rf'' r - f'^2 r}{f^2}

(ודאו את החישובים.) כדי שהגורם הלינארי יתבטל עם הגורם הלינארי הקיים, נדרש ש-a(r) = n.  תחת תנאים מסויימים שנפרט בהמשך, נובע ש-a מונוטונית עולה ושואפת לאינסוף כש-r שואף ל-R, ולכן ל-n גדול מספיק יהיה פיתרון למשוואה, נסמנו r_n. מקבלים:

\begin{array}{lcl} a_n &=& \frac{e^{g(r_n)}}{2\pi r_n^n} \int_{-\pi}^{\pi} e^{-\frac{\theta^2}{2}b(r) + O(\theta^3)} d\theta \\  &=& \frac{f(r_n)}{2\pi r_n^n} \frac{1}{\sqrt{b(r_n)}}\int_{-\frac{\pi}{b(r_n)}}^{\frac{\pi}{b(r_n)}} e^{-\frac{z^2}{2} + O(\frac{z^3}{b(r_n)^{1.5}})} dz \end{array}

היינו רוצים להגיד שהאינטגרנד מספיק קרוב לגאוסיאן ושקטע האינטגרציה שואף להיות כל הישר (כלומר b(r_n) \to \infty) ולקרב אותו ע"י \sqrt{2\pi}, ואז התוצאה הסופית היא:

a_n \sim \frac{f(r_n)}{r_n^n \sqrt{2\pi b(r_n)}}

וזו נוסחה אנלוגית לנוסחת סטירלינג.

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

התנאים שהיימן הגדיר הם (בפועל התנאים כלליים אף יותר), בנוסף לכך ש-f אנליטית עם רדיוס התכנסות R:

1. f מקבלת ערכים ממשיים על הממשיים (בתחום התכנסותה). בנוסף, קיים r ממשי (קטן מ-R) כך ש-R> r'>r \implies f(r') > 0.

2. קיימת פונקציה \delta מהחיוביים ל-[0, \pi], כך ש:

i. f(re^{i\theta}) \sim f(r) e^{i \theta a(r) - \frac{b(r) \theta^2}{2}} באופן אחיד עבור |\theta | \le \delta(r) כאשר r \to R^{-}.

ii. f(re^{i \theta}) = o(\frac{f(r)}{\sqrt{b(r)}}) באופן אחיד עבור \delta(r) \le |\theta| \le \pi כאשר r \to R^{-}.

(תנאי זה מאפשר לפצל את האינטגרל לסכום של 2 אינטגרלים – על [-\delta(r), \delta(r)] ועל המשלים, ולהראות שהשני זניח לעומת הראשון.)

3. \lim_{r \to R^{-}} b(r) = \infty.

ניתן להראות שעבור פונקציות כאלו המקסימום על המעגל re^{i\theta} מתקבל ב-r, תכונה שהיימן גם ניצל בהוכחה של נכונות הקירוב. כאמור, כל התכונות הנ"ל נדרשות כדי שהוכחה שלנו תוכל להפוך לריגורוזית. אתן לכם לחשוב על המשמעות של התנאים השונים ולשחזר את ההוכחה (תשוו לדוגמא שפתרנו בתחילת הפרק).

לפונקציות שמקיימות את כל התכונות הללו היימן קרא "מתאימות-היימן". הוא הראה שאם f מתאימה אז גם e^f. בנוסף, מכפלה של מתאימות היא מתאימה. עוד משפחה היא e^P, כאשר P פולינום עם מקדמים חיוביים. יש עוד המון משפחות.

המשפט הכללי נותן את סטירלינג באופן מיידי: הפונקציות יוצאות a(r) = r, b(r) = r, ומקבלים r_n=n. מציבים בנוסחה ומסיימים. ניתן דוגמא פחות טריוויאלית:

3. דוגמת האינבולוציות

תהי \exp(x+\frac{x^{2}}{2}) הפונקציה היוצרת האקספוננציאלית של מספר הפרמוטציות עם מעגלים בגודל 1 או 2 (כלומר אינבולוציות): \exp(x+\frac{x^{2}}{2})=\sum_{n\ge0}\frac{a_{n}}{n!}x^{n}, ו-a_n סופרת את האינבולוציות.

כדי להפעיל את שיטת היימן, נחשב את a,ba(r)=r(1+r),b(r)=r(1+2r).

כעת צריך לפתור את המשוואה a(r_{n})=r_{n}(1+r_{n})=nומקבלים:

r_{n}=\frac{-1+\sqrt{1+4n}}{2}=\sqrt{n}-\frac{1}{2}+O(n^{-1})

נעשה עוד שני חישובי עזר:

r_{n}+\frac{r_{n}^{2}}{2}=\frac{-1+2n+\sqrt{1+4n}}{4}=\frac{\sqrt{n}}{2}+\frac{n}{2}-\frac{1}{4}+O(n^{-1})

b(r_{n})=2n-r_{n}=2n+O(\sqrt{n})

כעת כל מה שנותר הוא להציב בנוסחה:

\begin{array}{lcl} \frac{a_{n}}{n!} & \sim & \frac{\exp(r_{n}+\frac{r_{n}^{2}}{2})}{\sqrt{2\pi b(r_{n})}r_{n}^{n}} \\  &= & \frac{\exp(\frac{\sqrt{n}}{2}+\frac{n}{2}-\frac{1}{4}+O(n^{-1}))}{\sqrt{2\pi b(r_{n})}(\sqrt{n}-\frac{1}{2}+O(n^{-1}))^{n}}\implies \\  a_{n}& \sim & (\frac{n}{e})^{n}\sqrt{2\pi n}\frac{1}{\sqrt{4\pi n+O(\sqrt{n})}}\frac{\exp(\frac{\sqrt{n}}{2}+\frac{n}{2}-\frac{1}{4}+O(n^{-1}))}{(\sqrt{n}-\frac{1}{2}+O(n^{-1}))^{n}} \\  & \sim & (\frac{n}{e})^{n}\frac{1}{\sqrt{2}}e^{-1/4}\frac{\exp(n/2)}{\sqrt{n}^{n}}\frac{\exp(\frac{\sqrt{n}}{2}+O(n^{-1}))}{(1-\frac{1}{2\sqrt{n}}+O(n^{-3/2}))^{n}} \\  & \sim & \frac{1}{(4e)^{1/4}}(\frac{n}{e})^{n/2}\frac{\exp(\frac{\sqrt{n}}{2}+O(n^{-1}))}{(1-\frac{1}{2\sqrt{n}}+O(n^{-3/2}))^{n}} \\  & \sim & \frac{1}{(4e)^{1/4}}(\frac{n}{e})^{n/2}\exp(\frac{\sqrt{n}}{2}+O(n^{-1})-n\ln(1-\frac{1}{2\sqrt{n}}+O(n^{-3/2})) \\  & \sim & \frac{1}{(4e)^{1/4}}(\frac{n}{e})^{n/2}\exp(\sqrt{n})\exp(O(n^{-1/2})) \end{array}

כלומר a_{n}\sim(\frac{n}{e})^{n/2}\frac{e^{\sqrt{n}}}{(4e)^{1/4}}. \blacksquare

את הדוגמה הקשוחה באמת אתן כתרגיל.

4. תרגילים

תרגיל 1 (מספרי Bell)

מספר Bell ה-n-י, המסומן B_n, סופר כמה חלוקות יש לקבוצה בגודל n. לדוגמא, לקבוצה בגודל 3 יש 5 חלוקות:

\{ \{ 1, 2, 3\} \} , \{ \{1 \}, \{2\}, \{ 3\}\}

\{ \{1 \}, \{2,3\} \} , \{ \{ 2 \}, \{ 1,3\} \}, \{ \{3 \} , \{ 1,2 \} \}

א. הראו שהפונקציה האקספוננציאלית היוצרת של מספרי בל היא \exp( \exp(x) -1).

ב. השתמשו בשיטת Hayman כדי להראות ש-

B_n \sim \frac{1}{\sqrt{n}} \lambda(n)^{n+\frac{1}{2}} e^{\lambda(n)-n-1}

כאשר \lambda מקיימת את המשוואה הסתומה \lambda(n) \ln \lambda(n) = n.

10. סיכום

1. מילות פרידה

הספקנו הרבה.

בהתחלה השתמשנו בכלים ממש בסיסיים כדי להראות ש-n^{n}>n!>(\frac{n}{e})^{n} (בתרגילים אפילו שיפרנו זאת עוד, עדיין עם שיטות אלמנטריות). אח"כ הבנו שהבעיה כאן היא קירוב של סכום ע"י אינטגרל, וניסינו להבין איך לעשות זאת בצורה טובה. בניסיון הראשון הצלחנו להראות ש-n! = (\frac{n}{e})^nn^{O(1)}, ובהמשך השתכללנו והשתמשנו בכלל הטרפז שנתן לנו את הקירוב הנכון, עד כדי חישוב הקבוע. הרחבנו על שיטת אוילר-מקלורן שנותנת איברים נוספים בקירוב האסימפטוטי של \ln (n!) ובאופן כללי של סכומים \sum_{i=1}^{n} f(i).

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

את הקבוע הסברנו בהרבה דרכים שבסופו של דבר כולן קשורות לכך שהאינטגרל של הגאוסיאן הוא \sqrt{2\pi}.

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

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

2. הערת סיום

יש ז'אנר שלם של הוכחות קצרות לקירוב, כמו שנוכחתם לדעת בתרגיל 3 בפרק 7. החלטתי גם אני להמציא הוכחה קצרה, ספציפית לכך שהגבול \lim_{n \to \infty} \frac{n!}{(\frac{n}{e})^n \sqrt{n} } קיים, חיובי וסופי.

נסמן f(n) = \frac{n!}{(\frac{n}{e})^n \sqrt{n}}. f(n) מתכנס לגבול חיובי אמ"מ \ln f(n) מתכנס, וזה שקול לכך שהטור \sum \ln \frac{f(n+1)}{f(n)} מתכנס. נחשב את האיבר הכללי שלו:

\frac{f(n+1)}{f(n)} = \frac{e}{(1+\frac{1}{n})^{n+0.5}} \implies

\begin{array}{lcl} \ln \frac{f(n+1)}{f(n)} & = & 1 - (n+0.5) \ln (1 +\frac{1}{n}) \\  & = & 1-(n+\frac{1}{2}) (\frac{1}{n} - \frac{1}{2n^2} + O(n^{-3}) ) \\  & = & 1-(1+O(n^{-2})) \\  & = & O(n^{-2}) \end{array}

ונובע שהטור מתכנס. \blacksquare

לקריאה נוספת:

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

2. הספר הנהדר "Asymptotic Methods in Analysis" של N. G. De Bruijn – דן בהרחבה בשיטת לפלס ובהכללה שלה, The Saddle Point Method.

3. "Principles of Random Walk" של Spitzer ו-"Random Walk: A Modern Introduction" של Lawler ו-Limic.

מקווה שנהנתם,

אופיר

מודעות פרסומת

אודות Ofir Gorodetsky

Graduate student at TAU. Can be contacted at bambaman1 at gmail dot com.
פוסט זה פורסם בקטגוריה אנליזה, חפירה. אפשר להגיע ישירות לפוסט זה עם קישור ישיר.

2 תגובות על מי מפחד מ-n עצרת?

  1. פינגבאק: תורת המספרים האנליטית | One and One

  2. משתמש אנונימי (לא מזוהה) הגיב:

    מעולה! תודה!!

להשאיר תגובה

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

הלוגו של WordPress.com

אתה מגיב באמצעות חשבון WordPress.com שלך. לצאת מהמערכת / לשנות )

תמונת Twitter

אתה מגיב באמצעות חשבון Twitter שלך. לצאת מהמערכת / לשנות )

תמונת Facebook

אתה מגיב באמצעות חשבון Facebook שלך. לצאת מהמערכת / לשנות )

תמונת גוגל פלוס

אתה מגיב באמצעות חשבון Google+ שלך. לצאת מהמערכת / לשנות )

מתחבר ל-%s