柯尔莫哥洛夫不等式

在概率论中，柯尔莫哥洛夫不等式是一个关于独立随机变量序列的部分和的不等式。这个不等式以苏联数学家安德雷·柯尔莫哥洛夫的名字命名，他在1929年发现了这个不等式。

不等式的陈述

设$\{X_n\}$是独立的随机变量序列，并且对所有正整数i，第i个随机变量的期望$E[X_i]=0$，方差$\mathrm{var}(X_i)=E[X_i^2]<\mathrm{\infty }$是有限的，那么对于任意$\epsilon >0$，

$\mathrm{Pr}(\underset{1\le k\le n}{\max }|S_k|\ge \epsilon )\le \frac{1}{{\epsilon }^2}\mathrm{var}(S_n)=\frac{1}{{\epsilon }^2}\sum _{k=1}^n\text{E}[X_k^2],$

其中，$S_k=X_1+\cdots +X_k$为前k项的部分和。

柯尔莫哥洛夫不等式很有用，例如可以给出随机游走最大的偏离，也可以证明强大数定律。

在不等式中，将最大值符号去掉即为切比雪夫不等式。

证明

对于给定的 $\epsilon >0$, 记事件

$\mathrm{\Lambda }=\{\underset{1\le j\le n}{\max }|S_j|\ge \epsilon \}.$

设随机时间 $T=\min \{j:|S_j|\ge \epsilon \}$ 为 $|S_j|$ 首次超过 $\epsilon$ 的时刻, 并定义事件 ${\mathrm{\Lambda }}_k=[T=k]$, 即

${\mathrm{\Lambda }}_k=\{\underset{1\le j\le k-1}{\max }|S_j|<\epsilon ,|S_k|\ge \epsilon \}.$

注意到 ${\mathrm{\Lambda }}_k$ 两两不交, 构成了 $\mathrm{\Lambda }$ 的划分, 即 $\mathrm{\Lambda }=\bigsqcup _{k=1}^n{\mathrm{\Lambda }}_k$, 所以我们有

$\begin{array}{cc}\mathrm{E}[S_n^2{\mathrm{𝟏}}_{\mathrm{\Lambda }}]& =\sum _{k=1}^n\mathrm{E}[S_n^2{\mathrm{𝟏}}_{{\mathrm{\Lambda }}_k}]\\ & =\sum _{k=1}^n(\mathrm{E}[S_k^2{\mathrm{𝟏}}_{{\mathrm{\Lambda }}_k}]+2\mathrm{E}[S_k{\mathrm{𝟏}}_{{\mathrm{\Lambda }}_k}(S_n-S_k)]+\mathrm{E}[(S_n-S_k{)}^2{\mathrm{𝟏}}_{{\mathrm{\Lambda }}_k}])\end{array}$

这里${\mathrm{𝟏}}_{\mathrm{\Lambda }}=\{\begin{array}{cc}1,& \omega \in \mathrm{\Lambda },\\ 0,& \omega \notin \mathrm{\Lambda }.\end{array}$.

因为 $S_k{\mathrm{𝟏}}_{{\mathrm{\Lambda }}_k}$ 与 $S_n-S_k=X_{k+1}+\cdots +X_n$ 独立, 因此其乘积期望为 0. 从而

$\mathrm{E}[S_n^2{\mathrm{𝟏}}_{\mathrm{\Lambda }}]=\sum _{k=1}^n(\mathrm{E}[S_k^2{\mathrm{𝟏}}_{{\mathrm{\Lambda }}_k}]+\mathrm{E}[(S_n-S_k{)}^2{\mathrm{𝟏}}_{{\mathrm{\Lambda }}_k}])\ge \sum _{k=1}^n\mathrm{E}[S_k^2{\mathrm{𝟏}}_{{\mathrm{\Lambda }}_k}]$

又因为 $\mathrm{E}[S_k^2{\mathrm{𝟏}}_{{\mathrm{\Lambda }}_k}]\ge {\epsilon }^2\mathrm{Pr}[{\mathrm{\Lambda }}_k]$, 所以

$\mathrm{E}[S_n^2{\mathrm{𝟏}}_{\mathrm{\Lambda }}]=\sum _{k=1}^n\mathrm{E}[S_n^2{\mathrm{𝟏}}_{{\mathrm{\Lambda }}_k}]\ge {\epsilon }^2\sum _{k=1}^n\mathrm{Pr}[{\mathrm{\Lambda }}_k]={\epsilon }^2\mathrm{Pr}[\mathrm{\Lambda }].$

这样就证明了

$\mathrm{Pr}[\mathrm{\Lambda }]\le \frac{1}{{\epsilon }^2}\mathrm{E}[S_n^2{\mathrm{𝟏}}_{\mathrm{\Lambda }}]\le \frac{1}{{\epsilon }^2}\mathrm{E}[S_n^2].$

定理得证。