柯爾莫哥洛夫不等式

在概率論中，柯爾莫哥洛夫不等式是一個關於獨立隨機變量序列的部分和的不等式。這個不等式以蘇聯數學家安德雷·柯爾莫哥洛夫的名字命名，他在1929年發現了這個不等式。

不等式的陳述

設$\{X_{n}\}$是獨立的隨機變量序列，並且對所有正整數i，第i個隨機變量的期望$E[X_{i}]=0$，方差$\operatorname {var} (X_{i})=E[X_{i}^{2}]<\infty$是有限的，那麼對於任意$\varepsilon >0$，

$\Pr \left(\max _{1\leq k\leq n}|S_{k}|\geq \varepsilon \right)\leq {\frac {1}{\varepsilon ^{2}}}\operatorname {var} (S_{n})={\frac {1}{\varepsilon ^{2}}}\sum _{k=1}^{n}{\text{E}}[X_{k}^{2}],$

其中，$S_{k}=X_{1}+\cdots +X_{k}$為前k項的部分和。

柯爾莫哥洛夫不等式很有用，例如可以給出隨機遊走最大的偏離，也可以證明強大數定律。

在不等式中，將最大值符號去掉即為切比雪夫不等式。

證明

對於給定的 ${\textstyle \varepsilon >0}$, 記事件

$\Lambda =\left\{\max _{1\leq j\leq n}|S_{j}|\geq \varepsilon \right\}.$

設隨機時間 ${\textstyle T=\min\{j:|S_{j}|\geq \varepsilon \}}$ 為 ${\textstyle |S_{j}|}$ 首次超過 ${\textstyle \varepsilon }$ 的時刻, 並定義事件 ${\textstyle \Lambda _{k}=[T=k]}$, 即

$\Lambda _{k}=\left\{\max _{1\leq j\leq k-1}|S_{j}|<\varepsilon ,|S_{k}|\geq \varepsilon \right\}.$

注意到 ${\textstyle \Lambda _{k}}$ 兩兩不交, 構成了 ${\textstyle \Lambda }$ 的劃分, 即 ${\textstyle \Lambda =\displaystyle \sqcup _{k=1}^{n}\Lambda _{k}}$, 所以我們有

${\begin{aligned}\operatorname {E} [S_{n}^{2}\mathbf {1} _{\Lambda }]&=\sum _{k=1}^{n}\operatorname {E} [S_{n}^{2}\mathbf {1} _{\Lambda _{k}}]\\&=\sum _{k=1}^{n}{\Big (}\operatorname {E} [S_{k}^{2}\mathbf {1} _{\Lambda _{k}}]+2\operatorname {E} [S_{k}\mathbf {1} _{\Lambda _{k}}(S_{n}-S_{k})]+\operatorname {E} [(S_{n}-S_{k})^{2}\mathbf {1} _{\Lambda _{k}}]{\Big )}\end{aligned}}$

這裡${\textstyle \mathbf {1} _{\Lambda }={\begin{cases}1,&\omega \in \Lambda ,\\0,&\omega \notin \Lambda .\end{cases}}}$.

因為 ${\textstyle S_{k}\mathbf {1} _{\Lambda _{k}}}$ 與 ${\textstyle S_{n}-S_{k}=X_{k+1}+\cdots +X_{n}}$ 獨立, 因此其乘積期望為 0. 從而

$\operatorname {E} [S_{n}^{2}\mathbf {1} _{\Lambda }]=\sum _{k=1}^{n}{\Big (}\operatorname {E} [S_{k}^{2}\mathbf {1} _{\Lambda _{k}}]+\operatorname {E} [(S_{n}-S_{k})^{2}\mathbf {1} _{\Lambda _{k}}]{\Big )}\geq \sum _{k=1}^{n}\operatorname {E} [S_{k}^{2}\mathbf {1} _{\Lambda _{k}}]$

又因為 ${\textstyle \operatorname {E} [S_{k}^{2}\mathbf {1} _{\Lambda _{k}}]\geq \varepsilon ^{2}\Pr[\Lambda _{k}]}$, 所以

$\operatorname {E} [S_{n}^{2}\mathbf {1} _{\Lambda }]=\sum _{k=1}^{n}\operatorname {E} [S_{n}^{2}\mathbf {1} _{\Lambda _{k}}]\geq \varepsilon ^{2}\sum _{k=1}^{n}\Pr[\Lambda _{k}]=\varepsilon ^{2}\Pr[\Lambda ].$

這樣就證明了

$\Pr[\Lambda ]\leq {\frac {1}{\varepsilon ^{2}}}\operatorname {E} [S_{n}^{2}\mathbf {1} _{\Lambda }]\leq {\frac {1}{\varepsilon ^{2}}}\operatorname {E} [S_{n}^{2}].$

定理得證。