引理 5.1.2 (柯尔莫哥洛夫不等式)

引理 5.1.2 (柯尔莫哥洛夫不等式, Kolmogorov's inequality)

设 $X_1,X_2,\cdots$,为独立随机变量序列, 具有有限的数学期望和方差, 则对任意 $\epsilon >0$,有

$$P\left(\underset{1\le k\le n}{\sup }\left|\sum _{i=1}^k\left(X_i-E\left[X_i\right]\right)\right|\ge \epsilon \right)\le \frac{\sum _{k=1}^n\mathrm{Var}\left[X_k\right]}{{\epsilon }^2}.$$

证明

思路

这是一个比普通切比雪夫不等式更强的不等式，它控制了整个“最大偏差”，而不是某一时刻的偏差。

步骤 1：定义中心化过程

设

• $Y_k=X_k-\mathbb{E}[X_k]$，则 $S_k={\sum }_{i=1}^k{Y}_i$
• $S_0=0$

由于 $Y_1,\dots ,Y_n$ 是两两不相关，且 $\mathbb{E}[Y_k]=0$，所以有：

$$\mathrm{Var}[S_k]=\sum _{i=1}^k\mathrm{Var}[Y_i]$$

步骤 2：构造停时变量

定义停时：

$$\tau :=\min \left\{k\le n||S_k|\ge \epsilon \right\}$$

若没有这样的 $k$，设 $\tau =n+1$

定义辅助变量：

$$Z:=S_{\min (\tau ,n)}$$

则 $Z$ 是最多到第 $n$ 项的部分和，并在达到界限 $\epsilon$ 时“停止”。

步骤 3：应用期望估计

注意：

• 若 ${\max }_{k\le n}|S_k|\ge \epsilon$，则 $|Z|\ge \epsilon$
• $Z^2\le S_n^2$

因此，

$$\begin{array}{rl}& {\epsilon }^2\cdot P\left(\underset{k\le n}{\max }|S_k|\ge \epsilon \right)\\ & \le {\epsilon }^2\cdot P\left(|Z|\ge \epsilon \right)\\ & \le {\epsilon }^2\cdot {\int }_{|Z|\ge \epsilon }{f}_Z(z)dz\\ & \le {\int }_{|Z|\ge \epsilon }{\epsilon }^2{f}_Z(z)dz\\ & \le {\int }_{|Z|\ge \epsilon }{Z}^2{f}_Z(z)dz\\ & \le \mathbb{E}[Z^2]\\ & \le \mathbb{E}[S_n^2]\\ & =\mathrm{Var}[S_n]\\ & =\sum _{k=1}^n\mathrm{Var}[X_k]\end{array}$$

于是得到：

$$P\left(\underset{1\le k\le n}{\max }|S_k|\ge \epsilon \right)\le \frac{{\sum }_{k=1}^n\mathrm{Var}[X_k]}{{\epsilon }^2}$$

证毕。

备注

• 本不等式是 Kolmogorov 在 1933 年为证明大数法则提出的。
• 若 $X_k$ 是独立随机变量，该不等式仍成立。
• 若 $X_k$ 是鞅差序列，还可以用 Doob 最大不等式等方法证明。