# proof of Kolmogorov’s inequality

For $k=1,2,\ldots,n$, let $A_{k}$ be the event that $|S_{k}|\geq\lambda$ but $|S_{i}|<\lambda$ for all $i=1,2,\ldots,k-1$. Note that the events $A_{1}$, $A_{2},\ldots,A_{n}$ are disjoint, and

 $\bigcup_{k=1}^{n}A_{k}=\Big{\{}\max_{1\leq k\leq n}|S_{k}|\geq\lambda\Big{\}}.$

Let $I_{A}$ be the indicator function of event $A$. Since $A_{1}$, $A_{2},\ldots,A_{n}$ are disjoint, we have

 $0\leq\sum_{k=1}^{n}I_{A_{k}}\leq 1.$

Hence, we obtain

 $\sum_{k=1}^{n}\text{Var}[X_{k}]=E[S_{n}^{2}]\geq\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}]$ $\displaystyle\geq\sum_{k=1}^{n}E[(S_{k}^{2}+2S_{k}(S_{n}-S_{k})+(S_{n}-S_{k})^% {2})I_{A_{k}}]$ $\displaystyle\geq\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\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}}]$ $\displaystyle\geq\lambda^{2}\sum_{k=1}^{n}E[I_{A_{k}}]$ $\displaystyle=\lambda^{2}\sum_{k=1}^{n}\Pr(A_{k})$ $\displaystyle=\lambda^{2}\Pr\Big{(}\bigcup_{k=1}^{n}A_{k}\Big{)}$ $\displaystyle=\lambda^{2}\Pr\Big{(}\max_{1\leq k\leq n}|S_{k}|\geq\lambda\Big{% )},$

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 ProofOfKolmogorovsInequality 2013-03-22 17:48:35 2013-03-22 17:48:35 kshum (5987) kshum (5987) 4 kshum (5987) Proof msc 60E15