Type (information theory, ${\hat{q}}_{x^n}$)

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]

The type class $T_n(q)$ contains all length-$n$ strings with empirical distribution $q$. Each $nq(a)$ must be a nonnegative integer and the counts must sum to $n$; otherwise the class is empty. Distinct type classes partition ${\mathcal{A}}^n$: every string belongs to exactly one class.

For four binary symbols there are five type classes, indexed by the number $k$ of ones. Their cardinalities are $1,4,6,4,1$, which sum to $16=2^4$. The balanced class contains exactly $0011,0101,0110,1001,1010,1100$. These are six different strings, not six different empirical distributions.

Write $n_a=nq(a)$. Arranging $n_a$ copies of each symbol gives the multinomial coefficientThe division by the factorials removes permutations among identical copies. In the balanced four-symbol example, $|T_4(q)|=4!/(2!2!)=6$. For binary symbols this becomes the binomial coefficient $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$; for three symbols with counts $(2,1,1)$, the class contains $4!/(2!1!1!)=12$ strings.

If a decoder already knows the length, alphabet and empirical distribution, it only needs to distinguish $|T_n(q)|$ possible strings. A fixed-length index therefore needs $\lceil {\log }_2|T_n(q)|\rceil$ bits. List the six balanced four-symbol strings in increasing lexicographic order and number them $0$ through $5$. A three-bit index identifies any one of them, whereas writing the original binary string directly takes four bits.

Knowing the empirical distribution is essential to that calculation. If it must also be sent, a simple fixed-length description of which of the five classes was used costs another $\lceil {\log }_{2}5\rceil =3$ bits. That naive balanced-string message totals six bits and is longer than the raw four-bit string. The example demonstrates the benefit of shared constraints, rather than a free lossless source coding scheme for every input. For long strings over a fixed alphabet, the overhead for identifying a class grows only logarithmically with length, while the information entropy of its frequency profile controls the leading cost within the class.

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)}$.

A possible empirical distribution corresponds to nonnegative integer counts $(n_1,\dots ,n_m)$ with sum $n$. Stars and bars therefore givesThe bound also follows by letting each count independently range from zero to $n$, which overcounts tuples whose sum is wrong. With the alphabet fixed, the count grows polynomially in $n$, whereas there are $m^n$ strings when $m\ge 2$. For binary symbols there are exactly $n+1$ profiles: the number of ones can be any integer from zero through $n$.

This reduces a rare-event calculation to a sum over profiles when the event depends only on counts. An event that depends on order may instead require counting the relevant subset inside each type class. A source with statistical dependence need not make strings of the same empirical distribution equiprobable; the memoryless assumption cannot simply be dropped.

For an attainable empirical distribution $q$ on a fixed finite alphabet of size $m$,Thus $\ln |T_n(q)|$ differs from $n{H}_e(q)$ by at most $m\ln (n+1)$, uniformly over attainable profiles. Information entropy is the leading logarithmic count; the polynomial factor matters at short lengths.^[ref]

The upper bound has a short explanation. Under an independent and identically distributed source whose law is $q$ itself, each string in $T_n(q)$ has probability $e^{-n{H}_e(q)}$. Multiplying by the number of such strings cannot give a probability above one. A corresponding polynomial lower bound follows from the multinomial coefficient; the Stirling's approximation gives sharper prefactors when needed.

For the balanced four-symbol class, $H_e(q)=\ln 2$, so the upper bound is $e^{4\ln 2}=16$, while the exact size is six. Information entropy is not an exact count for a short string. On the leading scale it becomes precise: the difference divided by $n$ tends to zero as $n$ grows with the alphabet fixed.

For a string of empirical distribution $q$, independence givesMultiplying this by the size of a type class gives its exact probability. The entropy bounds for a type class then implyThese bounds apply to one attainable empirical distribution, not automatically to a tail event containing many classes.^[ref] If $p(a)=0$ but $q(a)>0$, every string in that class is impossible and $D_e(q\Vert p)=+\infty$.

