This question concerns the standard setting for applying Fano's inequality to derive minimax bounds for a parameter estimation problem.

The goal is to estimate a parameter described by a random variable $X$ taking values $x \in \mathcal{X}$, where the set of possible parameters has bounded size, $|\mathcal{X}| = M$. I get observations in the form of a random variable $Y$, and then output an estimator $\hat{X} = f(Y)$ such that $X \rightarrow Y \rightarrow \hat{X}$ is a Markov chain.

One can then use Fano's inequality to show how the best that a classifier can perform is bounded by the mutual information $I(Y:X)$ between the observations and the parameter, e.g. \begin{equation} P(\hat{X} \neq X) \geq 1 - \frac{ I(Y:X) + \log 2}{\log M}. \tag{1} \end{equation} In practice, Eq. (1) is useful for showing that a classifier is guaranteed to fail if the mutual information between observations $Y$ and parameter $X$ is upper bounded like $I(Y:X) \ll \log M$.

My question is, if $I(Y:X)$ can be lower bounded, does this imply the existence of an estimation scheme $f$ (with minimal assumptions) such that $P(\hat{X} \neq X)$ can be upper bounded? Otherwise what is a simple counterexample (again, with minimal assumptions)?

More informally, if Fano's inequality (and the data processing inequality therein) says "garbage in $\Rightarrow$ garbage out", is there some statement like "(not garbage) in $\Rightarrow$ some way to get (not garbage) out"?


1 Answer 1


Yes. For instance, the error of an optimal estimator (i.e. maximum a posteriori estimator) may be upper bounded in terms of $H(X|Y)$. If we let the random variable $\hat{X}$ describing our estimator take values according to \begin{equation} \hat{x}(y) = \arg\max_{x} \text{Pr}(X=x|Y=y), \tag{1} \end{equation} Then an example of such a bound is, \begin{equation} \phi^*(\text{Pr}(\hat{X} \neq X)) \leq H(X|Y), \end{equation} where $\phi^*$ is defined in (Feder, 1994) but is most importantly monotonic. For example, if $\text{Pr}(\hat{X} \neq X) \leq 1/2$ (e.g. in the case of binary random variables) this rearranges to

\begin{equation} \text{Pr}(\hat{X} \neq X) \leq \frac{1}{2}\left(H(X) - I(X:Y)\right), \end{equation} which recovers the expected $\text{Pr}(\hat{X} \neq X)=0$ when $I(Y:X) = H(X)$.

  • $\begingroup$ Did you learn this for a course? Just wondering what kind of stats course you'd learn this in.. really fascinating work. $\endgroup$ Feb 1 at 0:27
  • $\begingroup$ I've been working on a research project related to sufficient conditions for successful estimation and stumbled on the linked paper completely by accident! $\endgroup$
    – forky40
    Feb 1 at 0:52

Your Answer

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

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