 Type (information theory)

A type 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,\dots ,x_n)$, its empirical distribution is the probability mass functionThe 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.^[ref]