2026-09-02 · 让稀有事件变成典型事件

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

起点问题。 弱大数律告诉我们：若 $X_1,X_2,\dots$ 独立同分布且 $\mu =\mathbb{E}{X}_1$ 存在，则经验均值

$${\bar{X}}_n:=\frac{1}{n}\sum _{i=1}^n{X}_i$$

偏离 $\mu$ 的概率趋于零。但它不回答衰减多快。指数型 Markov 不等式容易给出

$$\mathbb{P}({\bar{X}}_n\ge x)\le \exp \{-nI(x)\},$$

真正困难的是：这个指数是否只是一个方便上界，还是概率的真实对数尺度？今日的答案是 Cramér theorem（Cramér 定理）：在适当指数矩条件下，它确实是真实速率；匹配下界的发动机不是再做一次 Markov 估计，而是 change of measure（变化测度）。

对象与量词分四层：

1. 固定一个实值概率分布 $\nu$，令 $X_i\stackrel{\mathrm{iid}}{\sim }\nu$；
2. 对每个样本规模 $n$，考察 ${\bar{X}}_n$ 的分布；
3. 对每个闭集 $F\subset \mathbb{R}$ 与开集 $G\subset \mathbb{R}$，分别比较概率的上、下指数；
4. 令 $n\to \mathrm{\infty }$，以 $n^{-1}\log \mathbb{P}({\bar{X}}_n\in \cdot )$ 读取速度 $n$ 的衰减率。

完整量词链是

$$\begin{array}{rlrl}& \mathrm{\forall }F\subset \mathbb{R}\text{ closed},& & \underset{n\to \mathrm{\infty }}{lim sup}\frac{1}{n}\log \mathbb{P}({\bar{X}}_n\in F)\le -\underset{x\in F}{inf}I(x),\\ & \mathrm{\forall }G\subset \mathbb{R}\text{ open},& & \underset{n\to \mathrm{\infty }}{lim inf}\frac{1}{n}\log \mathbb{P}({\bar{X}}_n\in G)\ge -\underset{x\in G}{inf}I(x).\end{array}$$

先修：Markov 不等式、独立随机变量、弱大数律、凸函数与导数。主导 proof engines：指数 Markov 给局部上界；有限覆盖与 exponential tightness（指数紧性）把它升级为闭集上界；exponential tilting（指数倾斜）使目标均值在新测度下典型；弱大数律再给匹配下界。去向：Gärtner–Ellis theorem、Sanov theorem、relative entropy（相对熵）、统计物理中的自由能对偶，以及 rare-event importance sampling（稀有事件重要抽样）。

本期是三日 anchor micro-arc 的 Day 1。它诚实深化 2026-08-09：当日已把 Chernoff–Legendre 优化用于随机图割，只需固定候选的指数上界；今日删去候选计数与 union bound，补齐 Cramér 原理的集合表述和变化测度下界。Day 2 将把“调均值所支付的代价”改写成相对熵变分问题。

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

1.1 对数矩母函数与凸对偶

设 $X$ 为实值随机变量。定义 log moment-generating function（对数矩母函数）

$$\mathrm{\Lambda }(\theta ):=\log \mathbb{E}{e}^{\theta X}\in (-\mathrm{\infty },+\mathrm{\infty }],\theta \in \mathbb{R}.$$

今日采用一个清楚而略强的版本：

$$\begin{array}{}\text{(C)}& \mathrm{\exists }\eta >0,\mathbb{E}{e}^{\eta |X|}<\mathrm{\infty }.\end{array}$$

它保证 $\mathrm{\Lambda }(\theta )<\mathrm{\infty }$ 对所有 $|\theta |\le \eta$ 成立，特别地 $\mu =\mathbb{E}X$ 有限。定义 Legendre–Fenchel transform（Legendre–Fenchel 变换）

$$I(x):={\mathrm{\Lambda }}^{\ast }(x)=\underset{\theta \in \mathbb{R}}{sup}\{\theta x-\mathrm{\Lambda }(\theta )\}.$$

逐项检查基本性质：

