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

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.

• The proof of the inequality seems to be almost verbatim taken from Wikipedia... – Jason Jul 5 '17 at 20:43
• Additionally, assume both $\mathbb E[S_i]=0$ and $S_i\ge0$ is a contradiction. (This also appears in the Wikipedia article.) – Jason Jul 5 '17 at 20:45
• -1. Second @Jason. – Hans Jul 24 '17 at 7:10

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.)

Well, you have that $S_n$ is a martingale.

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

2. To show convergence, apply Levy martingale convergence theorem.

• Can I ask what is the statement of the Levy martingale convergence theorem? I searched google for it but I'm not sure which result is relevant. – Chris Apr 12 '13 at 6:17