Random coding constructs a channel code by sampling its codewords from a specified probability distribution and bounding the expected decoding error over that ensemble. If the expected average error is at most , at least one deterministic codebook has average error at most ; otherwise every book would exceed the expectation bound. This is the probabilistic method applied to communication codes.
For independently uniform binary codewords, a fixed competing word falls in any received word's radius- Hamming ball with probability . The union bound over competing messages, together with a bound on excessive channel noise, yields the basic random-coding error estimate. Expurgation of a codebook can then convert average-error control to maximal decoding error probability with negligible loss of asymptotic rate.
New to topics? Read the docs here!