Skip to content

定理Theorem

Gärtner–Ellis 定理

施工中 · 内容逐步修订

Gartner-Ellis theorem

从极限对数矩母函数导出大偏差,但以可微性和陡峭性保证匹配下界。

形式陈述 ​

若随机量不是 IID 样本均值,但仍能算出极限指数矩,是否还能得到大偏差?Gärtner–Ellis 定理给出一套可核验的充分条件。

设 d≥1、Zn∈Rd,速度 an>0 且 an→∞,对所有 θ∈Rd 极限

Λ(θ)=limn1anlog⁡Eean⟨θ,Zn⟩

存在于 (−∞,∞]。所有对数取自然对数。对每个固定方向 θ,这里使用实随机变量 ⟨θ,Zn⟩ 在参数 an 处的矩母函数,再取对数并归一化;无需来自单个 IID 因子。记 DΛ={Λ<∞}。假设 0∈DΛ∘,Λ 下半连续且本质光滑,即在 DΛ∘ 可微,并在内点趋向任何有限边界点时满足 ‖∇Λ(θ)‖→∞,其中 ∇Λ 是通常欧氏内积下的梯度。

则 Zn 以速度 an 满足LDP,良速率为其凸共轭

I(x)=Λ∗(x)=supθ{⟨θ,x⟩−Λ(θ)}.

若 DΛ=Rd,没有有限边界,陡峭性条件为空,但可微性仍需检查。

直觉

指数上界只需优化一个线性倾斜参数;下界则需要该参数真的能把目标 x 变成新分布的典型值。梯度关系 x=∇Λ(θ) 提供这个接口。不可微点可能隐藏多种竞争机制,有限域边界若不够陡,也可能留下倾斜参数无法到达的取值。

证明:倾斜集中与边界斜率 ​

记 Λn(θ)=an−1log⁡Eean⟨θ,Zn⟩。Hölder 不等式使每个 Λn 凸,取极限后 Λ 也凸,且 Λ(0)=0。取 η>0 使各 ±ηei 位于有效域内;这些参数的极限矩有限,所以 Chernoff 指数矩方法在各坐标给出指数紧性。同样

I(x)≥η‖x‖∞−maxi,±Λ(±ηei),

配合下半连续性说明 I 是良速率。在任一点选择使 ⟨θ,x⟩−Λ(θ) 接近 I(x) 的参数,并在其小邻域使用同一 Chernoff 界,得到局部上界;紧集有限覆盖与指数紧性给出完整闭集上界。

梯度点下界。 取内点 θ,令 x=∇Λ(θ)。充分大的 n 时 Λn(θ) 有限,定义倾斜律

dQnθdPn(z)=exp⁡{an(⟨θ,z⟩−Λn(θ))}.

对每个坐标及足够小的正、负 t,

limnan−1log⁡EQnθeant(Zn,i−xi)=Λ(θ+tei)−Λ(θ)−txi=o(|t|).

因此对任意固定 δ>0,先选小的非零 t,再用正、负方向的 Chernoff 界,得到 Qnθ(|Zn−x|≥δ) 指数趋零。这里用的是极限矩的可微性,没有假设 Zn 是 IID 平均。换回原律,在球内有

lim infnan−1log⁡Pn(|Zn−x|<δ)≥Λ(θ)−⟨θ,x⟩−|θ|δ=−I(x)−|θ|δ.

最后的等式来自凸共轭的梯度等号条件。对任何包含 x 的开集,令其中球半径趋零即得 −I(x);不能在固定半径时提前删掉 |θ|δ。

本质光滑性排除边界次梯度。 使用凸次梯度的定义。若有限值边界点 θ 存在 p∈∂Λ(θ),取内点 θ0,写 u=θ0−θ、θt=θ+tu、qt=∇Λ(θt),其中 0<t<1。两个次梯度不等式相加得 qt⋅u≥p⋅u。选 r>0 使 θ0±rei 全在内域。由 qt 的次梯度不等式,

(1−t)qt⋅u±rqt,i≤Λ(θ0±rei)−Λ(θt).

右侧因 Λ(θt)≥Λ(θ)+tp⋅u 而一致有上界,左侧的径向项也一致有下界。因此每个 qt,i 一致有界,与 t↓0 时的陡峭性矛盾。无限值边界点本来就没有次梯度,故 ∂Λ 只在内域可能非空。

推广到全部有限成本点。 对 x∈ri(domI),有限维闭凸函数在有效域相对内部存在次梯度,选 θ∈∂I(x)。Λ 是正常、闭、凸函数,双共轭等于自身,故共轭次梯度反演给出 x∈∂Λ(θ)。前一步迫使 θ 在内域,于是 x=∇Λ(θ),已有其下界。这里不需要严格凸性,也不要求 domI 满维。

再固定一个 z∈ri(domI)。对任意 I(x)<∞,令 xt=(1−t)x+tz,0<t≤1。把 z 周围有效域仿射包内的小球缩放 t 倍,便知 xt 位于相对内部;凸性与下半连续性给出 I(xt)→I(x)。任意包含 x 的开集最终也包含 xt,所以梯度点下界延伸到每个有限成本点,再取开集内下确界,得到完整 LDP。若删掉本质光滑性,这个延伸步骤不再自动成立。

例子与边界

让独立变量交替服从 Bernoulli(p) 与 Bernoulli(q),其中 p,q∈(0,1),并令 Zn 为前 n 项平均。变量独立但不同分布。以 an=n,指数矩乘积给出

Λ(θ)=12log⁡(1−p+peθ)+12log⁡(1−q+qeθ).

它在整条实轴有限且光滑,所以定理适用。零成本位置是 Λ′(0)=(p+q)/2,端点成本为 I(1)=−12log⁡(pq)。直接计算全为一的概率也得到 p⌈n/2⌉q⌊n/2⌋,其指数与该端点成本吻合。

一个明确反例是对所有 n 都令 Zn 等概率取 −1 或 1。速度 n 下

Λ(θ)=limnn−1log⁡cosh⁡(nθ)=|θ|.

其凸对偶在整个 [−1,1] 上为零,但真实随机量从来不进入 (−1,1):真正速率只有在 ±1 为零,其余为无穷。若机械地取凸对偶,就给不可能的中间取值分配了零成本。失败点是 Λ 在零不可微,而非“矩母函数没算出来”。

矩母函数域也不可随意延伸。例如速率 λ>0 的指数样本的 Λ(θ)=log⁡(λ/(λ−θ)) 只在 θ<λ 有限;接近边界时导数发散,恰好满足陡峭性。把同一代数表达式越过 λ 使用没有概率意义。

推论与应用

有限状态 Markov 加性统计量的极限指数矩常由倾斜转移矩阵的主特征值给出,随后仍需检查相应光滑性。定理的价值在于不要求 IID,边界则在于它输出凸速率;若模型具有真正的非凸速率,单靠对数矩母函数通常只能看见其凸化的信息。

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

拖动节点调整位置。

显示关系

显示:依赖

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