Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer 1

up vote 8 down vote accepted

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

share|improve this answer
1  
So, is there a quantitative statement which is a converse of Fano's inequality that follows from this argument? –  mobius dumpling Jun 6 at 20:08
    
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)}$." –  Henry Yuen Jun 6 at 22:09
    
Thanks, that's what I was asking. –  mobius dumpling Jun 7 at 14:09
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.