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

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

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

נוסח פורמלי

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

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

הוכחה

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

נגדיר בצורה אינדוקטיבית $Z_0=0$, וכן $$Z_{k+1}=\{\begin{array}{c}\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}{cc}\sum _{k=1}^n𝐄[(S_k-S_{k-1}{)}^2]& =\sum _{k=1}^n𝐄[S_k^2-2S_k{S}_{k-1}+S_{k-1}^2]\\ & =\sum _{k=1}^n𝐄[S_k^2-2(S_{k-1}+S_k-S_{k-1})S_{k-1}+S_{k-1}^2]\\ & =\sum _{k=1}^n𝐄[S_k^2-S_{k-1}^2]-2𝐄[S_{k-1}(S_k-S_{k-1})]\\ & =𝐄[S_n^2]-𝐄[S_0^2]=𝐄[S_n^2].\end{array}$

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

$\begin{array}{cc}\mathbb{P}(\underset{1\le k\le n}{max}{S}_k\ge \lambda )& =\mathbb{P}(Z_n\ge \lambda )\\ & \le \frac{1}{{\lambda }^2}𝐄\left[Z_n^2\right]=\frac{1}{{\lambda }^2}\sum _{k=1}^n𝐄[(Z_k-Z_{k-1}{)}^2]\\ & \le \frac{1}{{\lambda }^2}\sum _{k=1}^n𝐄[(S_k-S_{k-1}{)}^2]=\frac{1}{{\lambda }^2}𝐄\left[S_n^2\right]=\frac{1}{{\lambda }^2}𝐕𝐚𝐫\left(S_n\right)\end{array}$

שימוש

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

לקריאה נוספת

* תבנית:Cite book (Theorem 22.4)

• תבנית:Cite book