• $I$ 是仿射函数族 $x\mapsto \theta x-\mathrm{\Lambda }(\theta )$ 的逐点上确界，故凸且下半连续；
• 取 $\theta =0$ 得 $I(x)\ge 0$；
• Jensen 不等式给出 $\mathrm{\Lambda }(\theta )\ge \theta \mu$，故 $I(\mu )=0$；
• 若 $x>\mu$，则负的 $\theta$ 不会改善上确界，所以
  $$I(x)=\underset{\theta \ge 0}{sup}\{\theta x-\mathrm{\Lambda }(\theta )\};$$
  $x<\mu$ 时相应只需 $\theta \le 0$。

当 $\mathrm{\Lambda }$ 在某个 ${\theta }_x$ 可微且

$${\mathrm{\Lambda }}^{\prime }({\theta }_x)=x,$$

凸对偶的切线条件给出

$$I(x)={\theta }_{x}x-\mathrm{\Lambda }({\theta }_x).$$

这不是纯形式优化：${\theta }_x$ 将定义一个均值恰为 $x$ 的新概率分布。

1.2 Cramér 定理

定理（Cramér large-deviation principle，一维版）。 设 $X_1,X_2,\dots$ 为实值 i.i.d. 随机变量，并满足条件 (C)。令 ${\bar{X}}_n=n^{-1}\sum _{i=1}^n{X}_i$，令 $I={\mathrm{\Lambda }}^{\ast }$。则 $\{{\bar{X}}_n\}$ 以速度 $n$ 满足大偏差原理：

• 对每个闭集 $F\subset \mathbb{R}$，
  $$\underset{n\to \mathrm{\infty }}{lim sup}\frac{1}{n}\log \mathbb{P}({\bar{X}}_n\in F)\le -\underset{x\in F}{inf}I(x);$$
• 对每个开集 $G\subset \mathbb{R}$，
  $$\underset{n\to \mathrm{\infty }}{lim inf}\frac{1}{n}\log \mathbb{P}({\bar{X}}_n\in G)\ge -\underset{x\in G}{inf}I(x).$$

约定 $\log 0=-\mathrm{\infty }$、$inf\varnothing =+\mathrm{\infty }$。在一维 Cramér 定理中 $I$ 是 good rate function（好率函数）：每个次水平集 $\{x:I(x)\le c\}$ 都紧。

若 $x>\mu$ 且 $I$ 在 $x$ 附近有限连续，则取 $F=[x,\mathrm{\infty })$ 与 $G=(x,\mathrm{\infty })$ 可得

$$\underset{n\to \mathrm{\infty }}{lim}\frac{1}{n}\log \mathbb{P}({\bar{X}}_n\ge x)=-I(x).$$

这才是“$\mathbb{P}({\bar{X}}_n\ge x)\approx e^{-nI(x)}$”的精确定义：等式只在 $n^{-1}\log$ 尺度上成立，次指数因子未被描述。

1.3 上界：Markov 之后还缺什么

固定 $\theta \ge 0$ 与 $x\in \mathbb{R}$。由独立性，

$$\begin{array}{rl}\mathbb{P}({\bar{X}}_n\ge x)& =\mathbb{P}(e^{\theta n{\bar{X}}_n}\ge e^{\theta nx})\\ & \le e^{-\theta nx}\mathbb{E}{e}^{\theta \sum _{i=1}^n{X}_i}\\ & =\exp \{-n(\theta x-\mathrm{\Lambda }(\theta ))\}.\end{array}$$

对 $\theta \ge 0$ 取上确界便得到上尾 Chernoff bound。下尾类似。这一步只控制半直线；闭集上界还要处理两个问题。

1. 局部化。 对每个 $x\in F$ 与每个 $a<I(x)$，可选某个 ${\theta }_x$ 使
   $${\theta }_{x}x-\mathrm{\Lambda }({\theta }_x)>a.$$
   由连续性，该不等式在 $x$ 的某个邻域仍成立，给出该邻域的指数上界。
