# Law of Large Numbers for “Approximately” iid samples

Let $Z$ be a random variable taking values from the finite set $\mathcal{Z}$ with pmf $p_Z$. Let $Z^n$ be a random iid vector drawn according to $p_Z^n$, then LLN states that the sample mean of $Z^n$ converges to the mean of $Z$ almost surely. Now, let $\mathbf{K}$ be a random vector taking values from $\mathcal{Z}^n$ with distribution $p_{\mathbf{K}}\approx p_Z^n$ (I'll make this approximation explicit below). Can we make a similar statement to that of LLN for the random vector $\mathbf{K}$?

By approximation we mean: there exists an $\epsilon>0$ such that: $$p_Z^n(\mathbf{k})e^{-\epsilon n}\le p_{\mathbf{K}}(\mathbf{k})\le p_Z^n(\mathbf{k})e^{+\epsilon n}$$ for all $\mathbf{k}\in\mathcal{Z}^n$. Moreover we can have $\epsilon\rightarrow 0$ as $n\rightarrow \infty$.

-

Let $m=\mathbb E(Z)$ and, for every $t\gt0$, $A_n(t)=\{z\in\mathcal Z^n\mid |z_1+\cdots+z_n-nm|\geqslant nt\}$. Cramér's principle of large deviations states that, for every $n$, $$\mathbb P(Z^n\in A_n(t))\leqslant\mathrm e^{-nI(t)},$$ for some positive $I(t)$, hence $$\mathbb P(K^n\in A_n(t))\leqslant\mathrm e^{-n(I(t)-\epsilon_n)}.$$ Under the hypothesis that $\epsilon_n\to0$, the RHS is summable hence the first Borel-Cantelli lemma implies that $K^n$ is in $A_n(t)$ for at most finitely many $n$, almost surely. Hence, for every positive $t$, $\limsup\limits_{n\to\infty}\left|\frac{K_1+\cdots+K_n}n-m\right|\leqslant t$, almost surely, that is, $\frac{K_1+\cdots+K_n}n\to m$ almost surely.
(Note that this uses only the upper bound $\mathbb P(K^n=k^n)\leqslant\mathbb P(Z^n=k^n)\mathrm e^{\epsilon_nn}$ uniformly over $k^n$ in $\mathcal Z^n$, for some $\epsilon_n\to0$.)
Thanks for the very intelligent answer. It's interesting that the lower bound is not used in the proof. For the record, I think in your notation $n^{-1}K^n$ means $\frac{1}{n}\left(K_1+K_2+\cdots+K_n\right)$. – Jim Jan 7 '13 at 23:48