נוסח פורמלי
עריכה
ניתן להראות כי הסדרה
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}}}
לקריאה נוספת
עריכה
*
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 .