Skip to content

定理Theorem

Cramér 大偏差定理

施工中 · 内容逐步修订

Cramer theorem for large deviations

以指数倾斜补足 Chernoff 上界,得到 IID 样本均值的完整大偏差速率。

形式陈述 ​

Chernoff 方法给出指数上界,但它是否已经抓住真实概率的指数阶?Cramér 定理的新增内容,是在合适指数矩条件下补出匹配的下界。

设实随机变量 X1,X2,… 组成独立同分布样本,X―n=n−1∑iXi。令

Λ(θ)=log⁡EeθX1,I(x)=supθ∈R{θx−Λ(θ)}.

若矩母函数在零的某个开邻域内有限,则 X―n 在 R 上以速度 n、良速率函数 I 满足大偏差原理。这里 I 是 Λ 的凸共轭,采用实直线上的通常乘积配对。允许其他参数处 Λ(θ)=∞,这些参数不参与有限值优化。所有对数均为自然对数。

直觉

指数上界惩罚异常值;下界则换一个抽样规律,让原来的异常值成为新规律的平均值。然后计算从新规律换回原规律所付出的似然比,便看到这个异常事件确实需要、也只需要大约 nI(x) 的指数成本。

若某个内点参数 θ 满足 Λ′(θ)=x,定义倾斜分布

dPθ(y)=eθy−Λ(θ)dP(y).

在该分布下,零附近的指数矩为 eΛ(θ+t)−Λ(θ),因而一阶绝对矩有限、平均值为 x。对倾斜后的 IID 样本使用强大数定律,得到 Pθ(|X―n−x|<δ)→1。换回原分布,在该事件上有

P(|X―n−x|<δ)≥e−n(θx−Λ(θ)+|θ|δ)Pθ(|X―n−x|<δ).

取对数、除以 n,再让 δ↓0,得到可由内点倾斜到达的局部下界。下面补齐一般边界斜率和不能由有限参数直接到达的点;不额外要求矩母函数在整条实轴有限,也不要求其边界陡峭。

证明:上界与一般下界 ​

上界与良速率。 Hölder 不等式说明 Λ 凸,I 作为连续仿射函数的上确界是下半连续凸函数,且由参数零知 I≥0。取 η>0 使 Λ(η),Λ(−η)<∞,则

I(x)≥η|x|−max{Λ(η),Λ(−η)},

故其有限子水平集闭且有界,因而紧。Chernoff 方法在参数 ±η 给出样本均值的指数紧性。对任意点 x 和 r<I(x),可选有限矩参数 θ 使 θx−Λ(θ)>r;在 x 的足够小邻域 U 上仍有 θy−Λ(θ)>r,故 P(X―n∈U)≤e−nr。对紧集用有限覆盖,再用指数紧性处理紧集外的质量,就得到所有闭集上界。

任意目标点的下界。 固定 x∈R,令 Y=X1−x,并记 L(θ)=log⁡EeθY。目标是对每个 δ>0 证明

lim infn1nlog⁡P(|1n∑iYi|<δ)≥infθL(θ)=−I(x).

先设 P(Y>0)>0 且 P(Y<0)>0。对足够大的整数 M,令

LM(θ)=log⁡E[eθY1{|Y|≤M}],pM=P(|Y|≤M)>0.

截断分布在正、负两侧均有质量,所以 LM 光滑并在 θ→±∞ 时趋于无穷,存在最小点 θM,满足 LM′(θM)=0。先条件于 |Y|≤M,再以 θM 倾斜,得到均值为零的有界 IID 分布。对它用大数定律和前面的似然比估计:对 0<ρ<δ,原分布的概率至少是

pMnexp⁡{n[LM(θM)−log⁡pM−|θM|ρ]}PM,θM(|n−1∑iYi|<ρ).

最后一个概率趋于一;先取 n→∞,再令 ρ↓0,便得下界 minLM。这里 pMn 与条件化归一项恰好抵消,不能漏掉这一项或把不等号反向。

还须证明 minLM↑infL,不能直接交换极限和下确界。由单调收敛定理,LM↑L。记 cM=minLM,则 cM 单调增加,且 cM≤infL≤L(0)=0。固定一个两侧都有质量的 M0,集合 {θ:LM0(θ)≤0} 紧;所有 M≥M0 的最小点都在其中。若 c=limcM,则非空紧集 {LM≤c} 递减,交集中某个 θ∗ 满足 L(θ∗)≤c。配合 c≤infL,即得所需等式。

若 Y≥0 几乎处处,则 infθEeθY=P(Y=0):下界由零点质量给出,而令 θ→−∞,控制收敛定理给出反向逼近。事件“所有 Yi 都为零”提供完全相同的指数下界;若该原子质量为零,所需下界为 −∞,自动成立。Y≤0 的情形对称,Y=0 几乎处处也包含在内。这覆盖全部支持边界。最后在任意开集内选择目标点及其小球,并对目标点优化,得到完整开集下界。

例子与边界

令 Xi∼Bernoulli(p),0<p<1。则 Λ(θ)=log⁡(1−p+peθ)。对 0<q<1,令导数等于 q,得到

eθq=q(1−p)p(1−q),I(q)=qlog⁡qp+(1−q)log⁡1−q1−p=D(q‖p).

倾斜后的 Pθq 恰为 Bernoulli(q)。因此在原来的 Bernoulli(p) 世界里稀有的“平均值接近 q”,在新世界里以概率趋于一发生。上面的似然比下界把它带回去,证明相对熵不只是某个方便的上界指数,而是实际的大偏差成本。

在 q=1,事件“所有样本都为一”概率为 pn,直接给出 I(1)=−log⁡p;q=0 同理得到 −log⁡(1−p)。区间外不可能发生,速率为 ∞。不能把趋于无穷的倾斜参数当作有限数代回导数式来跳过端点检查。

对 p<q<1,I 在 [q,1] 上的最小值为 I(q),而开尾 (q,1] 可由靠近 q 的点逼近。因此 LDP 的上下界合拢,得到 n−1log⁡P(X―n≥q)→−D(q‖p)。但单点 {q} 可能因 nq 不是整数而概率为零,所以不能照抄尾事件的等式。

若服务时长或损失具有正则变化重尾,虽可能有有限方差,却没有零附近的有限正指数矩,本定理的假设不满足。对于固定项数的独立非负和,次指数分布以卷积尾等价精确表达“一次大跳”机制;要再让项数随门槛增长,需要额外的统一控制。中央极限定理成立并不能替代这里的指数矩条件。

推论与应用

指数倾斜也能用于稀有事件仿真,但必须保留似然比才能无偏地估计原概率。若研究非 IID 序列,可尝试Gärtner–Ellis 定理;仅存在极限对数矩母函数时,匹配下界仍需要额外的光滑性与边界条件。

参考资料
关系图谱26 个相邻概念 · 2 类关系

拖动节点调整位置。

显示关系

显示:依赖

  1. 前置三跳
  2. 前置二跳
  3. 前置一跳
  4. 当前条目
  5. 后续一跳
  6. 后续二跳
  7. 后续三跳
文字版关系按与当前条目的最短距离分组
类型化关系