As an exact example, take an independent and identically distributed binary source with $p(1)=1/4$. Each balanced four-symbol string has probability $(1/4{)}^2(3/4{)}^2=9/256$. There are six such strings, soThe relative entropy is $D_e((1/2,1/2)\Vert (3/4,1/4))=\frac{1}{2}\ln (4/3)$. The exponential upper bound is $e^{-4D_e}=9/16=0.5625$, visibly larger than the exact probability. It captures the cost of an atypical frequency without supplying the exact finite-length prefactor.

For $n=40$, the exact probability of twenty ones iswhile the exponential upper bound is approximately $0.00317121$. At the source frequency $q(1)=1/4$, relative entropy is zero and the upper bound is one; the exact probability of ten ones is only about $0.144364$. A likely neighborhood of frequencies need not give a large probability to a single exact profile.

The striking cancellation is that there are about $e^{n{H}_e(q)}$ strings in a class, but each costs about $e^{-n[H_e(q)+D_e(q\Vert p)]}$. The information entropy terms cancel, leaving relative entropy as the rarity exponent. Summing over polynomially many classes preserves that leading exponential scale. This is the elementary counting mechanism behind finite-alphabet versions of Sanov theorem and many error exponents in hypothesis testing.

In his 1998 retrospective, Imre Csiszár describes the method of types as a 1970s refinement of the typical set approach, with older counting ingredients. He credits his research group with turning those ingredients into a general tool, while explicitly declining to give a complete discovery history.^[ref] The useful shift is from an approximately typical collection to exact frequency classes: the latter retain enough structure to study how fast error probabilities decay.

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 chooses the probability distribution that satisfies a constraint while departing least from a reference law in relative entropy. The constraint might specify an expected value, several marginal probability distributions, or another convex set of permissible laws. The reference is held fixed: the variable is the first argument of $D(q\Vert p)$. Reversing the arguments gives a different minimization problem.

For a finite alphabet $\mathcal{A}$, take a positive reference probability mass function $p(a)>0$ and a nonempty closed convex set $\mathcal{C}$ in the probability simplex. ThenThe minimum exists and its minimizing probability distribution is unique. In this article, natural logarithms give nats. Using base-two logarithms rescales the objective without changing the minimizer.^[ref]

If $p$ already meets the constraint, its information projection is $p$ itself by relative entropy nonnegativity. If not, a constraint can change the relative weights of outcomes without specifying every weight individually. Relative entropy minimization under a mean constraint gives an especially useful example: it tilts the reference law rather than choosing an arbitrary distribution with the right average.

Let the possible numerical outcomes be $-1,0,1$, and give the reference law $p$ uniform distribution on a finite set: $p=(1/3,1/3,1/3)$. We want a law $q$ with expected value $1/2$. Write the three probabilities in outcome order as $(q_{-},q_0,q_{+})$. The mean constraint is $q_{+}-q_{-}=1/2$, while normalization requires $q_{-}+q_0+q_{+}=1$.

These conditions leave a whole line of possible probability distributions:For example, $(0,1/2,1/2)$ and $(1/4,0,3/4)$ both have the required mean. The constraint alone does not choose between them. Information projection selects the point on this line with the smallest relative entropy from the reference.

Exponential tilting gives weights proportional to $e^{-\theta },1,e^{\theta }$. Set $t=e^{\theta }>0$ and multiply these weights by $t$ to obtain $q^{\ast }=(1,t,t^2)/(1+t+t^2)$. Enforcing the mean givesThe positive root is $t=(1+\sqrt{13})/2$, henceThe most favored outcome becomes $1$, but all three remain possible. This is an exact constructed example with a stipulated reference law and constraint, not a fitted distribution from measurements.

