# Does large mutual information (between observations and parameter) imply the existence of a good estimator?

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"?

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