2. 从局部到整体。 有界部分 $F\cap [-R,R]$ 是紧集，可由有限多个上述邻域覆盖，有限和不改变主指数。尾部则由条件 (C) 和 Markov 不等式控制：
   $$\mathbb{P}(|{\bar{X}}_n|>R)\le \exp \{-n(\eta R-\mathrm{\Lambda }(\eta ))\}+\exp \{-n(\eta R-\mathrm{\Lambda }(-\eta ))\}.$$
   令 $R\to \mathrm{\infty }$，得到 exponential tightness，封住无界尾部。

因此“优化 Markov”给的是局部代价；闭集上界还依赖紧致覆盖与指数紧性。若忽略后两步，便尚未证明完整 LDP。

1.4 下界：把目标均值变成新世界里的典型值

先处理 regular point（正则点）：固定 $x$，假设存在 ${\theta }_x$ 使 $\mathrm{\Lambda }$ 在该点可微且 ${\mathrm{\Lambda }}^{\prime }({\theta }_x)=x$。定义 tilted law（倾斜分布）${\nu }_{{\theta }_x}$：

$$\frac{d{\nu }_{{\theta }_x}}{d\nu }(y)=\exp \{{\theta }_{x}y-\mathrm{\Lambda }({\theta }_x)\}.$$

归一化成立，因为

$$\int e^{{\theta }_{x}y-\mathrm{\Lambda }({\theta }_x)}\nu (dy)=1.$$

在新分布下，随机变量的均值是

$${\mathbb{E}}_{{\theta }_x}X=\frac{\mathbb{E}[X{e}^{{\theta }_{x}X}]}{\mathbb{E}{e}^{{\theta }_{x}X}}={\mathrm{\Lambda }}^{\prime }({\theta }_x)=x.$$

令 ${\mathbb{P}}_{{\theta }_x}$ 表示 $n$ 个倾斜样本的乘积分布。对任意 $\delta >0$，在事件

$$A_{n,\delta }:=\{|{\bar{X}}_n-x|<\delta \}$$

上，似然比满足

$$\frac{d\mathbb{P}}{d{\mathbb{P}}_{{\theta }_x}}=\exp \{-n{\theta }_x{\bar{X}}_n+n\mathrm{\Lambda }({\theta }_x)\}.$$

若 ${\theta }_x\ge 0$，则 ${\bar{X}}_n<x+\delta$ 给出

$$\begin{array}{rl}\mathbb{P}(A_{n,\delta })& ={\mathbb{E}}_{{\theta }_x}\left[\frac{d\mathbb{P}}{d{\mathbb{P}}_{{\theta }_x}}{\mathbf{1}}_{A_{n,\delta }}\right]\\ & \ge \exp \{-n[{\theta }_x(x+\delta )-\mathrm{\Lambda }({\theta }_x)]\}{\mathbb{P}}_{{\theta }_x}(A_{n,\delta })\\ & =\exp \{-n[I(x)+{\theta }_x\delta ]\}{\mathbb{P}}_{{\theta }_x}(A_{n,\delta }).\end{array}$$

${\theta }_x<0$ 时把误差写成 $|{\theta }_x|\delta$ 即可。关键发生在最后一项：在倾斜分布下，$x$ 已是均值，因此弱大数律给出

$${\mathbb{P}}_{{\theta }_x}(A_{n,\delta })⟶1.$$

所以

$$\underset{n\to \mathrm{\infty }}{lim inf}\frac{1}{n}\log \mathbb{P}(A_{n,\delta })\ge -I(x)-|{\theta }_x|\delta .$$

令 $\delta \downarrow 0$，得到 $-I(x)$ 的匹配下界。一般开集 $G$ 中选取一个 $x\in G$，再取足够小的区间 $(x-\delta ,x+\delta )\subset G$；最后对 $x$ 取优化。非正则边界点由凸性、逼近与下半连续性补齐。

证明的核心可压成

$$\boxed{{\displaystyle \text{原测度下稀有}\stackrel{\text{exponential tilt}}{\to }\text{新测度下典型}\stackrel{\text{likelihood cost}}{\to }I(x).}}$$

