Multinomial Type Large Deviation

Concept

The method of types is a powerful tool in large deviation theory and information theory. For a sequence of length N drawn from a population with distribution p, a "type" is the empirical distribution q = k / N of a specific realization. This module explores the bounds on the exact probability of observing a specific type.

The probability of a specific sequence of length N depends on the true population distribution. However, when we only care about the counts (multiplicity) of symbols, we are looking at the probability of a "type". The exact type probability is given by the product of the type's multiplicity (a multinomial coefficient) and the probability of any sequence with those counts.

The type lemma states that the exact probability of a type is exponentially bounded above and below by the Kullback-Leibler (KL) divergence (or relative entropy) between the empirical distribution q and the true distribution p:

(N + 1)^-3 exp(-N · D(q || p)) ≤ P(type) ≤ exp(-N · D(q || p))

Experiment

In this module, you can explore how the empirical KL divergence relates to the exact type probability. The interactive visualization dynamically computes these bounds as you adjust the inputs.

Select the Population distribution. Choose "Skewed" for a non-uniform prior or "Uniform" for equal probabilities.
Adjust the Sample size to see how the multiplicity of types grows polynomially with N.
Set the First count and Second count to define a specific type. The third count is automatically clamped as the remainder.
Observe the Exact type probability and compare it with the Exponential type upper bound and Polynomial type lower bound in the summary cards.

Interactive Module

Worked Example

Let us manually calculate the bounds for a skewed distribution with a specific sample size.

Assume a Sample size of N = 4, and we select a First count of 4 and Second count of 0. The counts are [4, 0, 0].
The empirical distribution is q = [1.0, 0.0, 0.0]. The true "Skewed" distribution is p = [0.5, 0.25, 0.25].
The empirical KL divergence is D(q || p) = 1.0 * ln(1.0 / 0.5) = ln(2) ≈ 0.693147.
The exponential upper bound is exp(-4 * ln(2)) = exp(-ln(16)) = 1 / 16 = 0.0625.
The polynomial lower bound is (4 + 1)^-3 * 0.0625 = 125^-1 * 0.0625 = 0.008 * 0.0625 = 0.0005.
The type multiplicity is 4! / (4! * 0! * 0!) = 1. The exact probability is 1 * 0.5⁴ = 0.0625.

Limitations

This demonstration assumes a finite alphabet of exactly three symbols and evaluates the probability of a single, specific type rather than the probability of all types in a typical set. The bounds provided by the type lemma are exact for any sample size N, but they are most useful for asymptotic analysis where the polynomial factor becomes negligible compared to the exponential rate.

Limitations and References

For a comprehensive mathematical foundation of the method of types and its applications in large deviation theory, refer to:

Cover, T. M., & Thomas, J. A. (2006). Elements of Information Theory.
Montanari, A. - Information Theory and Large Deviations

Multinomial Type Large Deviation