Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 2 down vote accepted

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

share|cite|improve this answer
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
Quite so. Thanks for spotting this. – Did Jan 7 '13 at 23:51

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.