上界的 $I(x)$ 来自优化；下界说明同一个优化参数真的制造出该偏差，因而率函数不是估计伪影。

1.5 例：Gaussian 分布的二次代价

若 $X\sim N(\mu ,{\sigma }^2)$ 且 $\sigma >0$，则

$$\mathrm{\Lambda }(\theta )=\mu \theta +\frac{{\sigma }^2{\theta }^2}{2}.$$

因此

$$I(x)=\underset{\theta \in \mathbb{R}}{sup}\{\theta (x-\mu )-\frac{{\sigma }^2{\theta }^2}{2}\}.$$

唯一极大点是

$${\theta }_x=\frac{x-\mu }{{\sigma }^2},$$

故

$$I(x)=\frac{(x-\mu {)}^2}{2{\sigma }^2}.$$

倾斜后的分布仍为 Gaussian，只是均值从 $\mu$ 平移到

$$\mu +{\sigma }^2{\theta }_x=x,$$

方差保持 ${\sigma }^2$。这给出一个完全可见的模型：指数倾斜不是抽象技巧，而是在最小修改分布形状的同时把目标偏差变成中心。

1.6 谱系：从正态尺度之外到现代 LDP

Harald Cramér 1938 年的法文论文 Sur un nouveau théorème-limite de la théorie des probabilités 研究独立同分布随机变量之和在比中央极限定理的 $\sqrt{n}$ 尺度更远处如何衰减。论文明确要求生成函数在零点邻域存在，并使用后来称为 Esscher / Cramér transform 的变化测度。其结果是现代 Cramér 定理的历史起点；现代闭集—开集 LDP 表述则把“尾概率的一个精确渐近”升级为适用于一般集合、可通过连续映射传递的框架。

历史谱系不能压成“旧定理已经过时”：原始问题、指数倾斜和主指数都存续下来；后来变化的是假设的整理、集合语言、凸分析表述及从 i.i.d. 和推广到经验测度、Markov 过程与路径空间的范围。

Graduate / modern extension. Cramér 定理是 contraction principle（伸缩原理）的基本输入：若 ${\bar{X}}_n$ 以率函数 $I$ 满足 LDP，且 $f:\mathbb{R}\to \mathbb{R}$ 连续，则 $f({\bar{X}}_n)$ 的率函数为

$$J(y)=inf\{I(x):f(x)=y\}.$$

这说明大偏差率函数像一种“指数尺度上的能量”，在投影或粗粒化时沿纤维取最小值。Day 2 将把同一结构提升到经验分布，并由 relative entropy 解释这种最小代价。

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

题目

设随机变量 $X$ 满足

$$a\le X\le b\text{a.s.},\mathbb{E}X=0,$$

其中 $a<b$。证明 Hoeffding lemma（Hoeffding 引理）

$$\mathrm{\forall }\lambda \in \mathbb{R},\log \mathbb{E}{e}^{\lambda X}\le \frac{{\lambda }^2(b-a{)}^2}{8}.$$

进而设 $X_1,\dots ,X_n$ 相互独立，$a_i\le X_i\le b_i$ a.s.，证明对每个 $t>0$，

$$\mathbb{P}(\sum _{i=1}^n(X_i-\mathbb{E}{X}_i)\ge t)\le \exp (-\frac{2t^2}{\sum _{i=1}^n(b_i-a_i{)}^2}).$$

模板识别

看到“独立、有界、控制和的尾概率”，应识别 bounded-mgf → exponential Markov → optimize（有界矩母函数—指数 Markov—参数优化） 模板。真正需要证明的不是尾界本身，而是每个中心化变量的 log-mgf 有统一二次包络；独立性随后把这些包络相加。

分级提示

