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?


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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