 Expurgation of a codebook

Expurgation discards messages with unusually high conditional decoding error. If a codebook with $2M$ equally likely messages has average error at most $ϵ$, at least $M$ messages have individual error at most $2ϵ$, by Markov's inequality. Retaining those messages and restricting the decoder's candidates gives a codebook with maximal error at most $2ϵ$, provided removal of candidates cannot spoil a previously successful decoding. This is the case for bounded-distance decoding with errors on ambiguity, and for a decoder that retains its former decisions whenever the decoded message remains.

For a sequence of block lengths $n$, halving a book changes its logarithmic rate by $1/n$, which tends to zero. Thus a vanishing average-error bound from a random coding construction can be converted into a vanishing maximal decoding error probability at the same limiting rate. The probabilistic construction first supplies a deterministic book with sufficiently small average error; expurgation is a subsequent deterministic step.