proof of Kolmogorov’s inequality

For $k=1,2,\mathrm{\dots },n$, let $A_k$ be the event that $|S_k|\ge \lambda$ but for all $i=1,2,\mathrm{\dots },k-1$. Note that the events $A_1$, $A_2,\mathrm{\dots },A_n$ are disjoint, and

$$\bigcup _{k=1}^n{A}_k=\{\underset{1\le k\le n}{\max }|S_k|\ge \lambda \}.$$

Let $I_A$ be the indicator function of event $A$. Since $A_1$, $A_2,\mathrm{\dots },A_n$ are disjoint, we have

$$0\le \sum _{k=1}^n{I}_{A_k}\le 1.$$

Hence, we obtain

$$\sum _{k=1}^n\text{Var}[X_k]=E[S_n^2]\ge \sum _{k=1}^{n}E[S_n^2{I}_{A_k}].$$

After replacing $S_n^2$ by $S_k^2+2S_k(S_n-S_k)+{(S_n-S_k)}^2$, we get

${\displaystyle \sum _{k=1}^n}\text{Var}[X_k]$ $\ge {\displaystyle \sum _{k=1}^n}E[(S_k^2+2S_k(S_n-S_k)+{(S_n-S_k)}^2)I_{A_k}]$

$\ge {\displaystyle \sum _{k=1}^n}E[(S_k^2+2S_k(S_n-S_k))I_{A_k}]$

$={\displaystyle \sum _{k=1}^n}E[S_k^2{I}_{A_k}]+2{\displaystyle \sum _{k=1}^n}E[S_n-S_k]E[S_k{I}_{A_k}]$

$={\displaystyle \sum _{k=1}^n}E[S_k^2{I}_{A_k}]$

$\ge {\lambda }^2{\displaystyle \sum _{k=1}^n}E[I_{A_k}]$

$={\lambda }^2{\displaystyle \sum _{k=1}^n}\mathrm{Pr}(A_k)$

$={\lambda }^2\mathrm{Pr}\left({\displaystyle \bigcup _{k=1}^n}{A}_k\right)$

$={\lambda }^2\mathrm{Pr}\left(\underset{1\le k\le n}{\max }|S_k|\ge \lambda \right),$

where in the third line, we have used the assumption that $S_n-S_k$ is independent of $S_k{I}_{A_k}$.

Title	proof of Kolmogorov’s inequality
Canonical name	ProofOfKolmogorovsInequality
Date of creation	2013-03-22 17:48:35
Last modified on	2013-03-22 17:48:35
Owner	kshum (5987)
Last modified by	kshum (5987)
Numerical id	4
Author	kshum (5987)
Entry type	Proof
Classification	msc 60E15