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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s