3
$\begingroup$

This question is related to this one. Let $(X_1, X_2, \ldots)$ be a sequence of random variables such that each $X_n$ takes its values in a finite space, say $\{0,1\}$, and the $\sigma$-field $\sigma(X_1, X_2, \ldots)$ is discrete (generated by a denumerable partition of events). The maximal possible entropy of $(X_1, \ldots, X_n)$ is $n \log 2$. Is it possible that $\frac{H(X_1, \ldots, X_n)}{n}$ does not go to zero as $n\to \infty$ ?

$\endgroup$

1 Answer 1

2
+50
$\begingroup$

No, this is impossible. Fix any $\epsilon>0$. Then, since, by assumption, the space is discrete, there is some finite set $\cal A$ of sequences $(X_1,X_2,\dots)$ such that ${\Bbb P}((X_i)\in {\cal A})>1-\epsilon$. Let $A$ be the event $(X_i)\in{\cal A}$. Then \begin{eqnarray*} H(X_1,\dots,X_n)&\le& H(X_1,\dots,X_n,A)\\ &=& H(A)+H(X_1,\ldots,X_n\mid A){\Bbb P}(A)+H(X_1,\ldots,X_n\mid A^C)(1-{\Bbb P}(A))\\ &\le& H(A)+H((X_i)\mid A)+n\epsilon\log 2. \end{eqnarray*} Since $\cal A$ is finite, $H((X_i)\mid A)$ is finite, so $$ \limsup_n \frac{H(X_1,\ldots,X_n)}{n}\le \epsilon \log 2, $$ and letting $\epsilon\to 0$, $$ \lim_n \frac{H(X_1,\ldots,X_n)}{n}=0. $$

$\endgroup$
3
  • $\begingroup$ Great. I need to learn these basic formulas about conditional entropy but I believe you. $\endgroup$ Jan 27, 2013 at 7:15
  • $\begingroup$ I'm trying to understand your solution David, using the wikipedia page about conditional entropy. You denote by $H(A)$ the entropy of the indicator function of $A$, don't you ? $\endgroup$ Jan 29, 2013 at 21:44
  • $\begingroup$ Yes, that's right. Similarly, $H(X_1,\ldots,X_n,A)$ is the joint entropy of the $X_i$s and the indicator function of $A$. $\endgroup$ Jan 29, 2013 at 22:28

You must log in to answer this question.

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