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

Solution 1:

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

Solution 2:

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 !

Solution 3:

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.

Solution 4:

Sorry again to unearth the topic, but I just can't leave a comment.

Afaik, the original result was published in S. Bernshtein, “Sur la loi des grands nombres”, Communications de la Société mathématique de Kharkow. 2-ée sé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.