# Weak Law of Large Numbers for Dependent Random Variables with Bounded Covariance

I'm currently stuck on the following problem which involves proving the weak law of large numbers for a sequence of dependent but identically distributed random variables. Here's the full statement:

• Let $(X_n)$ be a sequence of dependent identically distributed random variables with finite variance.

• Let $\displaystyle S_n = \sum_{i=1}^n X_i$ denote the $n^\text{th}$ partial sum of the random variables $(X_n)$.

• Assume that Cov$(X_i,X_j) \leq c^{|i-j|}$ for $i, j \leq n$ where $|c| \leq 1$.

Is it possible to show that $\displaystyle \frac{S_n}{n} \rightarrow \mathbb{E}[X_1]$ in probability? In other words, is it true that given any $\epsilon>0$,

$$\lim_{n\rightarrow \infty} \mathbb{P}\bigg[\Big|\frac{S_n}{n} - \mathbb{E}[X_1]\Big| > \epsilon\bigg] = 0$$

EDIT: Following some comments, it turns out that I had the right approach so I've gone ahead and answered my own question below.

-
I should add that I've tried using the Chebyshev inequality, but can't get the right kind of bound - so I suspect that there must be another way. – Elements Nov 26 '12 at 23:44
no, that's right, you should be able to show $\sigma^2(\frac { S_n} n) \rightarrow 0$ – mike Nov 26 '12 at 23:55
@mike Hmm I suspect I may not be using the right bounds... See above – Elements Nov 27 '12 at 0:31

Fix $\epsilon > 0$ and $n \in \mathbb{N}$, then we can use Chebyshev's inequality to see that

$$\mathbb{P}\bigg[\Big|\frac{S_n}{n} - \mathbb{E}[X_1]\Big| > \epsilon\bigg] \leq \frac{\text{Var}\Big(\frac{S_n}{n}\Big)}{\epsilon^2}$$

where

$$\displaystyle \text{Var}\Big(\frac{S_n}{n}\Big)= \frac{\text{Var}(S_n)}{n^2} \leq \frac{\sum_{i=1}^n\sum_{j=1}^n \text{Cov}{(X_i,X_j)}}{n^2} \leq \frac{\sum_{i=1}^n\sum_{j=1}^n c^{|i-j|}}{n^2}$$

We can then explicitly calculate the double sum $\sum_{i=1}^n\sum_{j=1}^n c^{|i-j|}$ as follows:

\begin{align} \sum_{i=1}^n\sum_{j=1}^n c^{|i-j|} &= \sum_{i=1}^n c^{|i-i|} + 2\sum_{i=1}^n\sum_{j=1}^{i-1} c^{|i-j|} \\ &= n + 2\sum_{i=1}^n\sum_{j=1}^{i-1} c^{|i-j|} \\ &= n + 2\sum_{i=1}^n\sum_{j=1}^{i-1} c^{i-j} \\ &= n + 2\sum_{i=1}^n c^i \frac{1 - c^{-i}}{1-c^{-1}} \\ &= n + 2\sum_{i=1}^n \frac{c^i + 1}{1-c^{-1}} \\ &= n + \frac{2c}{c-1} \sum_{i=1}^n c^{i}-1 \\ &= n + \frac{2c}{c-1} \big(\frac{1-c^{n+1}}{1-c} -n \big)\\ &= n + \frac{2c}{(c-1)^2}(c^{n+1}+1) + \frac{2c}{c-1}n\\ \ \end{align}

Thus,

$$\lim_{n\rightarrow\infty} \mathbb{P}\bigg[\Big|\frac{S_n}{n} - \mathbb{E}[X_1]\Big| > \epsilon\bigg] = \lim_{n\rightarrow\infty} \frac{\text{Var}\Big(\frac{S_n}{n}\Big)}{\epsilon^2} \leq \lim_{n\rightarrow\infty} \frac{n + \frac{2c}{(c-1)^2}(c^{n+1}+1) + \frac{2c}{c-1}n}{n^2 \epsilon^2} = 0$$

Seeing how our choice of $\epsilon$ was arbitrary, the statement above holds for any $\epsilon > 0$ and shows that $\frac{S_n}{n} \rightarrow E[X_1]$ in probability, as desired.

