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 > 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) < \infty$, then $(S_n)_{n\ge 1}$ converges almost surely. 
gf
 A: 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|<\lambda\text{ for }j<k\}$, $k=1,\ldots,n$. Moreover, we have
\begin{align*}
\mathbb P(A_k) &\le\lambda^{-2}\mathbb E[S_k^2\mathbf1_{A_k}]\\
&\le\lambda^{-2}\mathbb E[\big(S_k^2+(S_n-S_k)^2\big)\mathbf1_{A_k}]\\
&=\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.)
A: Well, you have that $S_n$ is a martingale. 


*

*To show the inequality, apply Doob's martingale inequality.

*To show convergence, apply Levy martingale convergence theorem.
A: 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} & \text{if } \max_{1\leq j\leq i}S_{j}<\lambda \\
Z_{i} & \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|>\delta \hspace{1mm} \text{for some}\hspace{1mm} n\geq N\right)=\lim_{m\rightarrow \infty}\mathbb P\left(|S_n-S_N|>\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<\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<\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}|>\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>0$,
$$\lim_{N\rightarrow\infty}\mathbb P\left(|S_n-S_N|>\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.
