Kolmogorov's maximal inequality and convergence of random series. Let $(X_n)_{n\ge 1}$ be a sequence of mutually independent random variables, on the same probability space, with expectation 0 and finite variance. Let $S_n = \sum_{l=1}^n X_l$. Prove that for any $\lambda &gt; 0$,

$$\lambda^2 \displaystyle P \left(\max_{1\le k\le n} \big| S_k \big| \ge \lambda \right) \le Var(S_n)$$

Prove that if $\sum_l Var(X_l) &lt; \infty$, then $(S_n)_{n\ge 1}$ converges almost surely. 

gf
There's a more elementary proof which avoids the use of martingales$^1$. Observe that the event $\{\max_{1\le k\le n}|S_k|\ge\lambda\}$ is the disjoint union of the events $A_k=\{|S_k|\ge\lambda,|S_j|&lt;\lambda\text{ for }j&lt;k\}$, $k=1,\ldots,n$. Moreover, we have

\begin{align*}
\mathbb P(A_k) &amp;\le\lambda^{-2}\mathbb E[S_k^2\mathbf1_{A_k}]\\
&amp;\le\lambda^{-2}\mathbb E[\big(S_k^2+(S_n-S_k)^2\big)\mathbf1_{A_k}]\\
&amp;=\lambda^{-2}\mathbb E[\big(S_k^2+2S_k(S_n-S_k)+(S_n-S_k)^2\big)\mathbf1_{A_k}],
\end{align*}
where the last line follows since $S_k\mathbf1_{A_k}$ and $S_n-S_k$ are independent and $\mathbb E[S_n-S_k]=0$. Thus we have

$$\mathbb P(A_k)\le\lambda^{-2}\mathbb E[\big(S_k+(S_n-S_k)\big)^2\mathbf1_{A_k}]=\lambda^{-2}\mathbb E[S_n^2\mathbf1_{A_k}]$$

and so summing over $k$ we find

$$\mathbb P\left(\max_{1\le k\le n}|S_k|\ge\lambda\right)\le\lambda^{-2}\mathbb E[S_n^2\mathbf1_{\max_{1\le k\le n}|S_k|\ge\lambda}]\le\lambda^{-2}\mathbb  E[S_n^2].$$



$1$. I have always found the use of martingales here unsatisfactory. Kolmogorov's inequality is often used to prove the Strong Law of Large Numbers which I imagine most would encounter before martingales in a first course in rigorous probability theory. Moreover, one of the existing answers here lifts directly from Wikipedia - aside from the blatant plagiarism, that proof has some issues. (E.g. it assumes both $\mathbb E[S_i]=0$ and $S_i\ge0$, it does not justify why $Z_n$ is a martingale, etc.)
For the Inequality:

This argument employs discrete martingales. The sequence $S_1,S_2,...,S_n$ is a martingale. Without loss of generality, we can assume that $S_{0}=0$ and $S_{i}\geq 0\forall i$.

Define: $(Z_i)_{i=0}^{n}$ as follows: Let $Z_{0}=0$, and 

$$
Z_{i+1} =
\begin{cases}
S_{i+1} &amp; \text{if } \max_{1\leq j\leq i}S_{j}&lt;\lambda \\
Z_{i} &amp; \text{otherwise}
\end{cases}
$$

$\forall i$. Then $(Z_{i})_{i=0}^{n}$ is also a martingale.

Since $S_{i}-S_{i-1}$ is indepenent and mean $0$,

$$\sum_{i=1}^{n}\mathbb E\left[\left(S_{i}-S_{i-1}\right)^2\right]=$$

$$\sum_{i=1}^{n}\mathbb E\left[S_{i}^{2}-2S_{i}S_{i-1}+S_{i-1}^{2}\right]=$$

$$\sum_{i=1}^{n}\mathbb E\left[S_{i}^{2}-2(S_{i-1}+S_{i}-S_{i-1})S_{i-1}+S_{i-1}^2\right]=$$

$$\sum_{i=1}^{n}\mathbb E\left[S_{i}^2-S_{i-1}^{2}\right]-2\mathbb E\left[S_{i-1}\left(S_{i}-S_{i-1}\right)\right]=$$

$$\mathbb E\left[S_{n}^2\right]-\mathbb E\left[S_{0}^{2}\right]=\mathbb E\left[S_{n}^{2}\right]$$

The same is true for $\displaystyle \left(Z_{i}\right)_{i=0}^{n}$. Thus,

$$\mathbb P\left(\max_{1\leq i\leq n}S_{i}\geq \lambda\right)=\mathbb P\left[Z_{n}\geq\lambda\right]$$

$$\leq \frac{1}{\lambda^2}\mathbb E\left[Z_{n}^{2}\right]=\frac{1}{\lambda^2}\sum_{i=1}^{n}\mathbb E\left[\left(Z_{i}-Z_{i-1}\right)^2\right]$$

$$\leq\frac{1}{\lambda^2}\sum_{i=1}^{n}\mathbb E\left[\left(S_{i}-S_{i-1}\right)^2\right]=\frac{1}{\lambda^2}\mathbb E\left[S_{n}^2\right]=\frac{1}{\lambda^2}\mathrm{Var}\left[S_{n}\right]$$
by Chebyshev's inequality.

Multiplying through by $\lambda$, we get
$$\lambda^2\mathbb P\left(\max_{1\leq k\leq n}S_{i}\geq \lambda\right)\leq \mathrm{Var}\left(S_{n}\right)$$



To show convergence:

A series converges if and only if it satisfies the Cauchy criterion. To check the latter, consider $N$ and consider

$$\mathbb P\left(|S_n-S_N|&gt;\delta \hspace{1mm} \text{for some}\hspace{1mm} n\geq N\right)=\lim_{m\rightarrow \infty}\mathbb P\left(|S_n-S_N|&gt;\delta\hspace{1mm}\text{for some}\hspace{1mm} N\leq n\leq N+m\right)$$

Thus, for fixed $N$, $m$, we must estimate the probability of the event 

$$\displaystyle \delta&lt;\max_{1\leq k\leq m}|S_{N+k}-S_{N}|$$

For a fixed $k$ we can use Chebyshev's inequality to get 

$$\mathbb P\left(\delta&lt;\max_{1\leq k\leq m}|S_{N+k}-S_{N}|\right)\leq \delta^{-2}\mathrm{Var}\left(X_{N}+X_{N+1}+...+X_{N+m}\right)$$

However we don't have a technique for controlling the maximum of $\displaystyle |S_{N+k}-S_{N}|$ over $k=1,2,...,m$

Hence we need Kolmogorov's maximal inequality:

Using the inequality, we obtain:

$$\mathbb P\left(|S_{n}-S_{N}|&gt;\delta\hspace{1mm}\text{for some}\hspace{1mm} N\leq n\leq N+m\right)\leq \delta^{-2}\sum_{k=N}^{N+m}\mathrm{Var}(X_{k})\leq \delta^{-2}\sum_{k=N}^{\infty}\mathrm{Var}(X_{k})$$

The right hand side goes to zero as $N\rightarrow \infty$, thus we conclude that for any $\delta&gt;0$,

$$\lim_{N\rightarrow\infty}\mathbb P\left(|S_n-S_N|&gt;\delta\hspace{1mm} \text{for some}\hspace{1mm}n\geq N\right)=0$$

This implies that:

$$\limsup S_{n}-\liminf S_{n}\leq \delta$$

almost surely. Take intersection over $\delta+\frac{1}{k}$, $k=1,2,...$ to get that $S_{n}$ converges almost surely.