<p><a href="http://en.wikipedia.org/wiki/Fano%27s_inequality">Fano's inequality</a> says that given a random variable $X$, and a random variable $Y$ that "guesses" $X$ correctly with some probability, we can lower bound the information that $Y$ gives on $X$. More formally, given two random variables $X,Y$ that take values from some alphabet $\Sigma$ such that $\Pr[X = Y]=p$, we can lower bound the mutual information $I(X:Y)$ in terms of $p$ and $|\Sigma|$. However, this inequality is useful only if $p &gt; 0.5$.</p>

<p>My question is whether there is a similar theorem that allows lower bounding the mutual information $I(X:Y)$ when $p$ is small, but non-trivial, i.e., $p &gt; \frac{1}{|\Sigma|}$.In such a case, $Y$ is still a non-trivial guess of $X$, so it should still give some information on $X$.</p>

<p>To be more concrete, suppose that $X$ is uniform over $\Sigma$, and that $p = \frac{1}{|\Sigma|} + \varepsilon$. Can we say anything about the mutual information $I(X:Y)$? What if $p = \frac{1}{\log|\Sigma|}$?</p>

<p>Thanks!</p>

CC BY-SA 3.0
2016-02-05T23:36:23.160Z
Hi Or, I think Fano's inequality roughly says that $I (X:Y) \geq p \cdot H(X)$ for all $p>0$ Doesn't it?
Igor Shinkar
CC BY-SA 3.0
2016-02-07T08:59:40.297Z
Not exactly. See the link.
Or Meir
CC BY-SA 3.0
2016-02-09T17:33:01.400Z
Looking at the proof (e.g., http://www.cs.cmu.edu/~aarti/Class/10704/lec2-dataprocess.pdf) I think you get the bound above, but this doesn't seem to give anything for $p = \frac{1}{\log(\Sigma)}$
Igor Shinkar
<it.information-theory>
Fano's inequality in the high error regime
Or Meir
# Fano's inequality in the high error regime

(Asked by: username_0 on 2013-05-08)

[Fano's inequality](http://en.wikipedia.org/wiki/Fano%27s_inequality) says that given a random variable $X$, and a random variable $Y$ that "guesses" $X$ correctly with some probability, we can lower bound the information that $Y$ gives on $X$. More formally, given two random variables $X,Y$ that take values from some alphabet $\Sigma$ such that $\Pr[X = Y]=p$, we can lower bound the mutual information $I(X:Y)$ in terms of $p$ and $|\Sigma|$. However, this inequality is useful only if $p > 0.5$.

My question is whether there is a similar theorem that allows lower bounding the mutual information $I(X:Y)$ when $p$ is small, but non-trivial, i.e., $p > \frac{1}{|\Sigma|}$.In such a case, $Y$ is still a non-trivial guess of $X$, so it should still give some information on $X$.

To be more concrete, suppose that $X$ is uniform over $\Sigma$, and that $p = \frac{1}{|\Sigma|} + \varepsilon$. Can we say anything about the mutual information $I(X:Y)$? What if $p = \frac{1}{\log|\Sigma|}$?

Thanks!

**Tags:** it.information-theory

> **Comments:**
> **username_1**: Hi Or, I think Fano's inequality roughly says that $I (X:Y) \geq p \cdot H(X)$ for all $p>0$ Doesn't it?  
> **username_0**: Not exactly. See the link.  
> **username_1**: Looking at the proof (e.g., http://www.cs.cmu.edu/~aarti/Class/10704/lec2-dataprocess.pdf) I think you get the bound above, but this doesn't seem to give anything for $p = \frac{1}{\log(\Sigma)}$  

---

## 0 answers

