= List-decoding Fano inequality
{title2=$p_e\geq1-\{I(J;Y)+\log2\}/\log(N/B)$}
If a uniform index $J$ has $N$ possibilities and every proposed success neighbourhood contains at most $B<N$ possibilities, then any estimator has failure <probability> at least the displayed expression. Condition on its success indicator: <conditional entropy> is at most $\log2+(1-p_e)\log B+p_e\log N$. Subtract this from $\log N$ to bound the <mutual information> and rearrange. A metric <Hamming ball> gives approximate recovery rather than exact index decoding.
Back to article page