1. 由 $x\mapsto e^{\lambda x}$ 的凸性，对每个 $x\in [a,b]$ 用端点割线控制 $e^{\lambda x}$，把一般 $X$ 约化为一个只取 $a,b$ 的 Bernoulli 型变量。
2. 令 $p=-a/(b-a)$，并把得到的上界写成某个函数 $g(u)$，其中 $u=\lambda (b-a)$；核验 $g(0)=g^{\prime }(0)=0$。
3. 证明 $g^{″}(u)\le 1/4$；这是倾斜 Bernoulli 分布的方差至多 $1/4$。两次积分得到 $g(u)\le u^2/8$。
4. 对中心化的 $X_i$ 应用引理，使用独立性相乘 mgf，再对 $\lambda >0$ 优化一个形如 $-\lambda t+{\lambda }^{2}L/8$ 的二次式，其中 $L=\sum _i(b_i-a_i{)}^2$。

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

人物与语境。 Terence Tao 在其第一人称课程博客 254A, Notes 0: A review of probability theory（2010-01-01）回顾 Markov、Chebyshev、矩方法与概率尾界。下列短引已在原文页面逐字核对。

核验短引（原文）：

“Chebyshev’s inequality gives a simple but still useful large deviation inequality”

中文翻译：

“Chebyshev 不等式给出一个简单但仍然有用的大偏差不等式。”

评论。 Tao 的原文是在搭建概率工具箱，不是陈述 Cramér 定理。短引有价值之处恰在于它把 Chebyshev 放在正确层级：若只知方差，二阶矩法已经能证明偏差概率变小；但对独立有界和，它通常只给多项式上界，无法读取真实的指数衰减率。今日的 log-mgf 与指数倾斜并不否定 Chebyshev，而是提高问题的分辨率：从“偏差罕见”推进到“每单位样本支付多少对数代价”。

这也给出一种方法论上的克制：先问目标需要方差尺度、中心极限尺度，还是远尾指数尺度，再选择工具。Chebyshev、中央极限定理与大偏差原理并非互相替代；它们分别回答粗尾界、中心波动与远尾指数三个不同问题。短引只说明这一工具层级，不能替代 Section 1 的变化测度证明。

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

4.1 有限均值不保证速度 $n$ 的正大偏差指数

令 $X$ 服从 Pareto 分布

$$\mathbb{P}(X>t)=t^{-3},t\ge 1.$$

逐项核验：

1. $X\ge 1$，且
   $$\mathbb{E}X={\int }_0^{\mathrm{\infty }}\mathbb{P}(X>t)dt=1+{\int }_1^{\mathrm{\infty }}{t}^{-3}dt=\frac{3}{2}<\mathrm{\infty }.$$
   因而弱大数律仍适用。
2. 对每个 $\theta >0$，
   $$\mathbb{E}{e}^{\theta X}=\mathrm{\infty },$$
   因为指数增长压过密度的多项式衰减。正向 Cramér condition 失效。
3. 固定 $x>\mu =3/2$。若 $X_1>nx$，则其余变量非负，所以 ${\bar{X}}_n>x$。因此
   $$\mathbb{P}({\bar{X}}_n>x)\ge \mathbb{P}(X_1>nx)=(nx{)}^{-3}.$$
4. 另一方面该概率至多 $1$，故
   $$-\frac{3\log (nx)}{n}\le \frac{1}{n}\log \mathbb{P}({\bar{X}}_n>x)\le 0.$$
   由夹逼，
   $$\underset{n\to \mathrm{\infty }}{lim}\frac{1}{n}\log \mathbb{P}({\bar{X}}_n>x)=0.$$

因此偏差概率确实趋于零，但不是 $e^{-cn}$ 级；在速度 $n$ 上，正率函数退化为零。主导机制是 single big jump（单个大跳），而不是所有样本共同受到指数倾斜。

4.2 这暴露的不是大数律边界，而是 Cramér 机制边界

该例同时满足：

• ${\bar{X}}_n\to \mu$ in probability；
• $\mathbb{P}({\bar{X}}_n>x)\to 0$；
• 但没有正的速度 $n$ 指数。

所以“收敛”与“指数收敛”不可混同。指数矩假设的作用正是排除过重的尾部，使整体偏移比单个巨值更经济；没有它时，Legendre 优化所需的正参数根本不可用。

4.3 为什么定理写闭集上界、开集下界

即使指数矩良好，也不能对每个任意 Borel 集 $A$ 都承诺极限

