# Fano's inequality in the high error regime

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|}$?

Thanks!

• 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? Feb 5, 2016 at 23:36
• Not exactly. See the link. Feb 7, 2016 at 8:59
• 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)}$ Feb 9, 2016 at 17:33