This shows the validity of the theorem for $c<1$, but not for $c=1$. We can easily extend the demonstration to all cases in which $|\mbox{Cov}(X_i,X_j)|\le f_{|i-j|}$ where $\lim_{i\to\infty}f_i=0$. Indeed in this case it is simple to show that $$\lim_{n\to\infty}{1\over n^2}\sum_{i=1}^n\sum_{j=1}^n \text{Cov}{(X_i,X_j)}\le \lim_{n\to\infty}{1\over n^2}\sum_{i=1}^n\sum_{j=1}^n |\text{Cov}{(X_i,X_j)}|\le \lim_{n\to\infty}{1\over n^2}\sum_{i=1}^n\sum_{j=1}^nf_{|i-j|}=0$$

-

I just wanted to add a reference for a similar result. This appears in Some new applications of Riesz products by Gavin Brown. I have adapted the notation to suit your question.

Proposition 1: Suppose that $(X_n)$ is a sequence of random variables of bounded modulus, $E(X_n) = \mu$ for all $n$ and that $$\sum_{N=1}^\infty \frac{1}{N} E(|Y_N|^2) < \infty$$ where $Y_N = \frac{1}{N} \sum_{n=1}^N (X_n - \mu)$. Then $Y_N \to 0$ almost surely.

Assume there exists some finite $M$ such that $|X_n -\mu| \leq M$ for all $n \in \mathbb Z^+$. Since $$E(|Y_N|^2) = \frac{1}{N^2}\sum_{i=1}^N\sum_{j=1}^N \text{Cov}(X_i,X_j) = \text{Var}\left(\frac{S_N}{N}\right)$$ Then $$\sum_{N=1}^\infty \frac{1}{N} E(|Y_N|^2) = \sum_{N=1}^\infty \frac{1}{N^3} \text{Var}(S_N)$$ As shown in the previous response, a consequence of the weak dependence assumption is that the right hand side is finite. By the above proposition, $Y_N \to 0$ almost surely. So $$Y_n = \frac{1}{N} \sum_{n=1}^N (X_n - \mu) = S_N - \mu \to 0$$ so $S_N \to \mu$ almost surely.

-

Sorry to unearth the topic, but I've got something here that might interest people, linked with this thread.

I ran across the following variant of your problem in T. Cacoullos Exercices in probability (Springer, 1989), exercice 254 : he calls it "theorem of Barnstein" (sic), but I couldn't find any clue about who this Barnstein is ; if it's a typo, then I don't know any variant of WLLN by Bernstein. Here's the statement :

Let $X_1, ..., X_n, ...$ be centered random variables. If there exist a constant $c>0$ such that for every, $i$, $\mathbf{V}[X_i] \leq c$ and if the following condition holds : $$\lim_{|i-j| \to +\infty} \mathrm{Cov}(X_i, X_j) = 0$$ Then, the weak law of large numbers hold.

This is a small generalization of your problem. The proof is very similar and consists in bounding the variance of $S_n /n$ in order to conclude with Chebyshev. To bound the variance, here's the argument (everything is very similar to what you wrote).

First, note that by Cauchy-Schwarz, $|\mathrm{Cov}(X_i, X_j)| \leq c$. Therefore, noting $S_n = X_1 + ... + X_n$, $$\mathbf{V}[S_n] \leq \sum_{i=1}^{n} c + 2\sum_{i=1}^n \sum_{j=i+1}^{n}\mathrm{Cov}(X_i, X_j)$$

Choose $\epsilon >0$, take $N$ such that $\forall |i-j|>N$, we have $\mathrm{Cov}(X_i, X_j) < \epsilon$. Now if $n$ is greater than $N$ (so we don't have problems with the indexes) split the sum over $j$ before and after $N$, so we have $$\sum_{i=1}^n \sum_{j=1}^{i-1}\mathrm{Cov}(X_i, X_j) = \sum_{i=1}^n \sum_{j=i+1}^{i+N}\mathrm{Cov}(X_i, X_j) + \sum_{i=1}^n \sum_{j=i+N+1}^{n}\mathrm{Cov}(X_i, X_j)$$ Invoking triangle inequality, we have

$$\left|\sum_{i=1}^n \sum_{j=1}^{i-1}\mathrm{Cov}(X_i, X_j) \right| \leq \sum_{i=1}^n Nc + \sum_{i=1}^n \sum_{j=i+N+1}^{n}\epsilon \leq nNc + n^2 \epsilon$$

Therefore, $$\mathbf{V}[S_n /n] \leq \frac{c}{n} + \frac{2Nc}{n} + \epsilon$$

This clearly proves that $\mathbf{V}[S_n /n] \to 0$ as $n \to + \infty$, ending the proof of the mysteriously so-called "theorem of Barnstein". I hope this will help someone !

-