Derive the LLN for a certain sequence

Question

I have a sequence of dependent random variables $X_1, X_2...X_n$. Each RV is correlated with two other RVs and uncorrelated with the others.The ones that are correlated satisfy the condition $Cov(X_i,X_j) \le \frac{1}{n^2}$

I need to:

1. Derive an upper bound on the variance of the sample mean $\sum_{i=1}^n\frac{X_i}{n}$
2. Derive a version of the LLN for the sequence

I'm not really sure where to start with this. I do know that the LLN says that as $n$ approaches infinity, the sample mean will approach $E(X)$, the expected value of the RV. But I don't understand how to derive a "version of it for this sequence, or even what "version" means here. I also don't know how to find an upper bound for the variance. We have used concentration inequalities to bound the sample mean... would I just somehow extend one of those (like Chebyshev's?) to apply to the variance?

Thank you for your help!

Answer 1

Hint: $$\operatorname{var}\left(\sum_{i=n}^n X_i\right) = \sum_{i=1}^n \operatorname{var}(X_i) + \sum_{i=1}^n \sum_{j=1; j \neq i}^n \operatorname{cov}(X_i,X_j)\tag{1}$$ How many terms in that double sum on the right are nonzero? What is the maximum value that these terms can have?

---

The question is very poorly formulated and both parts do not necessarily have an answer.

Assume that $n$ is a fixed number.

We are given that $X_i, 1 \leq i \leq n$ are dependent random variables such that each $X_i$ is correlated with $2$ other $X_j$ but uncorrelated with all the others. Furthermore, both of the two nonzero covariances $\operatorname{cov}(X_i,X_{j_{1}})$ and $\operatorname{cov}(X_i,X_{j_{2}})$ are no larger than $n^{-2}$. (Curiously, this upper bound on the covariances does not involve the variances of the random variables at all, and thus seems more like a bound on the (Pearson) correlation coefficients). So the $n\times n$ covariance matrix $C$ with entries $C_{i,j} = \operatorname{cov}(X_i,X_{j})$ has three nonzero entries in each row: one entry (on the diagonal) being a variance and the other two off-diagonal entries being at most $n^{-2}$.

Can such a covariance matrix exist? Yes, for example, suppose that only the following pairs of random variables are correlated: $$(X_1,X_2),~ (X_2,X_3),~ (X_3,X_4),~ \ldots,~ (X_{n-1},X_n),~ (X_n,X_1).$$ The covariance matrix in this case is a tri-diagonal matrix with two additional nonzero entries at $(n,1)$ and $(1,n)$. Note, however, that this correlation structure cannot be expanded to include a $(n+1)$-th random variabe $X_{n+1}$.

So, applying what was hinted at above in $(1)$, we get that $$\begin{align} \operatorname{var}\left(\sum_{i=n}^n X_i\right) &= \sum_{i=1}^n \operatorname{var}(X_i) + \sum_{i=1}^n \sum_{j=1; j \neq i}^n \operatorname{cov}(X_i,X_j)\\ &\leq \sum_{i=1}^n \operatorname{var}(X_i) + 2n\cdot n^{-2} &{\scriptstyle{\text{only}~2n~\text{terms are nonzero}}}\\ \operatorname{var}\left(\sum_{i=n}^n X_i\right) &\leq \sum_{i=1}^n \operatorname{var}(X_i) + \frac{2}{n}\tag{2}\\ \operatorname{var}\left(\frac 1n\sum_{i=n}^n X_i\right) &\leq \frac{1}{n^2}\sum_{i=1}^n \operatorname{var}(X_i) + \frac{2}{n^3}\tag{3} \end{align}$$ and if all the random variables have the same variance $\sigma^2$, then $$\operatorname{var}\left(\frac 1n\sum_{i=n}^n X_i\right) \leq \frac{\sigma^2}{n} + \frac{2}{n^3}.\tag{4}$$ This result is also found in @AlecosPapadopoulos's answer to this question.

Returning to $(1)$, note that variances are nonnegative numbers, and thus it must be that $$\sum_{i=1}^n \sum_{j=1; j \neq i}^n \operatorname{cov}(X_i,X_j) \geq -\sum_{i=1}^n \operatorname{var}(X_i).\tag{5}$$ Since there are only $2n$ nonzero terms on the left side of $(5)$, the average of the $2n$ nonzero covariances is bounded below by the negative of half the average variance. For the special case of all variances being $\sigma^2$ and all the nonzero covariances being equal, we have the peculiar result that $$-\frac{\sigma^2}{2} \leq \operatorname{cov}(X_i,X_j) \leq \frac{1}{n^2}.$$