The word "projection" does not mean ordinary perpendicular projection in the plotted Euclidean space. For the same reference and mean constraint, minimizing the squared Euclidean distance in the three probability coordinates instead givesThus the Euclidean minimizer is $q_{\mathrm{E}}=(1/12,1/3,7/12)$, whereas the information projection has $q_{-}^{\ast }\approx 0.116204$. The squared Euclidean objective at its own minimum is $1/8$; its relative entropy is approximately $0.210918$ nats, larger than the optimum $0.197378$ nats. Both distributions satisfy the same constraint.

The reference and objective encode what "least change" means. Relative entropy is asymmetric and is not a metric; its minimization answers a different question from linear least squares. The useful geometric analogy comes from a Pythagorean inequality for information projection, rather than from an assertion that the colored contours are circles.

For a uniform distribution on a finite set of $m$ outcomes, direct expansion of relative entropy giveswhere $H_e$ is information entropy in nats. Therefore minimizing relative entropy from this particular reference is equivalent to maximizing information entropy subject to the same constraint. This statement depends on the uniform reference; an arbitrary reference contributes its own weights.

In the three-outcome example, $H_e(q^{\ast })=\ln 3-D(q^{\ast }\Vert p)\approx 0.901235$ nats. The mean fixes one aggregate quantity, and information projection chooses how to distribute the remaining uncertainty. This extends maximum entropy on a finite alphabet, whose unconstrained maximizer is the uniform law itself.

Under the finite-alphabet, positive-reference, closed-convex set assumptions above, every feasible law $r\in \mathcal{C}$ satisfiesThus a feasible law's excess relative entropy above the optimum is at least its relative entropy from the optimizer. The information projection supplies a quantitative comparison with every other feasible law, not merely the location of a minimum.^[ref]

For affine expected value constraints, the result becomes a Pythagorean identity for relative entropy. In relative entropy minimization under a mean constraint, the logarithm of $q_i^{\ast }/p_i$ is an affine function of the outcome $a_i$. Any feasible $r$ has the same normalization and mean as $q^{\ast }$, making the residual in the three-point identity for relative entropy zero.^[ref]

Let $p_i>0$ be a probability mass function on a finite alphabet with numerical outcomes $a_i$. Prescribe a mean $m$ strictly between the smallest and largest outcomes. Exponential tilting giveswith $\theta$ chosen so that ${\sum }_i{q}_i^{\ast }{a}_i=m$. For any other feasible law $r$, direct substitution yieldsRelative entropy nonnegativity therefore proves optimality and uniqueness. At an extreme prescribed mean, feasible laws may have zero probabilities; a finite tilting parameter need not realize them, although a limit can.

Take independent and identically distributed draws from the uniform three-outcome reference above. An observed sample mean at least $1/2$ is unusual because the source expected value is zero. For two draws, the only successful ordered pairs are $(0,1),(1,0),(1,1)$, giving probability $3/9=1/3$.

For long samples, the relevant empirical distributions have mean at least $1/2$. The method of types assigns a profile $q$ a leading probability cost $e^{-nD(q\Vert p)}$. The least costly admissible profile is the information projection on three outcomes: in this example the minimizing mean is on the boundary $1/2$, and the leading exponent is approximately $0.197378$ nats per draw. The exponential scale is not an exact finite-sample probability formula.^[ref]

The attraction of this connection is that a constrained optimization problem predicts the most probable way an unusual aggregate observation can occur. It links relative entropy, expected value constraints and rare empirical distributions without identifying a rare event with just one exact attainable type class.

In Information Theory and Statistics: A Tutorial by Imre Csiszár and Paul C. Shields (2004, Historical Notes, §3, printed p. 522), the authors connect systematic studies of information projection with earlier relative entropy minimization principles and geometric work, including Imre Csiszár's I-Divergence Geometry of Probability Distributions and Minimization Problems by Imre Csiszár (1975). This is the tutorial's historical account, rather than a claim of one isolated invention. Its finite-alphabet treatment makes the projection identities available without the additional machinery needed for general probability spaces.