<p>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.</p>

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

CC BY-SA 4.0
2024-08-13T13:48:56.437Z
I couldn't find anything by Baumer in the proceedings of the 1994 IEEE ISIT. Do you happen to know how to find this talk?
smitke6
CC BY-SA 3.0
2018-03-25T00:13:48.143Z
2018-03-25T00:13:48.143Z
kodlu
<p>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 <i>min-entropy</i> 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)$. </p>

<p>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)$.</p>

<p>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)}$.</p>

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

CC BY-SA 3.0
2014-06-06T20:08:08.590Z
So, is there a quantitative statement which is a converse of Fano's inequality that follows from this argument?
greg
CC BY-SA 3.0
2014-06-06T22:09:00.617Z
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
CC BY-SA 4.0
2024-08-13T13:42:16.263Z
I realize it's been over a decade, but is there any chance anyone can provide a reference for this lower bound on the probability of success? I wish to use and cite it in my work.
smitke6
CC BY-SA 3.0
2014-06-06T14:49:37.303Z
2014-06-06T16:45:29.900Z
2014-06-06T16:45:29.900Z
Henry Yuen
<p><a href="http://en.wikipedia.org/wiki/Fano%27s_inequality">Fano's inequality</a> can be stated in many forms, and one particularly useful one is due (with a minor modification) to <a href="http://arxiv.org/abs/1108.1283">Oded Regev</a>:</p>

<blockquote>
  <p>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)$$</p>
</blockquote>

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

<p>Is there a "converse" to Fano's inequality: something of the form</p>

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

<p>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. </p>

<it.information-theory><randomized-algorithms>
A converse to Fano's inequality ?
Suresh Venkat
# A converse to Fano's inequality ?

(Asked by: username_0 on 2014-06-06)

[Fano's inequality](http://en.wikipedia.org/wiki/Fano%27s_inequality) can be stated in many forms, and one particularly useful one is due (with a minor modification) to [Oded Regev](http://arxiv.org/abs/1108.1283):

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

**Tags:** it.information-theory, randomized-algorithms

---

## 2 answers

### Answer by username_3 on 2014-06-06. Score: 13 | Accepted answer

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

> **Comments:**
> **username_4**: So, is there a quantitative statement which is a converse of Fano's inequality that follows from this argument?  
> **username_3**: 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)}$."  
> **username_2**: I realize it's been over a decade, but is there any chance anyone can provide a reference for this lower bound on the probability of success? I wish to use and cite it in my work.  

---

### Answer by username_1 on 2018-03-25. Score: 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).

> **Comments:**
> **username_2**: I couldn't find anything by Baumer in the proceedings of the 1994 IEEE ISIT. Do you happen to know how to find this talk?  

---

