אי-שוויון קולמוגורוב

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

האי-שוויון קרוי על שמו של המתמטיקאי הרוסי אנדריי קולמוגורוב.

נוסח פורמלי

יהיו $ X_{1},...,X_{n} $ משתנים מקריים בלתי תלויים, שתוחלת כולם היא אפס ושונות כולם סופית.

נסמן $ S_{k}=X_{1}+\dots +X_{k} $ לכל $ k=1,\dots n $. אזי לכל $ \lambda >0 $ מתקיים,

$ \mathbb {P} \left(\max _{1\leq k\leq n}\left|S_{k}\right|\geq \lambda \right)\leq {\frac {1}{\lambda ^{2}}}\cdot \mathbf {Var} \left(S_{n}\right)={\frac {1}{\lambda ^{2}}}\cdot \sum _{k=1}^{n}\mathbf {Var} \left(X_{k}\right) $

הוכחה

ניתן להראות כי הסדרה $ S_{1},S_{2},...,S_{n} $ היא מרטינגל. נניח ללא הגבלת הכלליות כי $ S_{0}=0 $ וכי $ S_{k}\geq 0 $ לכל $ k=1,\dots ,n $.

נגדיר בצורה אינדוקטיבית $ Z_{0}=0 $, וכן

$ Z_{k+1}={\begin{cases}{\begin{array}{cc}S_{k+1}&\max _{1\leq j\leq k}S_{j}<\lambda \\Z_{k}&{\mbox{otherwise}}\end{array}}\end{cases}} $

ניתן להראות כי הסדרה $ \left(Z_{k}\right)_{k=0}^{n} $ גם היא מרטינגל.

נשים לב שמתקיים,

$ {\begin{aligned}\sum _{k=1}^{n}\mathbf {E} [(S_{k}-S_{k-1})^{2}]&=\sum _{k=1}^{n}\mathbf {E} [S_{k}^{2}-2S_{k}S_{k-1}+S_{k-1}^{2}]\\&=\sum _{k=1}^{n}\mathbf {E} \left[S_{k}^{2}-2(S_{k-1}+S_{k}-S_{k-1})S_{k-1}+S_{k-1}^{2}\right]\\&=\sum _{k=1}^{n}\mathbf {E} \left[S_{k}^{2}-S_{k-1}^{2}\right]-2\mathbf {E} \left[S_{k-1}(S_{k}-S_{k-1})\right]\\&=\mathbf {E} [S_{n}^{2}]-\mathbf {E} [S_{0}^{2}]=\mathbf {E} [S_{n}^{2}].\end{aligned}} $

ניתן לראות כי אותו הדבר נכון עבור הסדרה $ \left(Z_{k}\right)_{k=0}^{n} $. לכן נובע על ידי אי-שוויון צ'בישב כי,

$ {\begin{aligned}\mathbb {P} \left(\max _{1\leq k\leq n}S_{k}\geq \lambda \right)&=\mathbb {P} \left(Z_{n}\geq \lambda \right)\\&\leq {\frac {1}{\lambda ^{2}}}\mathbf {E} \left[Z_{n}^{2}\right]={\frac {1}{\lambda ^{2}}}\sum _{k=1}^{n}\mathbf {E} \left[(Z_{k}-Z_{k-1})^{2}\right]\\&\leq {\frac {1}{\lambda ^{2}}}\sum _{k=1}^{n}\mathbf {E} \left[(S_{k}-S_{k-1})^{2}\right]={\frac {1}{\lambda ^{2}}}\mathbf {E} \left[S_{n}^{2}\right]={\frac {1}{\lambda ^{2}}}\mathbf {Var} \left(S_{n}\right)\end{aligned}} $

שימוש

נתבונן בהילוך מקרי פשוט על $ \mathbb {Z} $, בו כל צעד הוא משתנה מקרי $ X_{k} $ בעל התפלגות אחידה בדידה $ \mathbb {P} \left(X_{k}=1\right)=\mathbb {P} \left(X_{k}=-1\right)={\frac {1}{2}} $. לכן השונות של כל צעד היא $ 1 $.

בצעד ה-$ n $, מיקומו של ההילוך הוא $ S_{n}=X_{1}+\dots +X_{n} $. לפיכך מאי-שוויון קולמוגורוב ניתן להסיק כי אם אנחנו בצעד ה-$ n $, ההסתברות שהמיקום הרחוק ביותר אליו הגיע ההילוך הוא $ {\frac {1}{2n}} $, היא לכל היותר $ {\frac {1}{4n^{2}}}\sum _{k=1}^{n}\mathbf {Var} \left(X_{k}\right)={\frac {1}{4n^{2}}}\cdot n={\frac {1}{4n}} $

לקריאה נוספת

* Billingsley, Patrick (1995). Probability and Measure. New York: John Wiley & Sons, Inc. ISBN 0-471-00710-2. (Theorem 22.4)

• Feller, William (1968) [1950]. An Introduction to Probability Theory and its Applications, Vol 1 (Third ed.). New York: John Wiley & Sons, Inc. xviii+509. ISBN 0-471-25708-7.

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

אי-שוויון קולמוגורוב33508430Q1747439