= Type
{disambiguate=information theory}
{title2=$\widehat q_{x^n}$}
{wiki}
= Empirical distribution
{synonym}
A <type (information theory)> summarizes a string by how often each symbol occurs. Fix a finite <alphabet> $\mathcal A$ of <cardinality> $m$ and a positive length $n$. For a string $x^n=(x_1,\ldots,x_n)$, its <empirical distribution> is the <probability mass function>
$$
\widehat q_{x^n}(a)=\frac{\#\{j:x_j=a\}}{n},\qquad a\in\mathcal A.
$$
The <empirical distribution> forgets order. The strings $0011$ and $1010$ both assign <probability> $1/2$ to each binary symbol; $0001$ assigns $3/4$ to zero and $1/4$ to one. Thus a long string can have a short summary even though that summary does not reconstruct the original order.
For <independent and identically distributed> symbols, this loss of order has a useful consequence: all strings with the same <empirical distribution> have the same <probability>. The <method of types> uses this symmetry to turn questions about exponentially many strings into counting questions about relatively few frequency profiles.<The Method of Types by Imre Csiszár>[§I, printed p. 2505: partition by empirical distribution and equiprobability under a memoryless model]{ref}
Back to article page
