חסם צ'רנוף, חסם אנטרופיה ומה שביניהם

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

עולם הבעיה

אתם מטילים מטבע הוגן n פעמים. בתוחלת תצפו ל-\frac{n}{2} תוצאות פלי ו-\frac{n}{2} תוצאות עץ.

בואו ניקח מספר אמיתי – n = 2000. נניח ויצא לי עץ 1000 פעמים. מה ההסתברות לכך? \binom{2000}{1000} 2^{-2000}. אני אגלה לכם סוד: זה מספר קטן, אפילו שזו תוצאה סבירה – בדיוק התוחלת. אולי הסתברות זה לא המדד הנכון להסתכל עליו?
מסתבר שיש מדד מוצלח יותר והוא מספר סטיות התקן מהתוחלת. סטיית תקן היא שורש השונות: \sigma = \sqrt{E(X-EX)^2}. כל המידע מגולם במספר סטיות התקן מהתוחלת – זו יחידת המידה שלנו, ובמקום להסתכל על ההסתברות לאירוע הספציפי אפשר להסתכל על 'הסתברות הזנב', כלומר הסיכוי לקבל כמות סטיות כמו שקיבלנו או יותר.

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

תרגיל: חשבו תוחלת ושונות של משתנה בינומי:

E(\text{Binomial}(n,p)) = np
\text{Var}(\text{Binomial}(n,p))=np(1-p)

במקרה שלנו, מספר העצים הוא משתנה בינומי ולכן התוחלת של מספר העצים היא \frac{2000}{2} והשונות היא 2000 \frac{1}{2}(1-\frac{1}{2}) = 500.

התוצאה הספציפית של 1000 עצים היא בעלת מרחק 0 סטיות תקן מהתוחלת, כלומר – תוצאה מאוד לא מפתיעה.
ניקח מקרה אחר. אם יצאו 700 עצים, המרחק נהיה: \frac{1000 - 700}{\sqrt{500}} =13.41..., כלומר יותר מ-13 סטיות תקן מהתוחלת (מתחת לתוחלת). זה הרבה? זה מעט? נענה על שאלה זו בהמשך.

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

במקרה שלנו, ההסתברות הנדונה היא הסכום הבא:

P(\frac{\text{Binomial}(2000,\frac{1}{2}) - 1000}{\sqrt{500}} < -13) = 2^{-2000} \sum_{i=0}^{1000-\sqrt{500}\cdot 13} \binom{2000}{i}

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

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

טיזר: ניתן חסם לא רע בכלל לסכום \sum_{i=0}^{m} \binom{n}{i} שנתקלים בו לא מעט בקומבינטוריקה.

אבל לפני כן – נדון במשפט הגבול המרכזי (אם אתם מכירים – מומלץ לדלג):

משפט הגבול המרכזי

משפט הגבול המרכזי הוא תוצאה מדהימה במתמטיקה. נניח שנתונה לנו סדרה של משתנים מקריים \{ X_i \}_{i \ge 1} בלתי-תלויים ושווי התפלגות (לדוגמא: הטלות מטבע). בנוסף, נניח שיש להם תוחלת \mu סופית ושונות \sigma^2 גם כן סופית.

נרצה להבין את התפלגות הממוצע שלהם: M_n = \frac{\sum_{i \le n} X_i}{n}. השונות שלו שואפת לאפס: \text{Var}(M_n) = \frac{\sigma^2}{n} \to 0. כלומר הממוצע נהיה יותר ויותר מרוכז סביב התוחלת \mu = EM_n. זה התמריץ להוכחת חוק המספרים הגדולים, שאת ניסוחו המלא תמצאו כאן.

אז הממוצע עצמו לא אינפורמטיבי יותר מידי, לכן נסתכל על משהו מעט שונה – על הסכום מחולק בשורש n כפול סטיית התקן \sigma. אחרי נרמול זה מקבלים את  T_n = \frac{\sum_{i \le n} X_i}{\sigma \sqrt{n}}, משתנה מקרי בעל שונות קבועה השווה ל-1, כפי שהחישוב הבא מראה:

