1
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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}$. $\endgroup$ – Stéphane Laurent Oct 13 '13 at 17:27
  • $\begingroup$ Do you think we could dream about a sufficient asymptotic condition on the laws of the $X_n$ for $(**)$ to hold ? $\endgroup$ – Stéphane Laurent Oct 13 '13 at 21:32
  • $\begingroup$ 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... $\endgroup$ – Anthony Quas Oct 14 '13 at 7:24
  • $\begingroup$ 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$. $\endgroup$ – Stéphane Laurent Oct 14 '13 at 7:54

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.