---

Things are equally strange when one tries to derive a Law of Large Numbers type result in this schema and so we are looking at increasing values of $n$ instead of just a fixed integer value. Assume without loss of generality that $X_1$ and $X_2$ are correlated, and thus $$\operatorname{cov}(X_1,X_2) \leq \frac{1}{n^2}.$$ Since this must hold whether we are looking at $n=10$ or $n=100$ or $n=1000$ etc., we conclude that the upper bound on the nonzero correlations must be $0$, and since these covariances are supposed to be nonzero, it must be that all the nonzero covariances are strictly negative numbers. The alternative, that the $X_1$ and $X_2$ in the list $X_1, X_2, \ldots, X_{10}$ are not the same as the $X_1$ and $X_2$ in the list $X_1, X_2, \ldots, X_{100}$ is too dreadful to contemplate. There is also the issue of what the covariance matrix looks like since the structure described above cannot be extended. As noted in Alecos's answer, we need to modify the statement that "each random variable is correlated with exactly two other random variables" to something like "each random variable (with the possible exception of one or two) is correlated with exactly two other random variables". And of course, in the absence of any information about the variances of the random variables, we cannot guarantee any kind of law of large numbers result. $\operatorname{var}(X_i)$ being finite for all $i$ is insufficient; we need the variance of the sample mean to approach $0$ as $n \to \infty$.

Answer 2

Expanding on @DilipSarwate hint,

$$\operatorname{Var}\left(\frac 1n\sum_{i=n}^n X_i\right) =\frac 1{n^2} \sum_{i=1}^n \operatorname{var}(X_i) + \frac 1{n^2}\sum_{i=1}^n \sum_{j=1; j \neq i}^n \operatorname{cov}(X_i,X_j)$$

We have to determine carefully the number of non-zero covariances. We are told:

"Each RV is correlated with two other RVs and uncorrelated with the others"

This means that, e.g., $X_1, X_2, X_3$ are correlated between them, and none of the three is correlated with any other variable. So we have subsets of three random variables each providing in total six covariance terms, because each pair-wise covariance appears twice in the double sum.

This affects the total number of non-zero covariance depending on whether $n$ is exactly divisible by $3$, or not.

Assume first that $n$ is exactly divisible by $3$. Then the total number of non zero covariances is $6\cdot \frac n3 = 2n $

Then

$$\frac 1{n^2}\sum_{i=1}^n \sum_{j=1; j \neq i}^n \operatorname{cov}(X_i,X_j) \leq \frac 1{n^2}\cdot 2n\cdot \frac 1{n^2} = \frac 2{n^3} \tag{1}$$

Assume now that we increase $n$ by $1$. All variables up to index $n$ (which is divisible by three exactly), have exhausted their non-zero covariances between them, so the last variable cannot be correlated with any other variable. So we conclude that in this case, the upper bound for the covariance-double sum is the same.

Finally assume that now $n$ is such that division by three leaves $2$ as remainder. Using the same logic as before, we conclude that two more non-zero covariance terms appear (two times the covariance of the two "additional" random variables). Denote this $n_2 = n+2$. Then the non-zero covariance terms here are $2n +2 = 2(n+1)$, and the upper bound for the covariance term becomes

$$\frac 1{n_2^2}\sum_{i=1}^{n_2} \sum_{j=1; j \neq i}^{n_2} \operatorname{cov}(X_i,X_j) \leq \frac 1{n_2^2}\cdot 2(n+1)\cdot \frac 1{n_2^2} = \frac {2(n+1)}{(n+2)^4} \tag{2}$$

It is easy to check that the right-hand side of $(2)$ is smaller than the right-hand side of $(1)$ and so we conclude that for any finite $n$, the upper bound for the variance of the sample mean is

$$\sup_n\operatorname{Var}\left(\frac 1n\sum_{i=n}^n X_i\right) = \frac {\operatorname{var}(X)}{n} + \frac{2}{n^3}$$

(where we have assumed identical marginal distributions), since more over the sum-of-variances term declines with $n$.

Then a "version" of the Weak Law of Large Numbers would go

$$\Big\{E(\bar X_n) = E(X),\;\; \lim_{n\rightarrow \infty}\sup_n\operatorname{Var}\left(\bar X_n\right) = 0\Big\} \Rightarrow \bar X_n \xrightarrow{p} E(X)$$