\text{Var}(T_n) = \frac{n}{n\sigma^2} \sigma^2 = 1

התוחלת שלו גדלה, אז ננרמל שנית באמצעות הזזה הפעם. נחסר מכל אחד מה-X_i את התוחלת ונחזור על התהליך, כלומר נגדיר \overline{X}_{n} = \frac{\sum_{i \le n} X_i - n\mu}{\sigma \sqrt{n}}. מה זה המשתנה הזה? משתנה בעל תוחלת 0 ושונות 1, שמודד את כמות סטיות התקן של X_1 + \cdots + X_n – זה המדד המעניין, בעצם! למדוד את המרחק מהתוחלת ביחידות של סטיית תקן.

למעשה, יש לנו אינסוף משתנים כאלו, בעלי תוחלת 0 ושונות 1: \{\overline{X}_n\}_{n \ge 1}. מעניין לשאול האם הם מתכנסים לאיזושהי התפלגות? התשובה המפתיעה היא: כן! ושהיא אפילו לא תלויה בהתפלגות המשותפת של ה-X-ים. התפלגות זו היא ההתפלגות הנורמלית, בעלת פונקציית הצפיפות \frac{e^{-x^2/2}}{\sqrt{2\pi}} (נקראת 'גאוסיאן'). ובניסוח מתמטי,

\lim_{n \to \infty} P(\overline{X}_n \in (a,b)) = P(\text{N}(0,1)\in (a,b)) = \frac{1}{\sqrt{2\pi}} \int_{a}^{b} e^{-x^2/2} dx

למי שלא מכיר או זוכר, פונקציית הצפיפות של משתנה נורמלי נראית כמו פעמון:

פונקציית הצפיפות של התפלגות נורמלית

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

P(\sum_{i=1}^{n} X_i > n\mu + k\sigma\sqrt{n}) \to^{n \to \infty} \frac{1}{\sqrt{2\pi}} \int_{-\infty}^{k} e^{-x^2/2} dx

בואו נבין איך זה עוזר לנו בבעיה שהתחלנו איתה. אפשר להסתכל על משתנה מקרי בינומי בתור סכום של אינדיקטורים של האירועים "בהטלה ה-i התקבל פלי".
אם נחסר מהתוצאה את התוחלת ונחלק בסטיית התקן של המשתנה הבינומי (שהיא \sqrt{n} כפול סטיית התקן של אינדיקטור בודד) נקבל את המשתנה \overline{X}_n.
ממשפט הגבול המרכזי, הביטוי שקיבלנו מקודם, P(\overline{X}_n > k), שואף ל-P(N(0,1) > k) = \frac{1}{\sqrt{2\pi}} \int_{-\infty}^{k} e^{-x^2/2} dx. מגניב – התפלגות סטיות התקן היא נורמלית (בגבול)!

התכנסות מסוג זה – \lim_{n \to \infty} P(X_n > k) \to P(X > k) – נקראת "התכנסות בהתפלגות". התוצאה ש-\overline{X}_{n} מתכנסת בהתפלגות למשתנה נורמלי N(0,1) נקראת משפט הגבול המרכזי.

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

\sup_{k} |P(N(0,1) > k) - P(\overline{X}_n > k)| < \frac{1}{\sqrt{n}}

לא נדבר עליו כאן, אתם מוזמנים לקרוא עליו בבלוג של טרי טאו. אבל גם אם פשוט נאמין שהאינטגרל הזה קרוב מספיק להסתברות שלנו, לא ברור איך לחשב אותו – הפונקציה e^{-x^2/2} היא לא פונקציה אלמנטרית, כלומר אין לה פונקציה קדומה "פשוטה".

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

