# 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. 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 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$$

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 !

• It is Bernstein :) See here the history of LLN :)
– Roah
Mar 3 '19 at 5:23
• In the second long sum, do you mean $\sum_{i=1}^{n}\sum_{j=i+1}^{n}=\sum_{i=1}^{n}\sum_{j=i+1}^{i+N}+\sum_{i=1}^{n}\sum_{j=i+N+1}^{n}?$ I think you change every $\sum_{j=i+1}^{n}$ to $\sum_{j=1}^{i-1}$, perhaps they are equivalent? Oct 11 '19 at 14:51

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.

Afaik, the original result was published in S. Bernshtein, “Sur la loi des grands nombres”, Communications de la Société mathématique de Kharkow. 2-ée série, 16:1-2 (1918), 82–87. In hard-to-read form, as befits a classic.

Short proof (similar to proposed) of initial statement and generalizations for Riesz Means are in paper of V. V. Kozlov, T. Madsen, A. A. Sorokin, “On weighted mean values of weakly dependent random variables”, Moscow Univ. Math. Bull., 59:5 (2004), 36–39. Moreover, the note that conditions:

(1). $V[X_i]≤c$

(2) $\lim\limits_{|i-j| \to +\infty} \mathrm{Cov}(X_i, X_j) = 0$

can be weakened to:

(1'). $\sum\limits_{i=1}^n\mathbf{V}[X_i] = o(n^2)$

(2'). $|\mathrm{Cov}(X_i, X_j)| \le \varphi(|i-j|)$, where $\frac1n\sum\limits_{i=1}^n\varphi(i) \to 0$.

Unfortunately, both of this links are in Russian.

• You didn't give the links. Here they are, for reference: first article, and the second one. Apr 3 '16 at 16:33
• Congrats, you're in section 7 of Statistical Consequences of Fat Tails, by Nassim Nicholas Taleb. Apr 8 at 17:16