Typical sequences and asymptotic equipartition

Let X₁,X₂ and so on be iid on a finite alphabet with fixed law P. Restrict attention to its positive-probability support. The negative logarithm of the block probability is the sum of the individual negative logarithms. These summands have mean H(X) and finite variance, so the weak law of large numbers sends average self-information to H in probability. Fix a positive epsilon before taking the block length to infinity.

Define the entropy-typical set by requiring that this average lie within epsilon of H. Its probability tends to one. Each typical string has probability between two to the minus n times H plus epsilon and two to the minus n times H minus epsilon. This is an exponential-scale comparison, not exact uniformity. Strings with zero source probability are never observed and need not be assigned a finite self-information when forming this argument.

Since each typical string has probability at least two to the minus n times H plus epsilon, their total number cannot exceed two to the n times H plus epsilon. Conversely, if the typical set has probability at least one minus delta and each of its probabilities is at most two to the minus n times H minus epsilon, its cardinality must be at least one minus delta times two to the n times H minus epsilon. Both inequalities follow by summing, with the directions carefully reversed.

The estimates suggest a nearly lossless compression scheme: enumerate the typical strings using roughly nH bits and declare an error on the complement. They do not provide a zero-error code for every supported input. Nor does an entropy alone determine how large n must be before the complement probability is small. A finite-n guarantee requires an explicit concentration bound, exact probability calculation or another quantitative estimate for the chosen source.

For a binary source, an empirical type is the number of ones divided by n. All strings of one type have equal probability, but different nearby types have different multiplicities and probabilities. The typical band usually includes many types. Even when the mean type is exactly representable, the probability of that one type need not tend to one; for a nondegenerate Bernoulli source it decreases on the order of one over the square root of n.

Independence is the mechanism used in this proof. A stationary ergodic finite-alphabet source has a broader equipartition theorem involving its entropy rate, but replacing an arbitrary dependent sequence by an iid model is unjustified. For example, repeatedly copying a single fair bit yields only two possible blocks, regardless of length. Its one-symbol entropy is one bit while its per-symbol block entropy tends to zero. The joint law, rather than the marginal label distribution, controls compressibility.