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.



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.

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

  • $\begingroup$ 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. $\endgroup$ – Chris Apr 12 '13 at 6:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.