柯尔莫哥洛夫不等式

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

不等式的陈述
设\{X_n\}是独立的随机变量序列，并且对所有正整数i，第i个随机变量的期望E[X_i]=0，方差\operatorname{var}(X_i)=E[X_i^2]是有限的，那么对于任意\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项的部分和。

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

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

证明
对于给定的 \varepsilon>0, 记事件

: \Lambda = \left\{ \max_{1\le j\le n}|S_j|\ge \varepsilon\right\}.

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

: \Lambda_k = \left\{ \max_{1\le j \le k-1} |S_j|

注意到 \Lambda_k 两两不交, 构成了 \Lambda 的划分, 即 \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}

这里\mathbf{1}_\Lambda = \begin{cases}1,&\omega \in \Lambda,\\ 0,& \omega\notin \Lambda.\end{cases}.

因为 S_k \mathbf{1}_{\Lambda_k} 与 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) \ge \sum_{k=1}^n \operatorname{E}[S_k^2 \mathbf{1}_{\Lambda_k} ]

又因为 \operatorname{E}[S_k^2\mathbf{1}_{\Lambda_k}] \ge \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} ] \ge \varepsilon^2 \sum_{k=1}^n \Pr[\Lambda_k] = \varepsilon^2 \Pr[\Lambda].

这样就证明了

: \Pr[\Lambda] \le \frac{1}{\varepsilon^2} \operatorname{E}[S_n^2\mathbf{1}_\Lambda] \le \frac{1}{\varepsilon^2} \operatorname{E}[S_n^2].
定理得证。

参考文献