# order of convergence of the conditional entropy (2)

Let $X_n$ be a random variable distributed on $A_n:=\{1, \ldots, n\}$ and $g_n\colon A_n \to A_n$ such that $\Pr\big(X_n \neq g_n(X_n)\big) \to 0$. Putting $Y_n=g_n(X_n)$, then by Fano's inequality $$\frac{H(X_n\mid Y_n)}{\log n} \to 0,$$ which can be written $$\frac{H(X_n\mid Y_n)}{H(X_n)} \to 0 \qquad (\ast)$$ in the particular case when $X_n$ is uniformly distributed on $A_n$.

As shown by @AnthonyQuas here, $(\ast)$ fails in general. Now I'd like to know whether $$\limsup \frac{H(X_n\mid Y_n)}{H(X_n)} <1 \qquad (\ast\ast)$$ holds true in general, in the case when $H(X_n)\to \infty$.

I think there's a similar counterexample to the previous one. Let $X_n$ take the value 0 with probability $1-1/n$ and any value in $\{1,\ldots,N_n\}$ with probability $1/(nN_n)$. Set $Y_n=\min(X_n,1)$. Now $H(X_n|Y_n)=(1/n)\log N_n$ (the additional information in $X_n$ comes if $Y_n=1$ which has probability $1/n$; conditioned on $Y_n=1$, the expected additional information is $\log N_n$).
On the other hand, $H(X_n)=-(1-1/n)\log(1-1/n) - N(1/(nN))\log(1/(nN))\approx 1/n(\log n+\log N_n)$. Now if $N_n=2^n$, for example, then the ratio in (**) converges to 1.
• Thank you. The point $H(X_n) \to \infty$ does not hold with your choice of $N_n$ but one can take $N_n=2^{n^2}$. – Stéphane Laurent Oct 13 '13 at 17:27
• Do you think we could dream about a sufficient asymptotic condition on the laws of the $X_n$ for $(**)$ to hold ? – Stéphane Laurent Oct 13 '13 at 21:32
• Notice that $H(X_n|Y_n)=H(X_n,Y_n)-H(Y_n)=H(X_n)-H(Y_n)$, so that condition (**) is asking when $\limsup (H(X_n)-H(Y_n))/H(X_n) < 1$. Equivalently you're asking when is $\liminf H(Y_n)/H(X_n)>0$. I'm not sure what kind of asymptotic conditions you're thinking of, but this really tells you exactly what you need... – Anthony Quas Oct 14 '13 at 7:24
• Actually I'm interested in this example mathoverflow.net/questions/144783/…. Note that I'm expecting that $(**)$ holds for any choice of the $Y_n$. – Stéphane Laurent Oct 14 '13 at 7:54