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

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

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

נוסח פורמלי

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

נסמן ${\displaystyle S_{k}=X_{1}+\dots +X_{k}}$ לכל ${\displaystyle k=1,\dots n}$. אזי לכל ${\displaystyle \lambda >0}$ מתקיים, $${\displaystyle \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)}$$

הוכחה

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

נגדיר בצורה אינדוקטיבית ${\displaystyle Z_{0}=0}$, וכן $${\displaystyle 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}}}$$

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

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

${\displaystyle {\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}}}$

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

${\displaystyle {\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}}}$

שימוש

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

בצעד ה-${\displaystyle n}$, מיקומו של ההילוך הוא ${\displaystyle S_{n}=X_{1}+\dots +X_{n}}$. לפיכך מאי-שוויון קולמוגורוב ניתן להסיק כי אם אנחנו בצעד ה-${\displaystyle n}$, ההסתברות שהמיקום הרחוק ביותר אליו הגיע ההילוך הוא ${\displaystyle {\frac {1}{2n}}}$, היא לכל היותר ${\displaystyle {\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.