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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
4
  • $\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
    Commented Oct 13, 2013 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
    Commented Oct 13, 2013 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
    Commented Oct 14, 2013 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
    Commented Oct 14, 2013 at 7:54

You must log in to answer this question.

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