Sanov theorem turns relative entropy into the rate function for empirical measures. The theorem belongs to large deviations, but its geometry is central to information theory.
Empirical-measure deviations
Theorem. Let \(X_1,\ldots,X_n\sim P\) iid on a finite alphabet and let \(\widehat P_n\) be the empirical law. For a set \(\Gamma\) of probability measures, \[ P(\widehat P_n\in\Gamma)\approx \exp\{-n\inf_{Q\in\Gamma}D(Q\|P)\}, \] with the usual interior and closure qualifications for exact lower and upper bounds.
Information projection
Definition. An information projection of \(P\) onto a constraint set \(\Gamma\) is a minimizer \[ Q^\star\in\operatorname*{argmin}_{Q\in\Gamma}D(Q\|P). \] It is the most likely empirical law among those satisfying the constraint.
Proof from types
Proof. Group sequences by type. The number of possible types is polynomial in \(n\), while the probability of a type class is exponential with rate \(-D(Q\|P)\). Polynomial factors vanish on the \(n^{-1}\log\) scale, so the largest admissible type controls the probability.
Conditional limit principle
Remark. Conditioned on the rare event \(\widehat P_n\in\Gamma\), empirical laws concentrate near the information projection when it is unique. This is the finite-alphabet form of maximum entropy under constraints.
Sanov's theorem
Theorem. Let \(X_i\) be iid with law \(P\) on a finite alphabet and let \(\widehat P_n\) be the empirical law. For a set \(\Gamma\) of probability measures, \[ -\inf_{Q\in\Gamma^\circ}D(Q\|P) \le\liminf_{n\to\infty}\frac1n \log P(\widehat P_n\in\Gamma) \] \[ \le\limsup_{n\to\infty}\frac1n \log P(\widehat P_n\in\Gamma) \le-\inf_{Q\in\overline\Gamma}D(Q\|P). \]
Proof. For the upper bound, sum \(P^n(T_Q)\le e^{-nD(Q\|P)}\) over polynomially many types in \(\overline\Gamma\). For the lower bound, choose \(Q\in\Gamma^\circ\) with divergence close to the infimum and approximate \(Q\) by \(n\)-types \(Q_n\in\Gamma^\circ\). The lower type bound gives \[ P(\widehat P_n=Q_n)\ge (n+1)^{-m}e^{-nD(Q_n\|P)}. \] Continuity of KL on the relevant support completes the limit.
Cramér's theorem by contraction
Corollary. For a real function \(f\) on the alphabet, \[ P\left(\frac1n\sum_if(X_i)\in B\right) \] has rate \[ I(z)=\inf_{Q:Qf=z}D(Q\|P). \]
Proof. The sample mean is the continuous map \(Q\mapsto Qf\) applied to the empirical measure. Apply the contraction principle to Sanov's large-deviation principle.
Information projection
Definition. The information projection of \(P\) onto a set \(\mathcal C\) is \[ Q^*\in\arg\min_{Q\in\mathcal C}D(Q\|P). \]
Conditioned on the rare event \(\widehat P_n\in\mathcal C\), empirical distributions concentrate near \(Q^*\) when the minimizer is unique. This is the Gibbs conditioning principle: the least unlikely way to satisfy a constraint dominates.
Exponential-family form under moment constraints
Theorem. Minimize \(D(Q\|P)\) subject to \(Qf_j=c_j\), \(j=1,\ldots,k\), and \(Q1=1\). At an interior optimum, \[ Q_\lambda(x)= P(x)\exp\left\{ \sum_{j=1}^k\lambda_jf_j(x)-A(\lambda)\right\}, \] where \(A(\lambda)\) normalizes the mass and \(\lambda\) is chosen to satisfy the constraints.
Proof. Form the Lagrangian \[ \sum_xq(x)\log\frac{q(x)}{p(x)} -\sum_j\lambda_j\left\{\sum_xq(x)f_j(x)-c_j\right\} -\nu\left\{\sum_xq(x)-1\right\}. \] Stationarity in \(q(x)\) gives \(\log\{q(x)/p(x)\}+1-\sum_j\lambda_jf_j(x)-\nu=0\). Exponentiate and normalize.
Pythagorean inequality
Theorem. If \(\mathcal C\) is convex and \(Q^*\) is the I-projection of \(P\) onto \(\mathcal C\), then for every \(Q\in\mathcal C\), \[ D(Q\|P)\ge D(Q\|Q^*)+D(Q^*\|P). \] Equality holds for affine constraint sets under regularity.
Proof. Consider \(Q_t=(1-t)Q^*+tQ\). Optimality makes the right derivative of \(D(Q_t\|P)\) at zero nonnegative. Computing the derivative yields \[ \sum_x\{Q(x)-Q^*(x)\} \log\frac{Q^*(x)}{P(x)}\ge0. \] Expand \(D(Q\|P)-D(Q\|Q^*)-D(Q^*\|P)\); it equals this inner product.
Maximum entropy as reverse projection
On a finite alphabet with uniform \(U\), \[ D(Q\|U)=\log|\mathcal X|-H(Q). \] Thus maximizing entropy under constraints is equivalent to projecting the uniform law in KL. With a nonuniform reference \(P\), relative-entropy projection is the corresponding minimum-discrimination update.
Rare-event conditional law
Proposition. Suppose \(\mathcal C\) has unique I-projection \(Q^*\). For fixed \(k\), conditioned on \(\widehat P_n\in\mathcal C\), \[ (X_1,\ldots,X_k)\Rightarrow(Q^*)^{\otimes k}. \]
Proof outline. Sanov makes empirical measures outside any neighborhood of \(Q^*\) exponentially less likely than the constraint event. Conditional on an empirical type close to \(Q^*\), sampling finitely many coordinates without replacement converges to iid sampling from that type. Combine concentration of the type with this finite-coordinate approximation.