Fano's inequality via an error indicator

ID: fano-s-inequality-via-an-error-indicator

For a guess of a finite-alphabet variable , let and . The chain rule for conditional entropy gives . The first term is at most the binary entropy . The second is zero when the guess is right and at most when it is wrong, proving . This needs no optimality assumption on the guess.

New to topics? Read the docs here!