Kolmogorov's inequality

In probability theory, Kolmogorov's inequality is a so-called "maximal inequality" that gives a bound on the probability that the partial sums of a finite collection of independent random variables exceed some specified bound. The inequality is named after the Russian mathematician Andrey Kolmogorov.

Contents 1 Statement of the inequality 2 Proof 3 See also 4 References

Statement of the inequality

Let X₁, ..., 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] < +∞ for k = 1, ..., n. Then, for each λ > 0,

<math>\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], </math>

where S_k = X₁ + ... + X_k.

Proof

The following argument is due to Kareem Amin and employs discrete martingales. As argued in the discussion of Doob's martingale inequality, the sequence <math>S_1, S_2, \dots, S_n</math> is a martingale. Without loss of generality, we can assume that <math>S_0 = 0</math> and <math>S_i \geq 0</math> for all <math>i</math>. Define <math>(Z_i)_{i=0}^n</math> as follows. Let <math>Z_0 = 0</math>, and

<math>Z_{i+1} = \left\{ \begin{array}{ll}

S_{i+1} & \text{ if } \displaystyle \max_{1 \leq j \leq i} S_j < \lambda \\ Z_i & \text{ otherwise} \end{array} \right. </math> for all <math>i</math>. Then <math>(Z_i)_{i=0}^n</math> is a also a martingale. Since <math>\text{E}[S_{i}] = \text{E}[S_{i-1}]</math> for all <math>i</math> and <math>\text{E}[\text{E}[X|Y]] = \text{E}[X]</math> by the law of total expectation,

<math>\begin{align}

\sum_{i=1}^n \text{E}[ (S_i - S_{i-1})^2] &= \sum_{i=1}^n \text{E}[ S_i^2 - 2 S_i S_{i-1} + S_{i-1}^2 ] \\ &= \sum_{i=1}^n \text{E}\left[ S_i^2 - 2 \text{E}[ S_i S_{i-1} | S_{i-1} ] + \text{E}[S_{i-1}^2 | S_{i-1}] \right] \\ &= \sum_{i=1}^n \text{E}\left[ S_i^2 - 2 \text{E}[ S^2_{i-1} | S_{i-1} ] + \text{E}[S_{i-1}^2 | S_{i-1}] \right] \\ &= \text{E}[S_n^2] - \text{E}[S_0^2] = \text{E}[S_n^2]. \end{align} </math> The same is true for <math>(Z_i)_{i=0}^n</math>. Thus

<math>\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} </math> by Chebyshev's inequality.

See also

• Chebyshev's inequality
• Doob's martingale inequality
• Etemadi's inequality
• Landau-Kolmogorov inequality
• Markov's inequality

References

• Billingsley, Patrick (1995). Probability and Measure. New York: John Wiley & Sons, Inc.. ISBN 0-471-00710-2.  (Theorem 22.4)
• Feller, William [1950] (1968). An Introduction to Probability Theory and its Applications, Vol 1, Third Edition (in English), New York: John Wiley & Sons, Inc., xviii+509. ISBN 0-471-25708-7. 

---

This article incorporates material from Kolmogorov's inequality on PlanetMath, which is licensed under the GFDL.