A converse to Fano's inequality ?

Question

Fano's inequality can be stated in many forms, and one particularly useful one is due (with a minor modification) to Oded Regev:

Let $X$ be a random variable, and let $Y = g(X)$ where $g(\cdot)$ is a random process. Assume the existence of a procedure $f$ that given $y = g(x)$ can reconstruct $x$ with probability $p$. Then $$ I(X; Y) \ge pH(X) − H(p)$$

In other words, if I can reconstruct, there's a lot of mutual information in the system.

Is there a "converse" to Fano's inequality: something of the form

"Given a channel with sufficient mutual information, there is a procedure to reconstruct input from output with error that depends on the mutual information"

It would be too much to expect that this procedure would also be efficient, but it would also be interesting to see (natural) examples where the reconstruction exists but must be inefficient.

Answer 1

Consider the following reconstruction procedure $P(y)$: given $y$, output $x$ such that $\Pr[X = x \mid Y = y]$ is maximized. The probability that this procedure succeeds is $\max_x \Pr[x \mid Y = y]$. This is also $2^{-H_\infty(X | Y = y)}$, where $H_\infty(X \mid Y = y)$ is the min-entropy of the random variable $X$ conditioned on $Y = y$. We know that $H_\infty(X) \leq H_1(X)$, where $H_1(X)$ is the standard Shannon entropy of the random variable $X$. Now we just have to upper bound $H_\infty(X|Y = y)$ in terms of the mutual information $I(X:Y)$.

Write $I(X:Y) = H(X) - H(X|Y) = H(X) - \mathbb{E}_y[H(X \mid Y = y)]$. Using the inequality mentioned above, $I(X:Y) \leq H(X) - \mathbb{E}_y[H_\infty(X \mid Y = y)]$, or $\mathbb{E}_y[H_\infty(X \mid Y = y)] \leq H(X) - I(X:Y)$.

The probability that the procedure succeeds where $X$ and $Y$ are chosen randomly is $\mathbb{E}_y [2^{-H_\infty(X\mid Y = y)}]$, which by concavity is at least $2^{-\mathbb{E}_y[H_\infty(X \mid Y = y)]}$. Thus the probability the procedure succeeds is at least $2^{I(X:Y) - H(X)}$.

This procedure is optimal: given any randomness procedure $P$, the probability of success is $\mathbb{E}_y [ \sum_{x} \Pr(X = x \mid Y = y) \Pr(P(y) = x) ]$, which is maximized point-wise when $P(y)$ deterministically outputs the most likely $x$.

Answer 2

Nice answer and proof. So, the bound in your answer can also be rewritten $$ p_{err} \leq 1-2^{I(X;Y)-H(X)}=1-2^{-H(X|Y)},\quad\quad(1) $$ since $I(X;Y)=H(X)-H(X|Y)$ by definition. This appeared in IEEE ISIT 1994, in a talk by Baumer, to the best of my knowledge.

In a similar vein, one can obtain $$ p_{err} \leq 1 - \sum_{y \in {\cal Y}} P_Y(y) 2^{-H_2(X|Y)},\quad\quad(2) $$ where $$H_{\alpha}(Z)=\frac{1}{1-\alpha}\left( \sum_{z \in {\cal Z}} P_Z(z)^{\alpha}\right)$$ is the Renyi entropy of order $\alpha \in (0,1)\cup(1,\infty).$ Here, $\alpha=2,$ so the bound (2) is tighter than (1).