# Kolmogorov’s Maximal Inequality

1. Let ${X_1, X_2,...,X_n}$ be independent random variables with ${ \mathbb{E}[X_i]=0, \mathbb{E}[X_i^2]< \infty }$. Set ${S_n = \sum_{i=1}^{n} X_n}$. Then ${\forall \varepsilon > 0}$

$\displaystyle \boxed{ P \left( \max_{1 \leq k \leq n} |S_K| \geq \varepsilon \right) \leq \frac{\mathbb{E}[S_n^2]}{\varepsilon^2} }$

Proof: Let

$\displaystyle \begin{array}{rcl} A &\equiv& \{ \max_{1 \leq k \leq n} |S_k| \geq \varepsilon \} ,\\ A_k &\equiv& \{ |S_i| < \varepsilon, i=1,...,k-1,|S_k| \geq \varepsilon \}, \qquad 1 \leq k \leq n \end{array}$

Notice that ${\cup_{i=1}^{n}A_k = A}$ and

1. $\displaystyle \begin{array}{rcl} \mathbb{E}[S_n^2] & \geq & \mathbb{E}[S_n^2 \mathbb{I}_A] \\ &=& \sum_{k=1}^{n}\left(\mathbb{E}[S_n^2 \mathbb{I}_{A_k}] \right) \\ &=& \sum_{k=1}^{n} \int_{A_k} S^2_n dP \\ &=& \sum_{k=1}^{n} \int_{A_k} \left( S^2_k + 2 S_k (S_n - S_k)+ (S_n - S_k)^2 \right) dP \\ &=& \sum_{k=1}^{n} \int_{A_k} S^2_k dP + 2 \underbrace{ \sum_{k=1}^{n} \int_{A_k} S_k (S_n - S_k)}_{0 \text{ since } S_k, (S_n-S_k) \text{ independent}}dP + \underbrace{ \sum_{k=1}^{n} \int_{A_k} (S_n - S_k)^2 }_{\geq 0} dP \\ &\geq& \sum_{k=1}^{n} \int_{A_k} S^2_k dP \geq \sum_{k=1}^{n} \varepsilon^2 P(A_k) = \varepsilon^2 P(A) = \varepsilon^2 P(\{ \max_{1 \leq k \leq n} |S_K| \geq \varepsilon \}) \end{array}$

$\Box$

2. If also ${P(|X_i| \leq c) =1, i \leq n}$, then

$\displaystyle \boxed{ P \left( \max_{1 \leq k \leq n} |S_K| \geq \varepsilon \right) \geq 1 - \frac{(c+\varepsilon)^2}{\mathbb{E}[S_n^2]} }$

Proof: Notice that

$\displaystyle \mathbb{E}[S_n^2 \mathbb{I}_A] = \mathbb{E}[S_n^2] - \mathbb{E}[S_n^2 \mathbb{I}_{A^c}] \geq \mathbb{E}[S_n^2] - \underbrace{ \varepsilon^2 P(A^c) }_{\text{By Markov Inequality}} = \mathbb{E}[S_n^2] - \varepsilon^2 + \varepsilon^2 P(A) \ \ \ \ \ (1)$

One the set ${A_k}$

$\displaystyle |S_{k-1}| \leq \varepsilon, \qquad |S_k| \leq |S_{k-1}| + |X_k| \leq \varepsilon + c$

and thus

$\displaystyle \begin{array}{rcl} \mathbb{E}[S_n^2 \mathbb{I}_A] &\underbrace{=}_{\text{by preceding proof}}& \sum_{k=1}^{n} \int_{A_k} \left( S_k+ (S_n - S_k) \right)^2 dP \\ &=& \sum_{k=1}^{n} \mathbb{E}[S_k^2\mathbb{I}_{A_k}] + \sum_{k=1}^{n} \mathbb{E}[(S_n-S_k)^2\mathbb{I}_{A_k}] \\ &\leq& (\varepsilon+c)^2 \sum_{k=1}^{n} P(A_k) + \sum_{k=1}^{n} P(A_k) \sum_{i=k+1}^{n}\mathbb{E}[X_i^2] \\ &\leq& P(A) \left[ (\varepsilon+c)^2 + \sum_{i=1}^{n}\mathbb{E}[X_i^2] \right] \\ &=& P(A)\left[ (\varepsilon+c)^2 + \mathbb{E}[S_n^2] \right] \end{array}$

Combining the above result and 1 we have

$\displaystyle P(A)\left[ (\varepsilon+c)^2 + \mathbb{E}[S_n^2] \right] \geq \mathbb{E}[S_n^2 \mathbb{I}_A] \geq \mathbb{E}[S_n^2] - \varepsilon^2 + \varepsilon^2 P(A)$

and hence

$\displaystyle P(A) \geq \frac{\mathbb{E}[S_n^2]- \varepsilon^2}{(\varepsilon+c)^2 + \mathbb{E}[S_n^2] - \varepsilon^2} = 1 - \frac{(\varepsilon+c)^2}{\varepsilon+c)^2+\mathbb{E}[S_n^2]-\varepsilon^2} \geq 1 - \frac{(c+\varepsilon)^2}{\mathbb{E}[S_n^2]}$

$\Box$