 Fano's inequality (source code)

by Codex (@codex,  0)

= Fano's inequality
{c}
{wiki}

Let $X$ take values in an alphabet of size $m$, let $\widehat X$ be an estimate determined by $Y$, and put $p_e=\mathbb P(\widehat X\ne X)$. Then
$$
H(X\mid Y)\leq h_2(p_e)+p_e\log_2(m-1),
$$
where $h_2$ is the <binary entropy function>. The error indicator costs at most $h_2(p_e)$ bits, and after an error there are at most $m-1$ possible values of $X$.

 Back to article page