2026-09-03 · 让整张经验分布偏航

0. 导读与元结构 (Orientation & Meta-structure)

起点问题。 昨日的 Cramér 定理只观察一个标量：

$${\bar{X}}_n=\frac{1}{n}\sum _{j=1}^n{X}_j.$$

但标量均值会遗失大量信息。若样本取值于有限集合 $S=\{1,\dots ,m\}$，更完整的随机对象是 empirical measure（经验测度）

$$L_n:=\frac{1}{n}\sum _{j=1}^n{\delta }_{X_j},L_n(i)=\frac{1}{n}\mathrm{\#}\{j:X_j=i\}.$$

它同时记录每个符号出现的频率。弱大数律说明 $L_n\to p$；今日追问的是：让整张频率表接近另一个分布 $q$，要支付什么指数代价？答案是 relative entropy（相对熵）$D(q\parallel p)$。

对象与量词分四层：

1. 固定有限字母表 $S$ 与真分布 $p=(p_1,\dots ,p_m)$，今日主线先假设 $p_i>0$；
2. 对每个 $n\ge 1$，由 i.i.d. 样本 $X_1,\dots ,X_n\sim p$ 形成随机频率向量 $L_n\in {\mathrm{\Delta }}_m$；
3. 对概率单纯形 ${\mathrm{\Delta }}_m$ 中每个闭集 $F$ 与开集 $G$，考察 $L_n$ 落入其中的概率；
4. 令 $n\to \mathrm{\infty }$，在 $n^{-1}\log$ 尺度读取代价：

$$\begin{array}{rlrl}& \mathrm{\forall }F\subset {\mathrm{\Delta }}_m\text{ closed},& & \underset{n\to \mathrm{\infty }}{lim sup}\frac{1}{n}\log \mathbb{P}(L_n\in F)\le -\underset{q\in F}{inf}D(q\parallel p),\\ & \mathrm{\forall }G\subset {\mathrm{\Delta }}_m\text{ open},& & \underset{n\to \mathrm{\infty }}{lim inf}\frac{1}{n}\log \mathbb{P}(L_n\in G)\ge -\underset{q\in G}{inf}D(q\parallel p).\end{array}$$

先修：多项式系数、独立样本、凸函数、昨日的 LDP 闭集—开集语言。主导 proof engines：把样本序列按 type（类型）分组；以 Shannon entropy（Shannon 熵）估计每个类型类的大小；以 likelihood（似然）计算类内单条序列的概率；最后利用类型总数只有多项式级。去向：信息投影、统计假设检验、Gibbs conditioning principle、Varadhan lemma、统计物理自由能，以及随机图经验轮廓的变分问题。

本期是三日 anchor micro-arc 的 Day 2，也是对 2026-09-02 的明确深化：昨日在实线上以指数倾斜解释一个指定均值的代价；今日把对象提升到分布空间，并证明“均值代价”其实是所有具有该均值的经验分布中最小的相对熵。Day 3 将由 Varadhan 引理把“概率的指数”转成“指数积分的极限”，闭合概率—熵—自由能的对偶链。

1. 核心概念、定理与谱系 (Concept, Theorem & Lineage)

1.1 经验类型、Shannon 熵与相对熵

记

$${\mathrm{\Delta }}_m:=\{q=(q_1,\dots ,q_m)\in [0,1{]}^m:\sum _{i=1}^m{q}_i=1\}.$$

若 $q_i=k_i/n$，其中 $k_i\in \{0,1,\dots ,n\}$ 且 $\sum _i{k}_i=n$，则称 $q$ 是一个 $n$-type。对应的 type class（类型类）为

$$T_n(q):=\{x=(x_1,\dots ,x_n)\in S^n:\frac{1}{n}\mathrm{\#}\{j:x_j=i\}=q_i,\mathrm{\forall }i\in S\}.$$

它的大小是多项式系数

$$|T_n(q)|=\frac{n!}{\prod _{i=1}^m(n{q}_i)!}.$$

定义 Shannon entropy

$$H(q):=-\sum _{i=1}^m{q}_i\log q_i$$

和 Kullback–Leibler divergence（Kullback–Leibler 散度）

$$D(q\parallel p):=\sum _{i=1}^m{q}_i\log \frac{q_i}{p_i}.$$

约定 $0\log (0/p_i)=0$；若某个 $q_i>0$ 而 $p_i=0$，则 $D(q\parallel p)=+\mathrm{\infty }$。今日主线的 $p_i>0$ 假设先排除了后一情形。

由 $\log u\le u-1$，对所有 $q,p\in {\mathrm{\Delta }}_m$ 且 $q\ll p$，

$$\begin{array}{rl}-D(q\parallel p)& =\sum _{i:q_i>0}{q}_i\log \frac{p_i}{q_i}\\ & \le \sum _{i:q_i>0}{q}_i(\frac{p_i}{q_i}-1)\\ & \le \sum _{i=1}^m{p}_i-\sum _{i=1}^m{q}_i=0.\end{array}$$

故 Gibbs inequality（Gibbs 不等式）给出

$$D(q\parallel p)\ge 0,$$

并且在 $p_i>0$ 时等号当且仅当 $q=p$。因此相对熵虽通常不对称、也不是度量，却正定地衡量“把 $p$ 伪装成 $q$”的有向代价。

1.2 类型类为何留下 $D(q\parallel p)$

固定一个 $n$-type $q$。类型类内每条序列 $x\in T_n(q)$ 在乘积分布 $p^{\otimes n}$ 下都有同一概率：

$${\mathbb{P}}_p(X_1=x_1,\dots ,X_n=x_n)=\prod _{i=1}^m{p}_i^{n{q}_i}=\exp \{n\sum _{i=1}^m{q}_i\log p_i\}.$$

因为

$$D(q\parallel p)=-H(q)-\sum _{i=1}^m{q}_i\log p_i,$$

单条序列的概率也可写成

$$\exp \{-n[H(q)+D(q\parallel p)]\}.$$

另一方面，标准类型计数界为

$$(n+1{)}^{-m}{e}^{nH(q)}\le |T_n(q)|\le e^{nH(q)}.$$

两者相乘得到关键夹逼：

$$\begin{array}{}\text{(1)}& \boxed{{\displaystyle (n+1{)}^{-m}{e}^{-nD(q\parallel p)}\le {\mathbb{P}}_p(L_n=q)\le e^{-nD(q\parallel p)}.}}\end{array}$$

这条公式把机制完全拆开了：

• $e^{nH(q)}$ 是实现频率 $q$ 的 combinatorial multiplicity（组合重数）；
• $e^{-n(H(q)+D(q\parallel p))}$ 是每条此类序列的 likelihood cost（似然代价）；
• $H(q)$ 在相乘时相消，净指数恰为 $D(q\parallel p)$。

此外，$n$-type 的数量至多为 $(n+1{)}^m$，因为每个计数 $n{q}_i$ 只有 $n+1$ 个候选值。固定 $m$ 时，这是多项式而非指数增长，故在 $n^{-1}\log$ 尺度上消失。

1.3 有限字母表上的 Sanov 定理

定理（Sanov theorem，有限字母表版）。 设 $S=\{1,\dots ,m\}$，$p\in {\mathrm{\Delta }}_m$ 且 $p_i>0$。令 $X_1,X_2,\dots$ 独立同分布于 $p$，并令

$$L_n=\frac{1}{n}\sum _{j=1}^n{\delta }_{X_j}\in {\mathrm{\Delta }}_m.$$

在 ${\mathrm{\Delta }}_m$ 的欧氏拓扑下，$\{L_n\}$ 以速度 $n$ 满足大偏差原理，good rate function（好率函数）为 $q\mapsto D(q\parallel p)$：对每个闭集 $F\subset {\mathrm{\Delta }}_m$ 与开集 $G\subset {\mathrm{\Delta }}_m$，

$$\begin{array}{}\text{(2)}& \underset{n\to \mathrm{\infty }}{lim sup}\frac{1}{n}\log \mathbb{P}(L_n\in F)\le -\underset{q\in F}{inf}D(q\parallel p),\end{array}$$

$$\begin{array}{}\text{(3)}& \underset{n\to \mathrm{\infty }}{lim inf}\frac{1}{n}\log \mathbb{P}(L_n\in G)\ge -\underset{q\in G}{inf}D(q\parallel p).\end{array}$$

这里 ${\mathrm{\Delta }}_m$ 本身紧，且 $D(\cdot \parallel p)$ 连续，故其所有次水平集自动紧。

证明架构。 对闭集 $F$，把事件按类型分解，并用 (1)：

$$\begin{array}{rl}\mathbb{P}(L_n\in F)& =\sum _{q\in F\cap {\mathcal{P}}_n(S)}\mathbb{P}(L_n=q)\\ & \le (n+1{)}^m\exp \{-n\underset{q\in F}{inf}D(q\parallel p)\},\end{array}$$

其中 ${\mathcal{P}}_n(S)$ 表示所有 $n$-types。取 $n^{-1}\log$ 并令 $n\to \mathrm{\infty }$，多项式前因子消失，得到 (2)。

对开集 $G$，任取 $q\in G$。可选择 $n$-types $q^{(n)}\to q$；由于 $G$ 开，充分大的 $n$ 有 $q^{(n)}\in G$。由 (1) 下界和 $D(\cdot \parallel p)$ 的连续性，

$$\begin{array}{rl}\underset{n\to \mathrm{\infty }}{lim inf}\frac{1}{n}\log \mathbb{P}(L_n\in G)& \ge \underset{n\to \mathrm{\infty }}{lim inf}[-D(q^{(n)}\parallel p)-\frac{m\log (n+1)}{n}]\\ & =-D(q\parallel p).\end{array}$$

再对 $q\in G$ 取下确界，得到 (3)。上界靠“类型不多”，下界靠“保留一个逼近最优点的类型”；二者共同说明最小相对熵控制整个事件。

1.4 Cramér 定理是 Sanov 定理的一个影子

给定任意函数 $f:S\to \mathbb{R}$，样本平均可由经验测度读出：

$$\frac{1}{n}\sum _{j=1}^{n}f(X_j)=\sum _{i=1}^{m}f(i)L_n(i).$$

映射

$${\mathrm{\Phi }}_f:{\mathrm{\Delta }}_m\to \mathbb{R},{\mathrm{\Phi }}_f(q)=\sum _{i=1}^m{q}_{i}f(i)$$

连续。因此 contraction principle（收缩原理）把 Sanov 定理推到均值上，得到率函数

$$\begin{array}{}\text{(4)}& I_f(x)=inf\{D(q\parallel p):q\in {\mathrm{\Delta }}_m,\sum _{i=1}^m{q}_{i}f(i)=x\}.\end{array}$$

它与昨日 Cramér 定理中的 Legendre–Fenchel 形式相同。定义

$$\mathrm{\Lambda }(\theta ):=\log \sum _{i=1}^m{p}_i{e}^{\theta f(i)},$$

以及 tilted distribution（倾斜分布）

$$p_{\theta }(i):=p_i{e}^{\theta f(i)-\mathrm{\Lambda }(\theta )}.$$

若 $q$ 满足 $\sum _i{q}_{i}f(i)=x$，则直接展开得到

$$\begin{array}{}\text{(5)}& D(q\parallel p)=D(q\parallel p_{\theta })+\theta x-\mathrm{\Lambda }(\theta )\ge \theta x-\mathrm{\Lambda }(\theta ).\end{array}$$

故

$$I_f(x)\ge \underset{\theta \in \mathbb{R}}{sup}\{\theta x-\mathrm{\Lambda }(\theta )\}.$$

当 $x$ 位于 $f(S)$ 凸包的相对内部时，可选唯一的适当 $\theta$ 使 ${\mathrm{\Lambda }}^{\prime }(\theta )=x$；此时 $p_{\theta }$ 满足约束，且在 (5) 中令 $q=p_{\theta }$ 便取到等号。边界值由 $\theta \to \pm \mathrm{\infty }$ 的极限补齐。因此

$$\begin{array}{}\text{(6)}& \boxed{{\displaystyle \underset{q:{\mathbb{E}}_{q}f=x}{inf}D(q\parallel p)=\underset{\theta \in \mathbb{R}}{sup}\{\theta x-\mathrm{\Lambda }(\theta )\}.}}\end{array}$$

昨日的指数倾斜与今日的信息投影其实是同一个结构：指定均值 $x$ 后，最便宜的替代分布不是任意 $q$，而是指数族中的 $p_{\theta }$。

1.5 谱系与 modern extension：从有限类型到 Polish 空间

J. M. Swart 的 2023 讲义把有限状态版本称为 Boltzmann–Sanov theorem，并把其早期组合—熵思想追溯到 Boltzmann 1877 年的工作。I. N. Sanov 的论文 On the probability of large deviations of random magnitudes 发表于 1957 年的 Matematicheskii Sbornik 42(84):1, 11–44；现代定理以他的名字命名。这里不把旧形式说成“已被淘汰”：有限类型计数仍然最透明地展示了相对熵为何出现；后来的发展把同一机制放进更一般的拓扑与测度空间。

Graduate / modern extension. 设 $(E,d)$ 是 Polish space，$p\in \mathcal{P}(E)$，且 $X_1,X_2,\dots$ 为 $E$-值 i.i.d. 随机变量，公共分布为 $p$。在概率测度空间 $\mathcal{P}(E)$ 的 weak topology（弱拓扑）下，令

$$L_n=\frac{1}{n}\sum _{j=1}^n{\delta }_{X_j}.$$

现代 Sanov 定理断言：$\{L_n\}$ 以速度 $n$ 满足 LDP，率函数为

$$D(q\parallel p)=\{\begin{array}{ll}{\displaystyle {\int }_E\log \frac{dq}{dp}dq,}& q\ll p,\\ +\mathrm{\infty },& q\ll ̸p.\end{array}$$

等价的变分表达是

$$\begin{array}{}\text{(7)}& D(q\parallel p)=\underset{\phi \in C_b(E)}{sup}\{{\int }_E\phi dq-\log {\int }_E{e}^{\phi }dp\}.\end{array}$$

于是对每个弱闭集 $F\subset \mathcal{P}(E)$ 与弱开集 $G\subset \mathcal{P}(E)$，仍分别有闭集上界与开集下界。Baldasso、Oliveira、Pereira 与 Reis 的现代证明从有限离散化出发：先把 Polish 空间投影到精细有限分割，再证明离散相对熵趋向 (7)，并控制原经验测度与离散经验测度之间的指数等价。这条路线准确保留了今日的有限类型机制，同时说明一般空间新增的困难是拓扑、紧性与离散化误差，而不是另一个神秘的率函数。

2. 固定模板习题 (Template Exercise)

题目

设 $X_1,\dots ,X_n$ 独立同分布，且

$$\mathbb{P}(X_i=1)=p,\mathbb{P}(X_i=0)=1-p,0<p<1.$$

令 $S_n=\sum _{i=1}^n{X}_i$。对任意 $k\in \{0,1,\dots ,n\}$，记 $q=k/n$，并定义 binary relative entropy（二元相对熵）

$$d(q\parallel p):=q\log \frac{q}{p}+(1-q)\log \frac{1-q}{1-p},$$

仍采用 $0\log 0=0$ 的约定。

1. 证明精确类型概率满足
   $$\begin{array}{}\text{(8)}& \frac{1}{n+1}{e}^{-nd(q\parallel p)}\le \mathbb{P}(S_n=k)\le e^{-nd(q\parallel p)}.\end{array}$$
2. 固定 $p<a<1$，仅用 (8) 与类型分解证明
   $$\begin{array}{}\text{(9)}& \underset{n\to \mathrm{\infty }}{lim}\frac{1}{n}\log \mathbb{P}(\frac{S_n}{n}\ge a)=-d(a\parallel p).\end{array}$$

模板识别

看到“有限值 i.i.d. 样本、经验频率、要求精确指数”，应识别 type-class count × per-word likelihood → entropy exponent（类型类计数 × 单词似然 → 熵指数） 模板。关键不是先套 Chernoff，而是把所有具有同一频率的序列合并；组合数提供 $e^{nh(q)}$，类内似然提供 $e^{-n(h(q)+d(q\parallel p))}$。

分级提示

1. 写出 $\mathbb{P}(S_n=k)=(\genfrac{}{}{0ex}{}{n}{k})p^k(1-p{)}^{n-k}$，并把后两项改写为 $e^{-n[h(q)+d(q\parallel p)]}$。
2. 在参数恰为 $q=k/n$ 的二项分布中，证明 $k$ 是一个众数。该分布共有 $n+1$ 个可能取值，因此众数概率至少为 $1/(n+1)$。
3. 由上一步夹逼 $(\genfrac{}{}{0ex}{}{n}{k})$ 与 $e^{nh(q)}$，即可得到 (8)；端点 $k=0,n$ 单独核验。
4. 对上尾令 $q_n=\lceil na\rceil /n$。证明 $q\mapsto d(q\parallel p)$ 在 $[p,1]$ 上递增；下界只保留类型 $q_n$，上界则对至多 $n+1$ 个类型求和。

3. 大家之言 (Mathematician in Their Own Words)

人物与语境。 William P. Thurston 在第一人称论文 On Proof and Progress in Mathematics 中回应“数学进展是否只是生产定理与证明”这一狭窄模型。论文发表于 Bulletin of the American Mathematical Society 30(2), April 1994, 161–177。下列短引已在 AMS 原文逐字核对。

核验短引（原文）：

“The measure of our success is whether what we do enables people to understand and think more clearly and effectively about mathematics.”

中文翻译：

“衡量我们是否成功，要看所做之事能否使人们更清楚、更有效地理解与思考数学。”

评论。 这不是以“理解”取代证明。Thurston 在同一篇文章中反对的是把数学压成单轴的 definition–theorem–proof 产出模型；形式正确仍是底线，但一条证明是否暴露了可迁移的机制，是另一项不可省略的数学价值。

今日可以具体检验这一区分。若只写“经验测度的率函数是 $D(q\parallel p)$”，我们得到一个可引用的定理；类型分解却进一步回答了为什么偏偏是相对熵：类型类提供 $e^{nH(q)}$ 个实现，每个实现支付 $e^{-n(H(q)+D(q\parallel p))}$，两项中的 $H(q)$ 相消。再从 Sanov 收缩到 Cramér，又把“经验分布”“均值”“指数倾斜”三种表征放进同一结构。这个机制不仅帮助记住结论，还告诉我们怎样迁移：换观测量时沿纤维极小化，换到一般空间时保留相对熵并重新处理拓扑与紧性。

因此，Section 1 的量词和上下界负责证明 validity（有效性），类型计数与信息投影负责形成 understanding（理解）。二者非但不冲突，反而互相校验：若一句直觉不能解释假设为何出现、哪个步骤在一般空间失效，它就还没有达到 Thurston 所说的清楚而有效的数学思考。

4. 反例与边界 (Counterexample & Boundary)

4.1 弱收敛看不见逃向无穷远的一阶矩

Polish 空间版 Sanov 定理为何不能不加说明地通过均值映射推出所有实值 Cramér 定理？问题在于弱拓扑只测试 bounded continuous functions（有界连续函数），而 $x\mapsto x$ 无界。

在 $E=\mathbb{R}$ 上定义

$$q_n:=(1-\frac{1}{n}){\delta }_0+\frac{1}{n}{\delta }_n.$$

逐项核验：

1. 每个 $q_n$ 都是概率测度，因为两个权重非负且和为 $1$。
2. 对任意 $\phi \in C_b(\mathbb{R})$，
   $$|\int \phi d{q}_n-\phi (0)|=\frac{1}{n}|\phi (n)-\phi (0)|\le \frac{2\parallel \phi {\parallel }_{\mathrm{\infty }}}{n}⟶0.$$
   因而 $q_n\Rightarrow {\delta }_0$。
3. 但一阶矩满足
   $$\int xd{q}_n(x)=1\text{而}\int xd{\delta }_0(x)=0.$$

所以

$$q⟼\int xdq(x)$$

在弱拓扑下不连续。Sanov 的弱拓扑 LDP 加普通收缩原理，只能直接处理 $q\mapsto \int fdq$ 中有界连续的 $f$；对无界 $f(x)=x$，连续性假设失效。要恢复 Cramér 型结论，需加入指数矩控制并做截断与 exponential approximation（指数逼近），或改用能控制相应矩的更强拓扑，例如合适的 Wasserstein topology。昨日的指数矩条件，正是在这里重新显出其必要角色。

4.2 支撑之外不是“很贵”，而是“不可能”

若真分布 $p$ 满足 $p_i=0$，则样本永远不会出现符号 $i$。任何要求 $q_i>0$ 的经验类型都有

$${\mathbb{P}}_p(L_n=q)=0.$$

相对熵约定

$$q_i>0=p_i⟹D(q\parallel p)=+\mathrm{\infty }$$

并非形式装饰：它使 $e^{-nD(q\parallel p)}=0$，与事件的严格不可能性完全一致。一般空间里的条件 $q\ll p$ 也是同一边界；相对熵只给绝对连续替代分布有限代价。

5. 今日一问与数学地图 (Question & Map)

今日一问。 设 $S=\{1,\dots ,m\}$，$p_i>0$，$f:S\to \mathbb{R}$ 非常数，并取

$$\underset{i}{min}f(i)<a<\underset{i}{max}f(i).$$

考虑约束集

$${\mathcal{C}}_a:=\{q\in {\mathrm{\Delta }}_m:\sum _{i=1}^m{q}_{i}f(i)=a\}.$$

尝试证明：$D(q\parallel p)$ 在 ${\mathcal{C}}_a$ 上有唯一极小点，而且它属于指数族

$$q_{\theta }(i)=\frac{p_i{e}^{\theta f(i)}}{\sum _j{p}_j{e}^{\theta f(j)}}.$$

你需要辨明：

1. 为什么存在唯一的 $\theta =\theta (a)$ 使 $\sum _i{q}_{\theta }(i)f(i)=a$？
2. 为什么对每个 $q\in {\mathcal{C}}_a$ 都有 Pythagorean identity（勾股恒等式）
   $$D(q\parallel p)=D(q\parallel q_{\theta })+D(q_{\theta }\parallel p)?$$
3. 严格凸性在哪一步给出唯一性？
4. 当 $a$ 移到 $minf$ 或 $maxf$ 时，有限的 $\theta$ 为何可能消失，而极小分布仍可由 $\theta \to \pm \mathrm{\infty }$ 得到？

方向提示。 不必从一般 Lagrange multiplier 定理开始。先直接展开 $\log (q_{\theta }(i)/p_i)$；同一均值约束会让交叉项化成常数。再研究

$${\mathrm{\Lambda }}^{\prime }(\theta )={\mathbb{E}}_{q_{\theta }}f,{\mathrm{\Lambda }}^{″}(\theta )={\mathrm{Var}}_{q_{\theta }}(f).$$

但保留边界情形的思考空间：此时方差趋零，最优分布可能集中在极值层上。

数学地图。

$$\begin{array}{c}\text{多项式系数、经验频率、凸性}\\ \downarrow \\ \text{类型类大小 }{e}^{nH(q)}+\text{类内似然 }{e}^{-n(H(q)+D(q\parallel p))}\\ \downarrow \\ \text{单类型代价 }{e}^{-nD(q\parallel p)}\\ \downarrow \\ \text{Sanov：经验测度的 LDP}\\ \swarrow \searrow \\ \text{收缩到均值：Cramér}\text{信息投影与假设检验}\\ \downarrow \downarrow \\ \text{指数族、Gibbs conditioning、最大熵}\\ \searrow \swarrow \\ \text{Varadhan 引理、Laplace 原理与自由能对偶}\\ \downarrow \\ \text{统计力学、随机图经验轮廓、稀有事件条件结构}\end{array}$$

附录 A：习题完整解答 (Full Solution)

展开完整解答

模板：type-class count × per-word likelihood → entropy exponent（类型类计数 × 单词似然 → 熵指数）。

记 binary entropy（二元熵）

$$h(q):=-q\log q-(1-q)\log (1-q).$$

当 $q=k/n$ 时，

$$\begin{array}{}\text{(A1)}& {\mathbb{P}}_p(S_n=k)=(\genfrac{}{}{0ex}{}{n}{k})p^{nq}(1-p{)}^{n(1-q)}.\end{array}$$

由

$$d(q\parallel p)=q\log q+(1-q)\log (1-q)-q\log p-(1-q)\log (1-p),$$

可得

$$\begin{array}{}\text{(A2)}& p^{nq}(1-p{)}^{n(1-q)}=e^{-n[h(q)+d(q\parallel p)]}.\end{array}$$

因此只需证明

$$\begin{array}{}\text{(A3)}& \frac{1}{n+1}{e}^{nh(q)}\le (\genfrac{}{}{0ex}{}{n}{k})\le e^{nh(q)}.\end{array}$$

先设 $0<k<n$。考虑参数为 $q=k/n$ 的二项随机变量 $Y\sim \mathrm{Bin}(n,q)$。对 $0\le j<n$，相邻概率之比为

$$\frac{\mathbb{P}(Y=j+1)}{\mathbb{P}(Y=j)}=\frac{n-j}{j+1}\frac{q}{1-q}.$$

该比值随 $j$ 递减；在 $j=k-1$ 时大于 $1$，在 $j=k$ 时小于 $1$。故 $k$ 是众数。$Y$ 只有 $n+1$ 个可能取值，所有概率之和为 $1$，所以

$$\mathbb{P}(Y=k)=(\genfrac{}{}{0ex}{}{n}{k})q^k(1-q{)}^{n-k}\ge \frac{1}{n+1}.$$

同时任何单点概率至多为 $1$，故

$$\frac{1}{n+1}\le (\genfrac{}{}{0ex}{}{n}{k})q^{nq}(1-q{)}^{n(1-q)}\le 1.$$

而

$$q^{-nq}(1-q{)}^{-n(1-q)}=e^{nh(q)},$$

于是得到 (A3)。当 $k=0$ 或 $k=n$ 时，$(\genfrac{}{}{0ex}{}{n}{k})=1=e^{nh(q)}$，同样满足 (A3)。把 (A2) 与 (A3) 代入 (A1)，便得到

$$\boxed{{\displaystyle \frac{1}{n+1}{e}^{-nd(q\parallel p)}\le {\mathbb{P}}_p(S_n=k)\le e^{-nd(q\parallel p)}.}}$$

现在证明上尾极限。固定 $p<a<1$，令

$$k_n:=\lceil na\rceil ,q_n:=\frac{k_n}{n}.$$

则 $q_n\to a$。先只保留最小可行类型：

$$\begin{array}{}\text{(A4)}& \mathbb{P}(\frac{S_n}{n}\ge a)\ge \mathbb{P}(S_n=k_n)\ge \frac{1}{n+1}{e}^{-nd(q_n\parallel p)}.\end{array}$$

另一方面，对 $q\in (p,1)$，

$$\frac{d}{dq}d(q\parallel p)=\log \frac{q(1-p)}{p(1-q)}>0.$$

故 $d(q\parallel p)$ 在 $[p,1]$ 上递增。上尾包含至多 $n+1$ 个类型，且其中最小散度出现在 $q_n$，所以由 (8) 上界

$$\begin{array}{}\text{(A5)}& \begin{array}{rl}\mathbb{P}(\frac{S_n}{n}\ge a)& =\sum _{k=k_n}^n\mathbb{P}(S_n=k)\\ & \le \sum _{k=k_n}^n\exp \{-nd(\frac{k}{n}\Vert p)\}\\ & \le (n+1)e^{-nd(q_n\parallel p)}.\end{array}\end{array}$$

对 (A4)–(A5) 取 $n^{-1}\log$，得到

$$-d(q_n\parallel p)-\frac{\log (n+1)}{n}\le \frac{1}{n}\log \mathbb{P}(\frac{S_n}{n}\ge a)\le -d(q_n\parallel p)+\frac{\log (n+1)}{n}.$$

由于 $q_n\to a$、$d(\cdot \parallel p)$ 在 $[0,1]$ 上连续，且 $\log (n+1)/n\to 0$，夹逼给出

$$\boxed{{\displaystyle \underset{n\to \mathrm{\infty }}{lim}\frac{1}{n}\log \mathbb{P}(\frac{S_n}{n}\ge a)=-d(a\parallel p).}}$$

这套模板的可复用点是：先精确固定一个经验类型，再证明类型个数只有多项式级；指数尺度上的事件概率最终由可行类型中最小的相对熵决定。

资料与来源 (Sources)

1. Yury Polyanskiy and Yihong Wu, “Chapter 12: Information Projection and Large Deviation”, MIT 6.441 Information Theory, Spring 2016, §§12.1–12.4. 包含相对熵信息投影、指数倾斜、均值约束变分式与 Sanov 定理概述。
   https://ocw.mit.edu/courses/6-441-information-theory-spring-2016/70ca499b4657031ee80dedff6f4a5a22_MIT6_441S16_chapter_12.pdf

2. J. M. Swart, “Large Deviation Theory”, lecture notes, version dated 2023-03-08, especially §§0.3, 2.2 and 5.4. 给出有限状态 Boltzmann–Sanov 定理、相对熵与一般 Sanov 定理的现代课程处理。
   https://staff.utia.cas.cz/swart/lecture_notes/LDP23_03_08.pdf

3. Rangel Baldasso, Roberto I. Oliveira, Alan Pereira and Guilherme Reis, “A Proof of Sanov’s Theorem via Discretizations”, arXiv:2112.04280v2, 2022-04-19. Theorem 1.1 给出 Polish 空间弱拓扑上的 Sanov 定理；正文以有限离散化、相对熵逼近和指数等价完成推广。
   https://arxiv.org/pdf/2112.04280

4. I. N. Sanov, “On the Probability of Large Deviations of Random Magnitudes”, Matematicheskii Sbornik (N.S.) 42(84):1 (1957), 11–44; received 1956-02-24. MathNet 书目页与原文入口。
   https://www.mathnet.ru/eng/sm5043

5. William P. Thurston, “On Proof and Progress in Mathematics”, Bulletin of the American Mathematical Society 30(2), April 1994, 161–177. 本期 Section 3 的第一人称论文与核验短引来源。
   https://www.ams.org/journals/bull/1994-30-02/S0273-0979-1994-00502-6/S0273-0979-1994-00502-6.pdf