\frac{1}{\sqrt{2\pi}}\int_{k}^{\infty}e^{-x^{2}/2}dx\le\frac{1}{\sqrt{2\pi}}\int_{k}^{\infty}\frac{x}{k}e^{-x^{2}/2}dx=\frac{1}{\sqrt{2\pi}k}(-e^{-x^{2}/2})|_{k}^{\infty}=\frac{e^{-k^{2}/2}}{\sqrt{2\pi}k}

כדי לחסום מלמטה, נעשה אינטגרציה בחלקים פעמיים, כאשר ננצל את העובדה ש-(e^{-x^2/2})' = -xe^{-x^2/2}:

\begin{array}{lcl} \frac{1}{\sqrt{2\pi}}\int_{k}^{\infty}e^{-x^{2}/2}dx &=& \frac{1}{\sqrt{2\pi}}\int_{k}^{\infty}\frac{-1}{x}(-xe^{-x^{2}/2})dx \\  & = & \frac{1}{\sqrt{2\pi}}(\frac{-1}{x}e^{-x^{2}/2}|_{k}^{\infty}-\int_{k}^{\infty}\frac{1}{x^{2}}(e^{-x^{2}/2})dx \\  & = & \frac{1}{\sqrt{2\pi}}(\frac{1}{k}e^{-k^{2}/2}+\int_{k}^{\infty}\frac{1}{x^{3}}(-xe^{-x^{2}/2})dx \\  & = & \frac{1}{\sqrt{2\pi}}(\frac{1}{k}e^{-k^{2}/2}+\frac{e^{-x^{2}/2}}{x^{3}}|_{k}^{\infty}+\int_{k}^{\infty}\frac{3}{x^{4}}(e^{-x^{2}/2})dx) \\  & > & \frac{e^{-k^{2}/2}}{\sqrt{2\pi}}(\frac{1}{k}-\frac{1}{k^{3}}) \end{array}

אם משלבים את 2 החסמים, התחתון והעליון, האינטגרל יוצא אסימפטוטי ל-\frac{e^{-k^2/2}}{k\sqrt{2\pi}}.

תרגיל: הראו שלכל k \ge 0 מתקיים:

\frac{e^{-k^2/2}}{(k+\sqrt{k^2+4})/2}<\int\limits_k^{\infty}e^{-t^2/2} \, \text dt \le\frac{e^{-k^2/2}}{(k+\sqrt{k^2+\displaystyle\tfrac{8}{\pi}})/2}

הגיע הזמן לחישוב קונקרטי. כזכור, במקרה שלנו יש 13 סטיות תקן בערך. נשתמש בקירוב לגאוסיאן בדמות \frac{e^{-x^2/2}}{k\sqrt{2\pi}} ונקבל הסתברות שהיא בערך 2^{-127} – זעומה! כנראה שיש לי עסק עם מטבע מוטה…

5 סטיות תקן נותנות הסתברות שהיא בערך 2^{-21}, שהיא גם מאוד קטנה. יש כלל אצבע שנקרא "Five Sigma", שאומר שאירועים של 5 סטיות תקן ומעלה הם מאוד לא סבירים, ואם הם קורים כנראה יש לנו הנחות שגויות על ההתפלגות.

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

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

מרקוב

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

אי-שיוויון מרקוב: יהיה X משתנה מקרי חיובי עם תוחלת סופית, ויהי a מספר חיובי. אזי P(X\ge a) \le \frac{EX}{a}.

הוכחה:

EX \ge E(X \cdot 1_{X \ge a}) \ge E (a \cdot 1_{X \ge a}) = a P(X \ge a)

צ'בישב

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

אי-שיוויון צ'בישב: יהיה X משתנה מקרי עם תוחלת ושונות סופיים, ויהי k מספר חיובי. אזי P(|X-EX|\ge k\cdot \sigma) \le \frac{1}{k^2}.

הוכחה:

P(|X-EX| \ge k \cdot \sigma) = P(|X-EX|^2 \ge k^2\sigma^2) \le \frac{E|X-EX|^2}{k^2\sigma^2} = \frac{1}{k^2}

צ'רנוף

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

ההוכחה שלו משתמשת ברעיונות מאוד דומים להוכחה של צ'בישב. במקום להסתכל על \text{Binomial}(n,\frac{1}{2}), שהוא סכום של n אינדיקטורים – משתנים מקריים המקבלים את הערכים 0 ו-1 בהסתברות שווה, נסתכל על טרנספורמציה פשוטה שלו: S_{n} = 2\cdot\text{Binomial}(n,\frac{1}{2})-n. למשתנה S_n תוחלת 0 ("ממורכז סביב 0"), ואפשר לכתוב אותו בתור סכום של משתנים מקריים בת"ל \sum_{i=1}^{n}X_{i} כאשר ה-X_i מקבל את הערכים \pm 1 בהסתברות שווה. למי שמכיר – זה הילוך שיכור בזמן n. נשים לב שההסתברות שאנחנו רוצים לחשב הופכת ל:

P(\frac{\text{Binomial}(n,\frac{1}{2})-\frac{n}{2}}{\sqrt{\frac{n}{4}}}>k)=P(\frac{S_{n}}{\sqrt{n}}>k)=P(\sum_{i=1}^{n} X_i > \sqrt{n}k)

אנחנו מוכנים להתחיל בהוכחה. כמו שבהוכחה של צ'בישב הפעלנו פונקציה על הביטוי בתוך ההסתברות (העלאה בריבוע), נעשה זאת גם עכשיו עם הפונקציה המונוטונית עולה f_{c}(x)=e^{cx} (עבור c>0):

\begin{array}{lcl} P(\frac{S_{n}}{\sqrt{n}}>k) &=&P(e^{\sum_{i=1}^{n}cX_{i}}>e^{c\sqrt{n}k})\\  (\text{Markov}) &\le& \frac{E(e^{\sum_{i=1}^{n}cX_{i}})}{e^{c\sqrt{n}k}}\\  (\text{Independence}) &\le & \frac{\prod_{i=1}^{n}Ee^{cX_{i}}}{e^{c\sqrt{n}k}} \end{array}

את התוחלת במונה אפשר לחשב במפורש: Ee^{cX_{i}}=\frac{1}{2}(e^{c}+e^{-c}). הבעיה עם הפונקציה \frac{e^c + e^{-c}}{2} (שנקראת גם ":קוסינוס היפרבולי", \text{cosh}(c)) היא שאנחנו צריכים להעלות אותה בחזקת n (כמות הניסויים), ואין לנו מושג איך היא תיראה אחרי זה. לכן נשתמש באי-שיוויון המלוכלך הבא, שיחליף אותה במשהו נעים בהרבה – אקספוננט בודד: e^{c^{2}/2}>\frac{1}{2}(e^{c}+e^{-c}). למה זה נכון? מפתחים את טורי הטיילור של 2 האגפים ב-c^2, ובאגף שמאל המקדמים פשוט גדולים יותר אחד-אחד (חוץ מהשניים הראשונים, שיוצאים שווים):

e^{c^2/2} = \sum_{i \ge 0} \frac{c^{2i}}{2^i i!}, \frac{1}{2} (e^c + e^-c) = \sum_{i \ge 0} \frac{c^{2i}}{(2i)!}

בואו נשתמש בו באמת:

P(\frac{S_{n}}{\sqrt{n}}>k) < \frac{\prod_{i=1}^{n}e^{c^{2}/2}}{e^{c\sqrt{n}k}} = e^{nc^{2}/2-c\sqrt{n}k}

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

P(\frac{S_{n}}{\sqrt{n}}>k) < e^{-k^{2}/2}

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

תרגיל: הראו שצ'רנוף תמיד מנצח את צ'בישב, כלומר:

 \forall k > 0: e^{-k^2/2} < k^{-2}

אנטרופיה

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

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

לדוגמא, למטבע הוגן יש אנטרופיה של ביט אחד – יש לו 2 ערכים שווי הסתברות וכדי לקודד אותם אינטואיטיבי שנדרש ביט אחד – לא יותר, לא פחות. בדומה, ל-k מטבעות הוגנים תהיה אנטרופיה של k ביטים.
אבל אם יש לי מטבע לא הוגן, לדוגמא עם הסתברויות \frac{1}{3},\frac{2}{3}, אינטואיטיבי שצריך פחות ביטים כדי לקודד אותו. אבל בגלל שזה מבלבל לחשוב על ביטים שבריים, נסתכל על k הטלות בלתי-תלויות של מטבע כזה. במקום שיהיו 2^k אפשרויות שוות הסתברות, יש עדיין אותה כמות אפשרויות, אבל הן לא שוות הסתברות כלל. יש ריכוז של רוב ההסתברות באיזור הסדרות עם \frac{k}{3} תוצאות עץ ו-\frac{2k}{3} תוצאות פלי, ומה שמעוות בזה הוא שיש הרבה פחות סדרות מהסוג הזה לעומת לדוגמא סדרות עם בערך כמות שווה של עץ ופלי. בגלל שיש פחות כאלו סדרות, יותר קל לקודד אותן. כמה סדרות כאלו יש? בקירוב מאוד גס, \binom{k}{k/3} – ביטוי ש-\log_2 שלו הוא בערך 0.9k (בתרגיל תוכיחו זאת), ומכאן אפשר לנחש שבתוחלת צריך \sim 0.9k ביטים כדי לקודד אותו, ולכן נגיד שבמטבע בודד יש אנטרופיה של \sim 0.9 ביט.

האנטרופיה של משתנה מקרי X מוגדרת פורמלית בתור H(X)=\sum_{x\in Values(X)}P(X=x)\log_{1/2}P(X=x). ההיגיון מאחורי ההגדרה הוא זה: נגיד ודגמתי את X וקיבלתי את הערך x. המידע שהועבר לי הוא \log_{\frac{1}{2}}P(X=x) (תחשבו על מקרה של קוביה עם n צדדים עם הסתברויות שוות. אם אני זורק אותה ומקבל תוצאה כלשהי בעצם מועברים לי \log_2 n ביטים, שמקודדים איזה מהצדדים שלה יצא). H(X) הוא בדיוק תוחלת על המידע שכל ערך נותן לי. אפשר לקרוא עוד בויקיפדיה (ובכל מקרה לא נצטרך יותר מזה להמשך הדיון).

סימון מקובל לאנטרופיה של ניסוי ברנולי עם הסתברות p הוא H(p), ששווה ל-p\log_{1/2}p+q\log_{1/2}q, כאשר q=1-p. בדקו שזו פונקציה סימטרית ביחס ל-p=\frac{1}{2}, וששם היא מקבלת מקסימום.

תרגיל: השתמשו בקירוב סטירלינג כדי להוכיח ש-\log_2 \binom{n}{np} = nH(p) + O(\ln n).

ננסח את האי-שיוויון שלנו:

חסם אנטרופיה: עבור m\le\frac{n}{2} מתקיים:

\sum_{i\le m}\binom{n}{i} \le 2^{nH(\frac{m}{n})}

בואו נוכיח אותו בשתי שורות:

\begin{array}{lcl} 1 &\ge& P(\text{Binomial}(n,\frac{m}{n})\le m) \\  &=& \sum_{i=0}^{m}\binom{n}{i}(\frac{m}{n})^{i}(1-\frac{m}{n})^{n-i}\\  &\ge & \sum_{i=0}^{m}\binom{n}{i}\cdot\min_{0\le i\le m}(\frac{m}{n})^{i}(1-\frac{m}{n})^{n-i} \end{array}

כלומר \sum_{i\le m}\binom{n}{i}\le\max_{0\le i\le m}(\frac{m}{n})^{-i}(1-\frac{m}{n})^{i-n}. נותר להראות שלכל 0\le i\le m מתקיים (\frac{m}{n})^{-i}(1-\frac{m}{n})^{i-n}\le2^{nH(\frac{m}{n})}. פשוט ניקח \log_{2} וזה נהיה שקול ל-(\log_{1/2}\frac{m}{n}-\log_{1/2}(1-\frac{m}{n}))(m-i)\ge 0\blacksquare

אם מציבים m=\frac{n}{2}-k\sqrt{\frac{n}{4}} מקבלים:

P(\frac{S_n}{\sqrt{n}} >k ) = P(\frac{\text{Binomial}(n,\frac{1}{2})-\frac{n}{2}}{\sqrt{\frac{n}{4}}}>k)=2^{-n}\sum_{i> n-m}\binom{n}{i}=2^{-n}\sum_{i< m}\binom{n}{i}< 2^{n(H(\frac{1}{2}-\frac{k}{2}\sqrt{\frac{1}{n}})-1)}

כאשר באי-שיוויון האחרון השתמשנו בחסם. באמת מדובר באלטרנטיבה לצ'רנוף.

האם החסם הנ"ל טוב יותר? לגמרי. עשיתי בשבילכם את פיתוח הטיילור של n(H(\frac{1}{2}-\frac{k}{2}\sqrt{\frac{1}{n}})-1), וקבלתי את האי-שיוויון הבא:

P(\frac{S_{n}}{\sqrt{n}}>k) \le \exp(-\sum_{i\ge1}\frac{k^{2i}}{n^{i-1}2i(2i-1)})

הגורם הראשון באקספוננט הוא -\frac{k^{2}}{2}, הגורם של צ'רנוף. הגורם הבא הוא -\frac{k^{4}}{12n}. באופן כללי, כש-n שואף לאינסוף ו-k קבוע, ההבדל בין הקירובים זעום. אבל בכל מקרה שבו k פרופורציוני ל-n^{1/2}, צ'רנוף מפשל וקירוב האנטרופיה מחזיק מעמד.

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

ומה שביניהם

אז בדקתי באינטרנט מה ידוע על הקשר בין חסם צ'רנוף לחסם האנטרופיה, וגיליתי שיש וריאציה קלה על ההוכחה הסטנדרטית של צ'רנוף שנותנת את חסם האנטרופיה (זה הפתיע אותי, כי את צ'רנוף בגרסה בה הוא הופיע בפוסט ראיתי בכמה וכמה ספרים בהסתברות).
הרעיון הוא לדלג על שלב בהוכחה – לא למרכז את הסכום \text{Binomial}(n,\frac{1}{2}) = \sum_{i=1}^{n} Y_i של האינדיקטורים, ולהשאיר אותו כמו שהוא:

\begin{array}{lcl} P(\text{Binomial}(n,\frac{1}{2}) -\frac{n}{2} >k\sqrt{\frac{n}{4}}) &=& P(\sum_{i=1}^{n} Y_i > \frac{n}{2} + k\sqrt{\frac{n}{4}})\\  &=& P(e^{\sum_{i=1}^{n}cY_{i}}>e^{c(\frac{n}{2} + k\sqrt{\frac{n}{4}})})\\  (\text{Markov}) &\le& \frac{E(e^{\sum_{i=1}^{n}cY_{i}})}{e^{c(\frac{n}{2}+\sqrt{\frac{n}{4}}k)}}\\  (\text{Independence}) &\le & \frac{\prod_{i=1}^{n}Ee^{cY_{i}}}{e^{c(\frac{n}{2}+\sqrt{\frac{n}{4}}k)}} \end{array}

את התוחלת במונה אפשר לחשב במפורש: Ee^{cY_{i}}=\frac{1}{2}(e^{c}+1). שוב הגענו לבעית אופטימיזציה – אנחנו מחפשים c>0 כך שהביטוי הבא יהיה מינימלי:

\frac{(1+e^c)^n}{e^{c(\frac{n}{2} + \sqrt{\frac{n}{4}}k)}}

שוב נחסוך מכם את החישובים, ורק אגיד שהמקסימום מתקבל ב-c=\ln(\frac{\sqrt{n}+k}{\sqrt{n}-k}), ומקבלים את חסם האנטרופיה בשנית. (הערה: השתמשתי בהנחה ש-k<\sqrt{n}, שכדאי להניח כי שאר המקרים לא מעניינים מכיוון ש-|S_n| \le n.)

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

לקריאה נוספת: פוסט של טרי טאו על ריכוז של מידה.

להתראות בפוסט הבא!

 נספח – הוכחה של משפט הגבול המרכזי

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

\phi_{X}(t)=Ee^{itX}

אם X הוא משתנה מקרי רציף ו-f_X היא פונקציית הצפיפות שלו, הגדרה שקולה היא \int_{\mathbb{R}} e^{itx} f_{X}(t) dt. יש שיכירו אותה בתור התמרת פורייה, כי זה מה שהיא. אפשר גם להסתכל עליה בתור פונקציה יוצרת – תחת הנחות התכנסות מסוימות על X, ביניהן שכל המומנטים קיימים וסופיים (E|X|^k < \infty), אפשר להצדיק את ההחלפה בין סכום לאינטגרל בשיוויון הבא:

Ee^{itX} = E \sum_{k} \frac{(itX)^k}{k!} = \sum_{k} E \frac{(itX)^k}{k!} = \sum_{k} EX^k \frac{(it)^k}{k!}

ומקבלים שעד כדי פקטור i^k, הפונקציה האופיינית היא הפונקציה היוצרת האקספוננציאלית של המומנטים של ההתפלגות. קל להיווכח שכדי להיפטר מהפקטור הזה צריך להסתכל על Ee^{tX} דווקא.

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

למה בכלל אנחנו רוצים להסתכל על התמרת פורייה? שאלה טובה. התמרת פורייה היא טרנספורמציה קסומה שהופכת קונבולוציה לכפל (וכפל לקונבולוציה). כשאנחנו מחברים משתנים מקרים בלתי-תלויים, ההתפלגות שמתקבלת היא הקונבולוציה של ההתפלגויות המקוריות, ולכן הפונקצייה האופיינית של הסכום תהיה המכפלה של הפונקציות האופייניות: \phi_{X+Y} = \phi_{X} \phi_{Y}. במקרה שלנו, אנחנו רוצים להבין את ההתפלגות של סכום של הרבה משתנים מקריים, והפונקצייה האופיינית של ההתפלגות הזו תהפוך לחזקה של פונקציה האופיינית של המשתנה הבסיסי. אנחנו פשוט הופכים את הבעיה לחישובית – זה יסתכם בחישובי גבולות ברמת קורס ראשון בחדו"א.

הוכחה: ההוכחה תלך כך: נחשב את הפונקציה האופיינית של \overline{X}_{n} = \frac{ \sum_{i=1}^{n} X_i - n\mu}{\sigma \sqrt{n}}. נראה שהיא שואפת נקודתית לפונקציה האופיינית של \text{Normal}(0,1). נסיים בעזרת המשפט הבא, משפט הרציפות של Lévy: תהי X_n סדרה של מ"מ שהפונקציות האופייניות שלהם מתכנסת נקודתית לפונקציה \phi. נניח בנוסף שיש משתנה מקרי X עם פונקציה אופיינית \phi. אז הסדרה X_n מתכנסת בהתפלגות ל-X.

נתחיל. נשתמש חזק מאוד באי-תלות של המשתנים. בגלל ש-\overline{X}_{n} = \sum_{i=1}^{n} \frac{(X_i - \mu)}{\sqrt{n} \sigma}, ו-\phi_{X+Y} = \phi_{X} \phi_{Y} כאשר X,Y בת"ל, נקבל: \phi_{\overline{X}_{n}} = \phi_{(X_1-\mu)/(\sigma \sqrt{n})}^{n}.

בגלל של-\frac{X_i-\mu}{\sigma} תוחלת 0 ושונות 1, הפונקצייה האופיינית היא מהצורה 1-\frac{t^2}{2} + o(t^2). אחרי החלוקה בשורש n היא הופכת ל-1-\frac{t^2}{2n} + o(\frac{t^2}{n}). נקבל:

\phi_{\overline{X}_{n}}(t) = (1-\frac{t^2}{2n} + o(\frac{t^2}{n}))^{n} = ((1-\frac{t^2}{2n} + o(\frac{t^2}{n}))^{2n/t^2})^{t^2/2} \to e^{-t^2/2}

וזאת הפונקצייה האופיינית של משתנה נורמלי עם תוחלת 0 ושונות 1. לאיזו פונקציית צפיפות יש התמרת פורייה השווה ל-e^{-t^2/2}? היא עצמה חלקי \sqrt{2\pi}, כלומר לגאוסיאן! זה ממש מגניב. זה נכון ע"י השלמה לריבוע וקצת אנליזה מרוכבת:

\phi_{N(0,1)}(t) = \frac{1}{\sqrt{2\pi}} \int_{\mathbb{R}} e^{-x^2/2} e^{itx} dx

זו ההגדרה. עכשיו נשלים לריבוע:

\frac{e^{-t^2/2}}{\sqrt{2\pi}} \int_{\mathbb{R}} e^{-(x-it)^2/2} dx

אם נוכל להחליף את האינטגרנד ב-e^{-x^2/2} ננצח, כי אנחנו יודעים שהאינטגרל של הגאוסיאן יוצא אחד: \int_{\mathbb{R}} e^{-x^2/2} dx =\sqrt{2\pi}. איך אפשר לעשות החלפה זו? בעזרת שיקול דיי סטנדרטי – נסתכל על מלבן במישור המרוכב שנראה כך: צד אחד הוא [-r,r] \times \{ 0 \}, והצד ממול הוא [-r,r] \times \{ -t\}. שני הצדדים האחרים הם \{ \pm r \} \times [-t,0]. בגלל שהגאוסיאן הוא פונקציה שלמה, האינטגרל על המלבן יוצא אפס. ההחלפה שאנחנו רוצים לעשות שקולה לכך שהאינטגרל על הצלע התחתונה שווה לאינטגרל על הצלע העליונה כש-r שואף לאינסוף. בגלל שהאינטגרל על כל המלבן הוא אפס, זה שקול לכך שהאינטגרל על הצלעות הצדדיות שואף לאפס כש-r שואף לאינסוף, ואת זה מראים ע"י אי-שיוויון המשולש ושימוש בכך שגאוסיאן דועך מהר:

|\int_{\mathbb{R}} e^{-(\pm r -is)^2/2} ds| \le \int_{\mathbb{R}} |e^{-(\pm r -is)^2/2}| ds =\int_{\mathbb{R}} e^{(s^2-r^2)/2} ds= e^{-r^2/2} O(1) \to 0

עכשיו אפשר להשתמש במשפט Lévy ולסיים. \blacksquare

הערה: בעזרת קירוב סטירלינג אפשר להוכיח את משפט הגבול המרכזי באופן ישיר במקרה שלנו של משתנה בינומי. למעשה, מקדם בינומי הוא גאוסיאן: \binom{n}{\frac{n+\sqrt{n}k}{2}}=(\sqrt{\frac{2}{\pi}}+o(1))\frac{2^{n}}{\sqrt{n}}\exp(-\frac{k^{2}}{2}). על כל זאת ועוד בפוסט הבא.

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

אודות Ofir Gorodetsky

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

תגובה אחת על חסם צ'רנוף, חסם אנטרופיה ומה שביניהם

  1. פינגבאק: מי מפחד מ-n עצרת? | One and One

כתיבת תגובה

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

הלוגו של WordPress.com

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

תמונת Twitter

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

תמונת Facebook

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

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

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

מתחבר ל-%s