= Method of types
{wiki}
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>. Define
$$
H_e(q)=-\sum_a q(a)\ln q(a),\qquad
D_e(q\Vert p)=\sum_a q(a)\ln\frac{q(a)}{p(a)}.
$$
Here $p$ is the source <probability mass function> and $q$ is an attainable <empirical distribution>. Use $0\ln0=0$; first assume every $p(a)>0$. Base-two <logarithms> give the equivalent formulas with $2^{nH_2(q)}$ and $2^{-nD_2(q\Vert p)}$.
Back to article page
