Kolmogorov's inequality

Statement of the inequality

Let X1, ..., X**n : Ω → R be independent random variables defined on a common probability space (Ω, F, Pr), with expected value E[X**k] = 0 and variance Var[X**k] 0,

:\Pr \left(\max_{1\leq k\leq n} | S_k |\geq\lambda\right)\leq \frac{1}{\lambda^2} \operatorname{Var} [S_n] \equiv \frac{1}{\lambda^2}\sum_{k=1}^n \operatorname{Var}[X_k]=\frac{1}{\lambda^2}\sum_{k=1}^{n}\text{E}[X_k^2],

where S**k = X1 + ... + X**k.

The convenience of this result is that we can bound the worst case deviation of a random walk at any point of time using its value at the end of time interval.

Proof

The following argument employs discrete martingales. As argued in the discussion of Doob's martingale inequality, the sequence S_1, S_2, \dots, S_n is a martingale. Define (Z_i){i=0}^n as follows. Let Z_0 = 0, and :Z{i+1} = \left{ \begin{array}{ll} S_{i+1} & \text{ if } \displaystyle \max_{1 \leq j \leq i} | S_j | \end{array} \right. for all i. Then (Z_i)_{i=0}^n is also a martingale.

For any martingale M_i with M_0 = 0, we have that

\begin{align} \sum_{i=1}^n \text{E}[ (M_i - M_{i-1})^2] &= \sum_{i=1}^n \text{E}[ M_i^2 - 2 M_i M_{i-1} + M_{i-1}^2 ] \ &= \sum_{i=1}^n \text{E}\left[ M_i^2 - 2 (M_{i-1} + M_{i} - M_{i-1}) M_{i-1} + M_{i-1}^2 \right] \ &= \sum_{i=1}^n \text{E}\left[ M_i^2 - M_{i-1}^2 \right] - 2\text{E}\left[ M_{i-1} (M_{i}-M_{i-1})\right]\ &= \text{E}[M_n^2] - \text{E}[M_0^2] = \text{E}[M_n^2]. \end{align}

Applying this result to the martingale (S_i)_{i=0}^n, we have

\begin{align} \text{Pr}\left( \max_{1 \leq i \leq n} |S_i| \geq \lambda\right) &= \text{Pr}[|Z_n| \geq \lambda] \ &\leq \frac{1}{\lambda^2} \text{E}[Z_n^2] =\frac{1}{\lambda^2} \sum_{i=1}^n \text{E}[(Z_i - Z_{i-1})^2] \ &\leq \frac{1}{\lambda^2} \sum_{i=1}^n \text{E}[(S_i - S_{i-1})^2] =\frac{1}{\lambda^2} \text{E}[S_n^2] = \frac{1}{\lambda^2} \text{Var}[S_n] \end{align}

where the first inequality follows by Chebyshev's inequality.

This inequality was generalized by Hájek and Rényi in 1955.

References

• (Theorem 22.4)