Conditional entropy

For discrete random variables, conditional entropy is

For classical finite random variables, $H(X,Z\mid Y)=H(X\mid Y)+H(Z\mid X,Y)=H(Z\mid Y)+H(X\mid Z,Y)$. Each identity follows by inserting the corresponding joint entropy into $H(X,Z,Y)-H(Y)$. The two orders are particularly useful when one variable is a deterministic function of the others, as in Fano's inequality via an error indicator.

If $f(x,z)$ is a bijection of $x$ for every fixed $z$, thenIn particular, translating a random variable in a finite group by a value determined by the conditioning variable does not change its conditional entropy.

For discrete random variables, $H(U\mid V)\le H(U)$, with equality exactly when $U$ and $V$ are independent.

Let $X$ take values in an alphabet of size $m$, let $\hat{X}$ be an estimate determined by $Y$, and put $p_e=\mathbb{P}(\hat{X}\ne X)$. Thenwhere $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$.

For a guess $f(Y)$ of a finite-alphabet variable $X$, let $Z=1_{X\ne f(Y)}$ and $p_e=P(Z=1)$. The chain rule for conditional entropy gives $H(X\mid Y)=H(Z\mid Y)+H(X\mid Z,Y)$. The first term is at most the binary entropy $h(p_e)$. The second is zero when the guess is right and at most ${\log }_2(|J_X|-1)$ when it is wrong, proving $H(X\mid Y)\le h(p_e)+p_e{\log }_2(|J_X|-1)$. This needs no optimality assumption on the guess.

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 $\log 2+(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.

If independent random variables $X,Y$ take values in a finite additive group, thenIndeed, $H(X+Y)\ge H(X+Y\mid Y)=H(X)$, and symmetrically for $Y$. Independence is essential: taking $Y=-X$ makes the sum constant.