跳到主要内容

概率论拾遗：集中不等式

  集中不等式描述一个随机变量是否集中在某个取值附近, 即它是关于 Pr⁡(ε′≤X≤ε′′)\Pr(\varepsilon' \leq X \leq \varepsilon'') 的一类不等式.

1 亚高斯分布​

1.1 Chebyshev-Markov 不等式族​

Markov 不等式 令 XX 是一个非负随机向量, ∀ε>0\forall \varepsilon > 0,

Pr⁡(X≥ε)≤EXε  ⟺  EX≥εPr⁡(X≥ε)\Pr(X \geq \varepsilon) \leq \frac{\mathrm EX}{\varepsilon} \quad \iff \quad \mathrm EX \geq \varepsilon \Pr(X \geq \varepsilon)

从正向看, 它给随机变量的尾部概率给定了一个上界 (即给随机变量集中于 [0,ε)[0, \varepsilon) 区间的概率指定了下界). 从反向看, 它给随机变量的数学期望指定了一个下界, 这个下界与其尾部概率有关. 证明是很直观的, 因为

EX=(Pr⁡(X<ε)⋅EX∣X<ε⏟≥0+Pr⁡(X≥ε)⋅EX∣X≥ε⏟≥ε)≥εPr⁡(X≥ε)\mathrm EX = \Bigg( \underbrace{\Pr(X < \varepsilon) \cdot \mathrm EX \Big|_{X < \varepsilon}}_{\geq 0} + \Pr(X \geq \varepsilon) \cdot \underbrace{\mathrm EX \Big|_{X \geq \varepsilon}}_{\geq \varepsilon} \Bigg) \geq \varepsilon \Pr(X \geq \varepsilon)

Chebyshev 不等式 考虑随机变量 (X−EX)2(X - \mathrm EX)^2 总是非负的. 可以应用 Markov 不等式, ∀ε>0\forall \varepsilon > 0,

Pr⁡(∣X−EX∣≥ε)=Pr⁡((X−EX)2≥ε2)≤E(X−EX)2ε2=Var(X)ε2\Pr(|X - \mathrm EX| \geq \varepsilon) = \Pr((X - \mathrm EX)^2 \geq \varepsilon ^2) \leq \frac{\mathrm E(X - \mathrm EX)^2}{\varepsilon ^2} = \frac{\mathrm{Var}(X)}{\varepsilon ^2}

一般形式 令 XX 是随机变量 (不必要非负), 给定变换函数 g(⋅)≥0g(\cdot) \geq 0 非降, 且 g(ε)>0g(\varepsilon) > 0.

Pr⁡(X≥ε)≤Eg(X)g(ε)  ⟺  Eg(X)≥g(ε)Pr⁡(X≥ε)\Pr(X \geq \varepsilon) \leq \frac{\mathrm Eg(X)}{g(\varepsilon)} \quad \iff \quad \mathrm Eg(X) \geq g(\varepsilon) \Pr(X \geq \varepsilon)

证明方法与 Markov 不等式相同.

Chernoff 界 注意到包含参数 t>0t>0 的函数 g(x;t)=exp⁡txg(x; t) = \exp tx 是正非降的. 令 M(t)M(t) 是随机变量 XX 的矩母函数, 则应用 Markov 不等式的一般形式,

Pr⁡(X≥ε)≤M(t)exp⁡tε,∀t>0\Pr(X \geq \varepsilon) \leq \frac{M(t)}{\exp t\varepsilon}, \qquad \forall t > 0

它的另一个方向是

Pr⁡(X≤ε)≤M(t)exp⁡tε,∀t<0\Pr(X \leq \varepsilon) \leq \frac{M(t)}{\exp t\varepsilon}, \qquad \forall t < 0

不等号右边是关于参数 tt 的函数, 找到其最小值, 可以进一步可以找到最小上界.

注 指数函数是一个下凸函数, 据 Jensen 不等式有 M(t)=Eexp⁡tX≥exp⁡tEXM(t) = \mathrm E \exp tX \geq \exp t \mathrm EX. 所以若 ε≤EX\varepsilon \leq \mathrm EX 时 Chernoff 界大于等于 11 导致其不包含信息.

例 计算中心正态分布 X∼N(0,σ2)X \sim N(0, \sigma^2) 的 Chernoff 界. 我们知道它的矩母函数 M(t)=exp⁡t2σ2/2M(t) = \exp t^2 \sigma^2 /2. 它的 Chernoff 界是

Pr⁡(X≥ε)≤exp⁡t2σ2/2exp⁡tε=exp⁡(t2σ22−tε)\Pr(X \geq \varepsilon) \leq \frac{\exp t^2 \sigma^2 /2}{\exp t\varepsilon} = \exp \left( \frac{t^2 \sigma^2}{2} - t\varepsilon \right)

找到右边二次式的最小值, 取 t=ε/σ2t = \varepsilon / \sigma^2, 得到

Pr⁡(X≥ε)≤exp⁡(−ε22σ2)\Pr(X \geq \varepsilon) \leq \exp \left( -\frac{\varepsilon^2}{2\sigma^2} \right)

例 计算二项分布 X∼B(n,p)X \sim B(n, p) 的 Chernoff 界. 我们知道它的矩母函数

M(t)=(1−p+pet)n=(1+p(et−1))n≤(ep(et−1))n=eμ(et−1)M(t) = (1 - p + pe^t)^n = (1 + p(e^t - 1))^n \leq (e^{p(e^t - 1)})^n = e^{\mu (e^t - 1)}

其中 μ:=np\mu := np. 对 Chernoff 界做换元 δ:=ε/μ−1\delta := \varepsilon / \mu - 1 可以得到

Pr⁡(X≥(1+δ)μ)≤M(t)exp⁡tε≤exp⁡μ(et−1)exp⁡t(1+δ)μ=exp⁡μ(et−1−(1+δ)t)\Pr(X \geq (1 + \delta) \mu) \leq \frac{M(t)}{\exp t\varepsilon} \leq \frac{\exp \mu (e^t - 1)}{\exp t (1 + \delta) \mu} = \exp \mu (e^t - 1 - (1 + \delta)t)

右侧的带参函数 h(t;δ)=et−1−(1+δ)th(t; \delta) = e^t - 1 - (1+\delta) t 在 t=ln⁡(1+δ)t = \ln(1 + \delta) 处有全局最小值. 所以

Pr⁡(X≥(1+δ)μ)≤eδμ(1+δ)(1+δ)μ≤e−δ2μ/3\Pr(X \geq (1 + \delta) \mu) \leq \frac{e^{\delta \mu}}{(1 + \delta)^{(1 + \delta) \mu}} \leq e^{-\delta^2 \mu / 3}

其中最后一步使用了不等式 ln⁡(1+δ)≥2δ/(2+δ)\ln(1+\delta) \geq 2\delta / (2 + \delta), 需要条件 0<δ<10 < \delta < 1. 另一个方向的不等式 Pr⁡(X≥(1−δ)μ)≤e−δ2μ/2\Pr(X \geq (1 - \delta) \mu) \leq e^{-\delta^2 \mu / 2} 是类似的, 但是限定 t<0t < 0.

1.2 Hoeffding 不等式​

亚高斯分布

参考文献​