形式陈述
Chernoff 方法给出指数上界,但它是否已经抓住真实概率的指数阶?Cramér 定理的新增内容,是在合适指数矩条件下补出匹配的下界。
设实随机变量 X 1 , X 2 , … 组成独立同分布样本 理路 独立同分布样本 IID sample · Independent and identically distributed sample 以乘积分布描述来自同一总体的独立重复观测。 ,X ― n = n − 1 ∑ i X i 。令
Λ ( θ ) = log E e θ X 1 , I ( x ) = sup θ ∈ R { θ x − Λ ( θ ) } . 若矩母函数 理路 矩母函数 Moment-generating function · MGF 在存在邻域内以 E[e^{tX}] 编码随机变量各阶矩的函数。 在零的某个开邻域内有限,则 X ― n 在 R 上以速度 n 、良速率函数 I 满足大偏差原理 理路 大偏差原理 Large deviation principle · LDP 用开集下界和闭集上界刻画概率的指数衰减,区分速率函数、拓扑与精确概率。 。这里 I 是 Λ 的凸共轭 理路 凸共轭与 Fenchel–Young 不等式 Convex conjugate · Fenchel conjugate · Fenchel–Young inequality 以线性函数的最佳配对代价定义共轭,并导出原变量与对偶变量间的基本不等式。 ,采用实直线上的通常乘积配对。允许其他参数处 Λ ( θ ) = ∞ ,这些参数不参与有限值优化。所有对数均为自然对数。
直觉
指数上界惩罚异常值;下界则换一个抽样规律,让原来的异常值成为新规律的平均值。然后计算从新规律换回原规律所付出的似然比,便看到这个异常事件确实需要、也只需要大约 n I ( x ) 的指数成本。
若某个内点参数 θ 满足 Λ ′ ( θ ) = x ,定义倾斜分布
d P θ ( y ) = e θ y − Λ ( θ ) d P ( y ) . 在该分布下,零附近的指数矩为 e Λ ( θ + t ) − Λ ( θ ) ,因而一阶绝对矩有限、平均值为 x 。对倾斜后的 IID 样本使用强大数定律 理路 强大数定律 Law of large numbers · Strong law of large numbers · SLLN 独立同分布且可积时,样本均值沿几乎每条无限样本路径收敛到共同期望。 ,得到 P θ ( | X ― n − x | < δ ) → 1 。换回原分布,在该事件上有
P ( | X ― n − x | < δ ) ≥ e − n ( θ x − Λ ( θ ) + | θ | δ ) P θ ( | X ― n − x | < δ ) . 取对数、除以 n ,再让 δ ↓ 0 ,得到可由内点倾斜到达的局部下界。下面补齐一般边界斜率和不能由有限参数直接到达的点;不额外要求矩母函数在整条实轴有限,也不要求其边界陡峭。
证明:上界与一般下界
上界与良速率。 Hölder 不等式 理路 Hölder 不等式 Hölder's inequality 共轭指数下函数乘积的 L¹ 范数由各自的 Lᵖ 范数乘积控制。 说明 Λ 凸,I 作为连续仿射函数的上确界是下半连续凸函数,且由参数零知 I ≥ 0 。取 η > 0 使 Λ ( η ) , Λ ( − η ) < ∞ ,则
I ( x ) ≥ η | x | − max { Λ ( η ) , Λ ( − η ) } , 故其有限子水平集闭且有界,因而紧。Chernoff 方法 理路 Chernoff 方法与 Chernoff 界 Chernoff method · Chernoff bounds 从指数矩与 Markov 不等式推导尾界,给出独立 Bernoulli 和的乘法形式、KL 形式及适用条件。 在参数 ± η 给出样本均值的指数紧性 理路 指数紧性 Exponential tightness 以任意强度的指数尾控制质量逃向无穷,将紧集上界升级为所有闭集上界。 。对任意点 x 和 r < I ( x ) ,可选有限矩参数 θ 使 θ x − Λ ( θ ) > r ;在 x 的足够小邻域 U 上仍有 θ y − Λ ( θ ) > r ,故 P ( X ― n ∈ U ) ≤ e − n r 。对紧集用有限覆盖,再用指数紧性处理紧集外的质量,就得到所有闭集上界。
任意目标点的下界。 固定 x ∈ R ,令 Y = X 1 − x ,并记 L ( θ ) = log E e θ Y 。目标是对每个 δ > 0 证明
lim inf n 1 n log P ( | 1 n ∑ i Y i | < δ ) ≥ inf θ L ( θ ) = − I ( x ) . 先设 P ( Y > 0 ) > 0 且 P ( Y < 0 ) > 0 。对足够大的整数 M ,令
L M ( θ ) = log E [ e θ Y 1 { | Y | ≤ M } ] , p M = P ( | Y | ≤ M ) > 0. 截断分布在正、负两侧均有质量,所以 L M 光滑并在 θ → ± ∞ 时趋于无穷,存在最小点 θ M ,满足 L M ′ ( θ M ) = 0 。先条件于 | Y | ≤ M ,再以 θ M 倾斜,得到均值为零的有界 IID 分布。对它用大数定律和前面的似然比估计:对 0 < ρ < δ ,原分布的概率至少是
p M n exp { n [ L M ( θ M ) − log p M − | θ M | ρ ] } P M , θ M ( | n − 1 ∑ i Y i | < ρ ) . 最后一个概率趋于一;先取 n → ∞ ,再令 ρ ↓ 0 ,便得下界 min L M 。这里 p M n 与条件化归一项恰好抵消,不能漏掉这一项或把不等号反向。
还须证明 min L M ↑ inf L ,不能直接交换极限和下确界。由单调收敛定理 理路 单调收敛定理 Monotone convergence theorem 非负可测函数单调递增时,积分极限等于极限函数积分。 ,L M ↑ L 。记 c M = min L M ,则 c M 单调增加,且 c M ≤ inf L ≤ L ( 0 ) = 0 。固定一个两侧都有质量的 M 0 ,集合 { θ : L M 0 ( θ ) ≤ 0 } 紧;所有 M ≥ M 0 的最小点都在其中。若 c = lim c M ,则非空紧集 { L M ≤ c } 递减,交集中某个 θ ∗ 满足 L ( θ ∗ ) ≤ c 。配合 c ≤ inf L ,即得所需等式。
若 Y ≥ 0 几乎处处,则 inf θ E e θ Y = P ( Y = 0 ) :下界由零点质量给出,而令 θ → − ∞ ,控制收敛定理 理路 控制收敛定理 Dominated convergence theorem 几乎处处收敛且被同一可积函数控制时,可以交换极限与积分。 给出反向逼近。事件“所有 Y i 都为零”提供完全相同的指数下界;若该原子质量为零,所需下界为 − ∞ ,自动成立。Y ≤ 0 的情形对称,Y = 0 几乎处处也包含在内。这覆盖全部支持边界。最后在任意开集内选择目标点及其小球,并对目标点优化,得到完整开集下界。
例子与边界
令 X i ∼ Bernoulli ( p ) ,0 < p < 1 。则 Λ ( θ ) = log ( 1 − p + p e θ ) 。对 0 < q < 1 ,令导数等于 q ,得到
e θ q = q ( 1 − p ) p ( 1 − q ) , I ( q ) = q log q p + ( 1 − q ) log 1 − q 1 − p = D ( q ‖ p ) . 倾斜后的 P θ q 恰为 Bernoulli( q ) 。因此在原来的 Bernoulli( p ) 世界里稀有的“平均值接近 q ”,在新世界里以概率趋于一发生。上面的似然比下界把它带回去,证明相对熵不只是某个方便的上界指数,而是实际的大偏差成本。
在 q = 1 ,事件“所有样本都为一”概率为 p n ,直接给出 I ( 1 ) = − log p ;q = 0 同理得到 − log ( 1 − p ) 。区间外不可能发生,速率为 ∞ 。不能把趋于无穷的倾斜参数当作有限数代回导数式来跳过端点检查。
对 p < q < 1 ,I 在 [ q , 1 ] 上的最小值为 I ( q ) ,而开尾 ( q , 1 ] 可由靠近 q 的点逼近。因此 LDP 的上下界合拢,得到 n − 1 log P ( X ― n ≥ q ) → − D ( q ‖ p ) 。但单点 { q } 可能因 n q 不是整数而概率为零,所以不能照抄尾事件的等式。
若服务时长或损失具有正则变化重尾 理路 正则变化函数 Regularly varying function · Regular variation 正则变化以缩放比值的幂函数极限刻画幂律,允许不改变幂指数的慢变化修正。 ,虽可能有有限方差,却没有零附近的有限正指数矩,本定理的假设不满足。对于固定项数的独立非负和,次指数分布 理路 次指数分布 Subexponential distribution · Principle of a single big jump 次指数重尾的固定有限和超过高门槛时,主要由一个分量单独超过门槛造成,其和尾渐近为单项尾的项数倍。 以卷积尾等价精确表达“一次大跳”机制;要再让项数随门槛增长,需要额外的统一控制。中央极限定理成立并不能替代这里的指数矩条件。
推论与应用
指数倾斜也能用于稀有事件仿真,但必须保留似然比才能无偏地估计原概率。若研究非 IID 序列,可尝试Gärtner–Ellis 定理 理路 Gärtner–Ellis 定理 Gartner-Ellis theorem 从极限对数矩母函数导出大偏差,但以可微性和陡峭性保证匹配下界。 ;仅存在极限对数矩母函数时,匹配下界仍需要额外的光滑性与边界条件。
参考资料