I am working on the following exercise:

Let $(X_n)_{n \ge 1}$ be a stochastic process of i.i.d. random variables with values in a finite set $\mathcal{X}$ and distribution $p(x)$. Let $\mu= E(X_1)$. Given $\epsilon > 0$, let

\begin{align} A^{(n)} &:= \biggl\{ (x_1, \ldots, x_n) \in \mathcal{X} : \bigg\lvert -\frac{1}{n} \log_2\bigl((p(x_1,\ldots,x_n) \bigr) - H(X_1) \bigg\rvert \le \epsilon \biggr\} \\ B^{(n)} &:= \biggl\{ (x_1, \ldots, x_n) \in \mathcal{X} : \bigg\lvert -\frac{1}{n} \sum_{i=1}^nx_i-\mu \bigg\rvert \le \epsilon \biggr\} \end{align}

Show that

a) $P \left[\bigl(X_1,\ldots,X_n\bigr) \in A^{(n)}\right] \rightarrow1 \text{ for } n \rightarrow \infty$

b) $P \left[\bigl(X_1,\ldots,X_n\bigr) \in B^{(n)}\right] \rightarrow1 \text{ for } n \rightarrow \infty$

c) $P \left[\bigl(X_1,\ldots,X_n\bigr) \in A^{(n)} \cap B^{(n)}\right] \rightarrow1 \text{ for } n \rightarrow \infty$

I have done $a)$ and $b$). I do not see how I could do c) however. Could you help me?


1 Answer 1


If you have done (a) and (b) then (c) follows very simply.

To save some writing, let $E_n$ be the event that $(X_1, \dots X_n) \in A^{(n)}$ and $F_n$ similarly for $B^{(n)}$. You have shown $P(E_n) \to 1$ and $P(F_n) \to 1$, and you want to show $P(E_n \cap F_n) \to 1$.

Use de Morgan's law to write $P(E_n \cap F_n) = 1 - P(E_n^c \cup F_n^c)$. Then by union bound, $$P(E_n^c \cup F_n^c) \le P(E_n^c) + P(F_n^c) \to 0.$$


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .