Fano's 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|}$?


  • $\begingroup$ 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? $\endgroup$ Feb 5, 2016 at 23:36
  • $\begingroup$ Not exactly. See the link. $\endgroup$
    – Or Meir
    Feb 7, 2016 at 8:59
  • $\begingroup$ Looking at the proof (e.g., 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)}$ $\endgroup$ Feb 9, 2016 at 17:33


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.