בתורת ההסתברות , אי-שוויון קולמוגורוב או אי-שוויון המקסימום של קולמוגורוב מתאר חסם הסתברותי למאורע שהמקסימום של סדרת הסכומים החלקיים של סדרה סופית של משתנים מקריים בלתי-תלויים גדול מערך קבוע כלשהו.
האי-שוויון קרוי על שמו של המתמטיקאי הרוסי אנדריי קולמוגורוב .
נוסח פורמלי יהיו
X
1
,
.
.
.
,
X
n
{\displaystyle X_{1},...,X_{n}}
משתנים מקריים בלתי תלויים , שתוחלת כולם היא אפס ושונות כולם סופית.
נסמן
S
k
=
X
1
+
⋯
+
X
k
{\displaystyle S_{k}=X_{1}+\dots +X_{k}}
k
=
1
,
…
n
{\displaystyle k=1,\dots n}
λ
>
0
{\displaystyle \lambda >0}
P
(
max
1
≤
k
≤
n
|
S
k
|
≥
λ
)
≤
1
λ
2
⋅
V
a
r
(
S
n
)
=
1
λ
2
⋅
∑
k
=
1
n
V
a
r
(
X
k
)
{\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)}
הוכחה ניתן להראות כי הסדרה
S
1
,
S
2
,
.
.
.
,
S
n
{\displaystyle S_{1},S_{2},...,S_{n}}
מרטינגל . נניח ללא הגבלת הכלליות כי
S
0
=
0
{\displaystyle S_{0}=0}
S
k
≥
0
{\displaystyle S_{k}\geq 0}
k
=
1
,
…
,
n
{\displaystyle k=1,\dots ,n}
נגדיר בצורה אינדוקטיבית
Z
0
=
0
{\displaystyle Z_{0}=0}
Z
k
+
1
=
{
S
k
+
1
max
1
≤
j
≤
k
S
j
<
λ
Z
k
otherwise
{\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}}}
ניתן להראות כי הסדרה
(
Z
k
)
k
=
0
n
{\displaystyle \left(Z_{k}\right)_{k=0}^{n}}
מרטינגל .
נשים לב שמתקיים,
∑
k
=
1
n
E
[
(
S
k
−
S
k
−
1
)
2
]
=
∑
k
=
1
n
E
[
S
k
2
−
2
S
k
S
k
−
1
+
S
k
−
1
2
]
=
∑
k
=
1
n
E
[
S
k
2
−
2
(
S
k
−
1
+
S
k
−
S
k
−
1
)
S
k
−
1
+
S
k
−
1
2
]
=
∑
k
=
1
n
E
[
S
k
2
−
S
k
−
1
2
]
−
2
E
[
S
k
−
1
(
S
k
−
S
k
−
1
)
]
=
E
[
S
n
2
]
−
E
[
S
0
2
]
=
E
[
S
n
2
]
.
{\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}}}
ניתן לראות כי אותו הדבר נכון עבור הסדרה
(
Z
k
)
k
=
0
n
{\displaystyle \left(Z_{k}\right)_{k=0}^{n}}
אי-שוויון צ'בישב כי,
P
(
max
1
≤
k
≤
n
S
k
≥
λ
)
=
P
(
Z
n
≥
λ
)
≤
1
λ
2
E
[
Z
n
2
]
=
1
λ
2
∑
k
=
1
n
E
[
(
Z
k
−
Z
k
−
1
)
2
]
≤
1
λ
2
∑
k
=
1
n
E
[
(
S
k
−
S
k
−
1
)
2
]
=
1
λ
2
E
[
S
n
2
]
=
1
λ
2
V
a
r
(
S
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}}}
שימוש נתבונן בהילוך מקרי פשוט על
Z
{\displaystyle \mathbb {Z} }
X
k
{\displaystyle X_{k}}
התפלגות אחידה בדידה
P
(
X
k
=
1
)
=
P
(
X
k
=
−
1
)
=
1
2
{\displaystyle \mathbb {P} \left(X_{k}=1\right)=\mathbb {P} \left(X_{k}=-1\right)={\frac {1}{2}}}
שונות של כל צעד היא
1
{\displaystyle 1}
בצעד ה-
n
{\displaystyle n}
S
n
=
X
1
+
⋯
+
X
n
{\displaystyle S_{n}=X_{1}+\dots +X_{n}}
n
{\displaystyle n}
1
2
n
{\displaystyle {\frac {1}{2n}}}
1
4
n
2
∑
k
=
1
n
V
a
r
(
X
k
)
=
1
4
n
2
⋅
n
=
1
4
n
{\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 33508430 אי-שוויון קולמוגורוב
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d4a8b900bd3f5bcd02c2ff86a929599517980831)
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5b517098a21e44cad3a8b768e53da61573272cd)