$$\underset{n\to \mathrm{\infty }}{lim}\frac{1}{n}\log \mathbb{P}({\bar{X}}_n\in A)$$

存在。格点分布和随 $n$ 可达性变化的不规则集合会让概率在零与非零之间振荡。闭集上界允许从外部封闭，开集下界允许在内部放入小邻域；二者正是稳定于极限的拓扑形式。只有当

$$\underset{A^{\circ }}{inf}I=\underset{\bar{A}}{inf}I$$

时，上下界才自动合成一个集合级指数极限。

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

今日一问。 设 $X_1,X_2,\dots$ 为 i.i.d. 标准 Gaussian 随机变量，已知

$${\bar{X}}_n\text{的率函数为}I(x)=\frac{x^2}{2}.$$

令

$$Y_n=({\bar{X}}_n{)}^2.$$

不用直接计算 $Y_n$ 的密度，尝试仅从 Cramér 定理推出 $Y_n$ 的大偏差原理及其率函数 $J:\mathbb{R}\to [0,\mathrm{\infty }]$。你需要回答：

1. 对给定 $y>0$，连续映射 $f(x)=x^2$ 有两个原像，率函数为何应在它们之间取最小？
2. $y=0$ 处应怎样处理？
3. $y<0$ 为什么必须令 $J(y)=+\mathrm{\infty }$？
4. 这个例子怎样展示 contraction principle 中“沿纤维取最小代价”的含义？

方向提示。 先写

$$J(y)=inf\{\frac{x^2}{2}:x^2=y\},$$

但先不要急着化简；逐项处理空原像、单原像与双原像。

数学地图。

$$\begin{array}{c}\text{Markov 不等式、独立和、弱大数律}\\ \downarrow \\ \text{log-mgf }\mathrm{\Lambda }\text{ 与凸对偶 }I={\mathrm{\Lambda }}^{\ast }\\ \swarrow \searrow \\ \text{指数上界与指数紧性}\text{指数倾斜与匹配下界}\\ \downarrow \downarrow \\ \text{Cramér 大偏差原理}\\ \swarrow \searrow \\ \text{contraction principle、Gärtner--Ellis}\text{Sanov、相对熵、重要抽样}\\ \downarrow \\ \text{统计物理自由能、随机图变分问题、稀有事件算法}\end{array}$$

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

展开完整解答

模板：bounded-mgf → exponential Markov → optimize（有界矩母函数—指数 Markov—参数优化）。

先证 Hoeffding 引理。由 $\mathbb{E}X=0$ 且 $a\le X\le b$，必有 $a\le 0\le b$。若 $a=b=0$ 结论平凡；以下设 $a<b$。

对每个 $x\in [a,b]$，凸函数 $u\mapsto e^{\lambda u}$ 位于连接端点值的割线之下：

$$e^{\lambda x}\le \frac{b-x}{b-a}{e}^{\lambda a}+\frac{x-a}{b-a}{e}^{\lambda b}.$$

取期望并用 $\mathbb{E}X=0$，得

$$\mathbb{E}{e}^{\lambda X}\le \frac{b}{b-a}{e}^{\lambda a}+\frac{-a}{b-a}{e}^{\lambda b}.$$

令

$$p:=\frac{-a}{b-a}\in [0,1],\nu :=\lambda (b-a).$$

则 $a=-p(b-a)$、$b=(1-p)(b-a)$，上式右侧等于

$$(1-p)e^{-p\nu }+p{e}^{(1-p)\nu }=e^{-p\nu }(1-p+p{e}^{\nu }).$$

定义

$$g(\nu ):=-p\nu +\log (1-p+p{e}^{\nu }).$$

直接计算 $g(0)=g^{\prime }(0)=0$。再令

$$q_{\nu }:=\frac{p{e}^{\nu }}{1-p+p{e}^{\nu }}\in [0,1].$$

则

$$g^{″}(\nu )=q_{\nu }(1-q_{\nu })\le \frac{1}{4}.$$

对 $\nu \ge 0$，两次积分得

