Kolmogorov's Inequality - Proof

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 is a martingale. Without loss of generality, we can assume that and for all . Define as follows. Let, and

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.

for all . Then is also a martingale. Since is independent and mean zero,

\begin{align} \sum_{i=1}^n \text{E} &= \sum_{i=1}^n \text{E} \\ &= \sum_{i=1}^n \text{E}\left \\ &= \sum_{i=1}^n \text{E}\left - 2\text{E}\left\\ &= \text{E} - \text{E} = \text{E}. \end{align}

The same is true for . Thus

\begin{align} \text{Pr}\left( \max_{1 \leq i \leq n} S_i \geq \lambda\right) &= \text{Pr} \\ &\leq \frac{1}{\lambda^2} \text{E} =\frac{1}{\lambda^2} \sum_{i=1}^n \text{E} \\ &\leq \frac{1}{\lambda^2} \sum_{i=1}^n \text{E} =\frac{1}{\lambda^2} \text{E} = \frac{1}{\lambda^2} \text{Var} \end{align}

by Chebyshev's inequality.

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

Read more about this topic:  Kolmogorov's Inequality

Famous quotes containing the word proof:

    “It comes to pass oft that a terrible oath, with a swaggering accent sharply twanged off, gives manhood more approbation than ever proof itself would have earned him.”
    —William Shakespeare (1564–1616)

    “The fact that several men were able to become infatuated with that latrine is truly the proof of the decline of the men of this century.”
    —Charles Baudelaire (1821–1867)

    “a meek humble Man of modest sense,
    Who preaching peace does practice continence;
    Whose pious life’s a proof he does believe,
    Mysterious truths, which no Man can conceive.”
    —John Wilmot, 2d Earl Of Rochester (1647–1680)