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

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

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

נוסח פורמלי

יהיו $X_1,...,X_n$ משתנים מקריים בלתי תלויים, שתוחלת כולם היא אפס ושונות כולם סופית.

נסמן $S_k=X_1+\dots +X_k$ לכל $k=1,\dots n$. אזי לכל $\lambda >0$ מתקיים, $$\mathbb{\mathbb{P}}(\underset{1\le k\le n}{\max }\left|S_k\right|\ge \lambda )\le \frac{1}{{\lambda }^2}\cdot \mathbf{V}\mathbf{a}\mathbf{r}\left(S_n\right)=\frac{1}{{\lambda }^2}\cdot \sum _{k=1}^n\mathbf{V}\mathbf{a}\mathbf{r}\left(X_k\right)$$

הוכחה

ניתן להראות כי הסדרה $S_1,S_2,...,S_n$ היא מרטינגל. נניח ללא הגבלת הכלליות כי $S_0=0$ וכי $S_k\ge 0$ לכל $k=1,\dots ,n$.

נגדיר בצורה אינדוקטיבית $Z_0=0$, וכן $$Z_{k+1}=\{\begin{array}{l}\begin{array}{cc}{S}_{k+1}& \underset{1\le j\le k}{\max }{S}_j<\lambda \\ Z_k& \text{otherwise}\end{array}\end{array}$$

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

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

$\begin{array}{rl}\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}[S_k^2-2(S_{k-1}+S_k-S_{k-1})S_{k-1}+S_{k-1}^2]\\ & =\sum _{k=1}^n\mathbf{E}[S_k^2-S_{k-1}^2]-2\mathbf{E}[S_{k-1}(S_k-S_{k-1})]\\ & =\mathbf{E}[S_n^2]-\mathbf{E}[S_0^2]=\mathbf{E}[S_n^2].\end{array}$

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

$\begin{array}{rl}\mathbb{\mathbb{P}}(\underset{1\le k\le n}{\max }{S}_k\ge \lambda )& =\mathbb{\mathbb{P}}(Z_n\ge \lambda )\\ & \le \frac{1}{{\lambda }^2}\mathbf{E}\left[Z_n^2\right]=\frac{1}{{\lambda }^2}\sum _{k=1}^n\mathbf{E}[(Z_k-Z_{k-1}{)}^2]\\ & \le \frac{1}{{\lambda }^2}\sum _{k=1}^n\mathbf{E}[(S_k-S_{k-1}{)}^2]=\frac{1}{{\lambda }^2}\mathbf{E}\left[S_n^2\right]=\frac{1}{{\lambda }^2}\mathbf{V}\mathbf{a}\mathbf{r}\left(S_n\right)\end{array}$

שימוש

נתבונן בהילוך מקרי פשוט על $\mathbb{\mathbb{Z}}$, בו כל צעד הוא משתנה מקרי $X_k$ בעל התפלגות אחידה בדידה $\mathbb{\mathbb{P}}(X_k=1)=\mathbb{\mathbb{P}}(X_k=-1)=\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{V}\mathbf{a}\mathbf{r}\left(X_k\right)=\frac{1}{4n^2}\cdot n=\frac{1}{4n}$

לקריאה נוספת

* בתהליכי בנייה "תבנית:Cite book" (Theorem 22.4)

• בתהליכי בנייה "תבנית:Cite book"