 Method of types

The method of types combines two facts: there are few possible empirical distributions, and strings within each type class are equiprobable under an independent and identically distributed source. Information entropy determines how many strings share a frequency profile; relative entropy determines how unlikely that profile is under a specified source law. The connection is useful both for lossless source coding and for understanding rare observations.

The following formulas use natural logarithms, so information entropy and relative entropy are measured in nats. DefineHere $p$ is the source probability mass function and $q$ is an attainable empirical distribution. Use $0\ln 0=0$; first assume every $p(a)>0$. Base-two logarithms give the equivalent formulas with $2^{n{H}_2(q)}$ and $2^{-n{D}_2(q\Vert p)}$.