10
$\begingroup$

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.

$\endgroup$
11
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ So, is there a quantitative statement which is a converse of Fano's inequality that follows from this argument? $\endgroup$ – mobius dumpling Jun 6 '14 at 20:08
  • $\begingroup$ What do you mean by quantitative? The argument I gave above should say, "Given a channel with mutual information $I(X:Y)$, there is a reconstruction procedure with error at most $1 - 2^{I(X:Y) - H(X)}$." $\endgroup$ – Henry Yuen Jun 6 '14 at 22:09
1
$\begingroup$

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

$\endgroup$

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.