$$g(\nu )={\int }_0^{\nu }(\nu -s)g^{″}(s)ds\le \frac{1}{4}{\int }_0^{\nu }(\nu -s)ds=\frac{{\nu }^2}{8}.$$

对 $\nu <0$，同一 Taylor 积分余项或将积分方向反转，仍得 $g(\nu )\le {\nu }^2/8$。所以

$$\log \mathbb{E}{e}^{\lambda X}\le g(\lambda (b-a))\le \frac{{\lambda }^2(b-a{)}^2}{8}.$$

Hoeffding 引理得证。

现在令

$$Y_i:=X_i-\mathbb{E}{X}_i.$$

平移不改变区间长度，所以 $\mathbb{E}{Y}_i=0$，且 $Y_i$ 落在长度 $b_i-a_i$ 的某个区间内。对任意 $\lambda >0$，由指数 Markov 不等式、独立性与刚证的引理，

$$\begin{array}{rl}\mathbb{P}(\sum _{i=1}^n{Y}_i\ge t)& \le e^{-\lambda t}\mathbb{E}\exp \left(\lambda \sum _{i=1}^n{Y}_i\right)\\ & =e^{-\lambda t}\prod _{i=1}^n\mathbb{E}{e}^{\lambda Y_i}\\ & \le \exp (-\lambda t+\frac{{\lambda }^2}{8}\sum _{i=1}^n(b_i-a_i{)}^2).\end{array}$$

记

$$L:=\sum _{i=1}^n(b_i-a_i{)}^2.$$

若 $L=0$，每个 $X_i$ 都几乎处处为常数，左侧概率为 $0$。若 $L>0$，对二次式

$$-\lambda t+\frac{L{\lambda }^2}{8}$$

求最小值，唯一最优参数为

$${\lambda }_{\ast }=\frac{4t}{L}>0.$$

代入得

$$-{\lambda }_{\ast }t+\frac{L{\lambda }_{\ast }^2}{8}=-\frac{2t^2}{L}.$$

因此

$$\boxed{{\displaystyle \mathbb{P}(\sum _{i=1}^n(X_i-\mathbb{E}{X}_i)\ge t)\le \exp (-\frac{2t^2}{\sum _{i=1}^n(b_i-a_i{)}^2}).}}$$

这套模板的可复用点是：先把单变量 log-mgf 控制成二次函数；独立性把二次预算相加；最后只做一维凸优化。

资料与来源 (Sources)

1. David Gamarnik, “Lecture 2: Large Deviations for i.i.d. Random Variables”, MIT 6.265/15.070J Advanced Stochastic Processes, Fall 2013, dated 2013-09-09. 包含指数 Markov、log-mgf 与 Legendre 变换的推导。
   https://ocw.mit.edu/courses/15-070j-advanced-stochastic-processes-fall-2013/ed35842f2e902421e4a6cdd4d9eca6fe_MIT15_070JF13_Lec2.pdf

2. David Gamarnik, “Lecture 3: Cramér’s Theorem”, MIT 6.265/15.070J Advanced Stochastic Processes, Fall 2013, dated 2013-09-11. 包含闭集上界、开集下界、率函数性质与指数变化测度证明。
   https://ocw.mit.edu/courses/15-070j-advanced-stochastic-processes-fall-2013/f536bc29826255afee543b03b605bf4d_MIT15_070JF13_Lec3.pdf

3. Harald Cramér, “Sur un nouveau théorème-limite de la théorie des probabilités”, Colloque consacré à la théorie des probabilités, Actualités scientifiques et industrielles 736, Hermann, Paris, 1938, pp. 2–23; Hugo Touchette English translation, 2018. 这是历史原始论文的可核验法英对照版本，记录指数矩条件、变化分布与大偏差尺度。
   https://appliedmaths.sun.ac.za/~htouchette/archive/docs/cramer1.pdf

4. Terence Tao, “254A, Notes 0: A review of probability theory”, What’s new, 2010-01-01. 本期 Section 3 的第一人称课程笔记与核验短引来源。
   https://terrytao.wordpress.com/2010/01/01/254a-notes-0-a-review-of-probability-theory/