# Almost sure convergence via pairwise independence

If ${A_1,A_2,...}$ are pairwise independent and ${\sum_{n=1}^{\infty}P(A_n)=\infty}$ then as ${n \rightarrow \infty}$

$\displaystyle \boxed{ \frac{\sum_{m=1}^{n}\mathbb{I}_{A_m}}{\sum_{m=1}^{n}P(A_m)} \xrightarrow{a.s.} 1 }$

Proof:

Let ${X_m = \mathbb{I}_{A_m}}$ and ${S_n = X_1+...+Xn}$. Since ${A_m}$ are pairwise independent, the ${X_m}$ are uncorrelated and thus

$\displaystyle var(S_n) = var(X_1) + ... + var(X_n)$

Since ${X_m \in \{0,1 \}}$

$\displaystyle var(X_m) \leq \mathbb{E}[X_m^2] = \mathbb{E}[X_m] \Rightarrow var(S_n) \leq \mathbb{E} [S_n]$

Now using the Chebyshev’s inequality

$\displaystyle P[ |S_n - \mathbb{E}[S_n] > \delta \mathbb{E}[S_n]] \leq \frac{var(S_n)}{(\delta \mathbb{E}[S_n])^2} = \frac{1}{\delta^2 \underbrace{ \mathbb{E}[S_n]}_{ \substack{ \infty \\ \text{ by assumption}} } } \rightarrow 0 , \qquad n \rightarrow \infty$

Hence

$\displaystyle \frac{S_n}{\mathbb{E}[S_n]} \xrightarrow{p} 1$

For a.s. convergence we have to take subsequences. Let

$\displaystyle n_k = \inf \{ n: \mathbb{E}[S_n] \geq k^2 \} \text{ and } T_k = S_{n_k}$

Then

$\displaystyle P( |T_k - \mathbb{E}[T_k] > \delta \mathbb{E}[T_k]) \leq \frac{1}{\delta^2 \underbrace{ \mathbb{E}[T_k]}} \leq \frac{1}{\delta^2 \underbrace{ k^2}_{ \substack{ \text{since} \\ k^2 \leq \mathbb{E}[T_k] \leq k^2+1 } }}$

So

$\displaystyle \sum_{k=1}^{\infty} P( |T_k - \mathbb{E}[T_k] > \delta \mathbb{E}[T_k]) < \infty$

and the Borel-Cantelli lemma implies

$\displaystyle P( |T_k - \mathbb{E}[T_k] > \delta \mathbb{E}[T_k] \text{ i.o.}) = 0$

which means that

$\displaystyle \frac{T_k}{\mathbb{E}[T_k]} \xrightarrow{a.s.} 1$

Now pick an ${\omega}$ s.th. ${T_k(\omega)/ \mathbb{E}[T_k] \rightarrow 1}$ and observe that if ${n_k \leq n < n_{k+1}}$ then

$\displaystyle \frac{T_k(\omega)}{ \mathbb{E}[T_{k+1}]} \leq \frac{S_n}{\mathbb{E}[S_n]} \leq \frac{T_{k+1}(\omega)}{\mathbb{E}[T_k]}$

or

$\displaystyle \frac{\mathbb{E}[T_k]}{ \mathbb{E}[T_{k+1}]} \frac{T_k(\omega)}{ \mathbb{E}[T_{k}]} \leq \frac{S_n}{\mathbb{E}[S_n]} \leq \frac{T_{k+1}(\omega)}{\mathbb{E}[T_k+1]} \frac{\mathbb{E}[T_{k+1}]}{ \mathbb{E}[T_{k}]}$

But since

$\displaystyle k^2 \leq \mathbb{E}[T_k] \leq \mathbb{E}[T_{k+1}] \leq (k+1)^2+1$

we have that ${ \frac{\mathbb{E}[T_{k+1}]}{ \mathbb{E}[T_{k}]} \rightarrow 1}$ and hence the terms at the right and left ends both ${\rightarrow 1}$.

References:

A.N. Shiryaev (1996), Probability, Springer

W. Feller (1971), An Introduction to Probability Theory and Its Applications, Vol.2. John Wiley & Sons (NY)

R. Durrett (2010). Probability: Theory and Examples, Cambridge University Press

O. Kallenberg (2006),  Foundations of modern probability, Springer