Multinomial Type Large Deviation
Compare exact multinomial type mass with its relative-entropy exponential rate.
Free theory articleCompare exact multinomial type mass with its relative-entropy exponential rate.
Concept & interpretation
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.
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.