# Is the following reasoning regarding the Law of Large Numbers beyond an i.i.d assumption valid?

Assume that $X_i$ is not independent nor identically distributed to $X_j$ for $i≠j$.  Then $$E[\bar X]=E[\frac 1n ∑_{k=1}^nX_k ]=\frac 1n ∑_{k=1}^nμ_k$$ $$Var[\bar X]=Var[\frac 1n ∑_{k=1}^nX_k ]=\frac{1}{n^2} Var[∑_{k=1}^nX_k ]$$ $$P(|\bar X-E[\bar X]|≥ε)≤\frac{Var[\bar X]}{ε^2}$$ $$P(|\bar X-E[\bar X]|≥ε)≤\frac{Var[∑_{k=1}^nX_k ]}{n^2 ε^2}$$ $$Var[∑_{k=1}^nX_k ]= ∑_{k=1}^nVar[X_k]+2∑_{i≠j;i<j}Cov(X_i,X_j)$$ $$P(|\bar X-E[\bar X]|≥ε)≤\frac{∑_{k=1}^nVar[X_k ]}{n^2 ε^2}+\frac{2∑_{i≠j;i<j}Cov(X_i,X_j )}{n^2 ε^2}$$ $$P(|\bar X-E[\bar X]|≥ε)≤\frac{nAvg(Var[X_k ])}{n^2 ε^2}+\frac{2∑_{i≠j;i<j}Cov(X_i,X_j)}{n^2 ε^2}$$ $$P(|\bar X-E[\bar X]|≥ε)≤\frac{Avg(Var[X_k ])}{nε^2}+\frac{2∑_{i≠j;i<j}Cov(X_i,X_j )}{n^2 ε^2}$$  There are ${n \choose 2}=\frac{n(n-1)}{2}$ terms in $∑_{i≠j;i<j}Cov(X_i,X_j )$  Let $Cov(X_i,X_j )^*$ be the average Covariance: $$\frac{n(n-1)}{2} Cov(X_i,X_j )^*=∑_{i≠j;i<j}Cov(X_i,X_j )$$ Then $$P(|\bar X-E[\bar X]|≥ε)≤\frac{Avg(Var[X_k ])}{nε^2}+\frac{2 \frac{n(n-1)}{2} Cov(X_i,X_j )^*}{n^2 ε^2}$$ $$P(|\bar X-E[\bar X]|≥ε)≤\frac{Avg(Var[X_k ])}{nε^2}+\frac {n(n-1)Cov(X_i,X_j )^*}{n^2 ε^2}$$ $$P(|\bar X-E[\bar X]|≥ε)≤\frac{Avg(Var[X_k ])}{nε^2}+\frac {(n-1)Cov(X_i,X_j )^*}{n ε^2}$$ $$P(|\bar X-E[\bar X]|≥ε)≤\frac{Avg(Var[X_k ])}{nε^2}+\frac{(n-1)}{n}\frac{Cov(X_i,X_j )^*}{ε^2}$$ $$\lim_{n\to \infty}\frac{(n-1)}{n}=1$$  ∴ Convergence requirement: $Cov(X_i,X_j )^*→0$ as $n→∞$  This means that as long as the average variance $(Avg(Var[X_k ]))$ is bounded above and the average covariance goes to zero as $n$ gets large, the Law of Large Numbers applies. 
Under these conditions: $P(|\bar X-E[\bar X]|≥ε)→0$ as $n→∞$ where $X_i$ is not independent nor identically distributed to $X_j$ for $i≠j$.

• The main issue is the covariance decay, which can be hard to guarantee. – Ian Dec 25 '17 at 23:53
• True, unless you can structure the random variable sequence so that each successive random variable is only added to the sequence if doing so will keep the cumulative sum of the covariances at 0. I guess the second term on the upper bound of Chebyshev's Inequality wouldn't matter in that case. – Alex Dec 26 '17 at 0:47