Type (information theory)

The type, or empirical distribution, of a finite string records the relative frequency of each symbol.

For a finite alphabet $A$, there are at most $(n+1{)}^{|A|}$ length-$n$ types, and under an i.i.d. law $P$ the probability of the type class $T_R$ is at most $2^{-nD(R\Vert P)}$ when logarithms use base two.

Sanov's theorem is the large deviation principle for empirical distributions of independent identically distributed observations. On a finite alphabet with sampling law $Q$, its rate function is $D_e(R\Vert Q)$.

An information projection of $Q$ onto a set $\mathcal{C}$ of probability distributions minimizes $D(P\Vert Q)$ over $P\in \mathcal{C}$. For a closed convex set and suitable $Q$, it obeys the Pythagorean inequality