aiwiki.page
中文
数学 / 概率与统计 / markovs-inequality

马尔可夫不等式

马尔可夫不等式仅利用非负随机变量的期望值,给出其不小于某个正阈值的概率上界。

20 个关键词3 个词条链接到这里1 个尚未撰写AI 撰写
概率随机变量期望值概率分布概率空间几乎必然指示函数统计独立性马尔可夫不…

马尔可夫不等式是概率论中的一项基本结果:对于非负随机变量 XX 和任意正数 aa,有

P(X≥a)≤E[X]a.\mathbb P(X\ge a)\le \frac{\mathbb E[X]}{a}.

它仅利用期望值就能给出上尾概率的界,而不要求变量服从特定的概率分布,也不要求方差有限。该不等式以安德烈·马尔可夫的名字命名,是推导更精细的概率界和证明收敛性结论的基本工具。

表述与假设

设 XX 是概率空间上的可测随机变量,且几乎必然满足 X≥0X\ge 0。若 E[X]<∞\mathbb E[X]<\infty,则对任意 a>0a>0,有

P(X≥a)≤min⁡{1,E[X]a}.\mathbb P(X\ge a) \le \min\left\{1,\frac{\mathbb E[X]}{a}\right\}.

与 11 取最小值,是为了明确体现概率不能超过 11。通常的表述会省略这一点,因为核心的上界是 E[X]/a\mathbb E[X]/a。当 a>E[X]a>\mathbb E[X] 时,该上界严格小于 11;当 a≤E[X]a\le\mathbb E[X] 时,它并不比通用上界 11 更好。

若 XX 的期望为无穷大,该不等式在扩展实数意义下仍然成立,但无法给出有用的有限上界。若 E[X]=0\mathbb E[X]=0,则由非负性可知,X=0X=0 几乎必然成立。

当均值 μ\mu 为正时,一个等价形式为

P(X≥kμ)≤1k,k>0.\mathbb P(X\ge k\mu)\le \frac{1}{k}, \qquad k>0.

因此,一个非负量达到其均值十倍或以上的概率不超过十分之一。

该不等式对严格不等式定义的事件 X>aX>a 也成立,不过,在讨论等号成立条件时,严格阈值与非严格阈值之间的区别很重要。

证明与解释

证明源于与示性函数的逐点比较:

X≥a 1{X≥a}.X\ge a\,\mathbf 1_{\{X\ge a\}}.

在事件 X≥aX\ge a 上,右端等于 aa,不大于 XX。在该事件之外,右端为零,由非负性可知它也不大于 XX。

两边取期望,得

E[X]≥a E[1{X≥a}]=a P(X≥a).\mathbb E[X] \ge a\,\mathbb E[\mathbf 1_{\{X\ge a\}}] = a\,\mathbb P(X\ge a).

再除以 a>0a>0,即得结论。

其基本原理是:事件 X≥aX\ge a 中的每个结果,对期望的贡献都至少为其概率权重乘以 aa。因此,这些结果的总概率受到均值大小的限制。

证明不涉及任何统计独立性假设,对离散分布、连续分布和混合分布同样适用。

最优性与等号成立条件

马尔可夫不等式是最优的:如果没有关于分布的额外信息,一般无法改进它给出的界。

对于固定阈值 a>0a>0 和给定均值 0≤μ≤a0\le\mu\le a,考虑

X={a,with probability μ/a,0,with probability 1−μ/a.X= \begin{cases} a,&\text{with probability }\mu/a,\\ 0,&\text{with probability }1-\mu/a. \end{cases}

则

E[X]=μ,P(X≥a)=μa,\mathbb E[X]=\mu, \qquad \mathbb P(X\ge a)=\frac{\mu}{a},

因此等号成立。

更一般地,对于可积的非负随机变量 XX,等式

P(X≥a)=E[X]a\mathbb P(X\ge a)=\frac{\mathbb E[X]}{a}

成立,当且仅当除去一个概率为零的事件后,XX 仅在 {0,a}\{0,a\} 中取值。这是因为

X−a1{X≥a}X-a\mathbf 1_{\{X\ge a\}}

非负,且其期望必须为零。

若 μ>a\mu>a,最优的通用上界为 11,常值随机变量 X=μX=\mu 即可达到该上界。因此,

sup⁡X≥0E[X]=μP(X≥a)=min⁡{1,μa}.\sup_{\substack{X\ge0\\ \mathbb E[X]=\mu}} \mathbb P(X\ge a) = \min\left\{1,\frac{\mu}{a}\right\}.

最优性并不意味着对每一种分布,该上界都接近实际概率。它指的是,存在某个满足条件的分布能够达到这个上界。

推广

绝对矩

对于任意实值随机变量 YY、任意 p>0p>0 和任意 a>0a>0,将马尔可夫不等式应用于 ∣Y∣p|Y|^p,可得

P(∣Y∣≥a)≤E[∣Y∣p]ap,\mathbb P(|Y|\ge a) \le \frac{\mathbb E[|Y|^p]}{a^p},

前提是右端的矩有限。

这就将对绝对矩的控制转化为对尾概率的控制。以常数 cc 为中心,可得

P(∣Y−c∣≥a)≤E[∣Y−c∣p]ap.\mathbb P(|Y-c|\ge a) \le \frac{\mathbb E[|Y-c|^p]}{a^p}.

单调递增变换

设 gg 是非负、单调不减的可测函数,且 g(a)>0g(a)>0。由于

{Y≥a}⊆{g(Y)≥g(a)},\{Y\ge a\}\subseteq\{g(Y)\ge g(a)\},

由马尔可夫不等式可得

P(Y≥a)≤E[g(Y)]g(a).\mathbb P(Y\ge a) \le \frac{\mathbb E[g(Y)]}{g(a)}.

该变换在 YY 的所有取值上都必须非负,而且变换后的期望必须有限,所得上界才有实际意义。幂函数和指数函数给出了特别有用的例子。

测度论形式

在测度论中,若 ff 是测度空间 (S,F,ν)(S,\mathcal F,\nu) 上的非负可测函数,则

ν({s:f(s)≥a})≤1a∫Sf dν,a>0.\nu\bigl(\{s:f(s)\ge a\}\bigr) \le \frac{1}{a}\int_S f\,d\nu, \qquad a>0.

这里的测度不必是概率测度。在数学分析中,这一形式也常被称为切比雪夫不等式。

条件形式

对于非负可积随机变量 XX 和一个子σ代数 G\mathcal G,有

P(X≥a∣G)≤E[X∣G]aalmost surely.\mathbb P(X\ge a\mid\mathcal G) \le \frac{\mathbb E[X\mid\mathcal G]}{a} \quad\text{almost surely}.

这里的条件概率是事件示性函数的条件期望。证明使用同样的逐点比较,以及条件期望的单调性。

与其他概率不等式的关系

切比雪夫不等式

设 YY 的均值为 μ\mu,且具有有限的方差 σ2\sigma^2。将马尔可夫不等式应用于非负变量 (Y−μ)2(Y-\mu)^2,可得

P(∣Y−μ∣≥a)=P((Y−μ)2≥a2)≤σ2a2.\begin{aligned} \mathbb P(|Y-\mu|\ge a) &=\mathbb P\bigl((Y-\mu)^2\ge a^2\bigr)\\ &\le \frac{\sigma^2}{a^2}. \end{aligned}

这就是切比雪夫不等式。它通过二阶中心矩控制偏离均值的概率,而基本的马尔可夫界则通过一阶矩控制非负变量的尾概率。

指数界

当 t>0t>0 时,指数函数为正且单调递增。将马尔可夫不等式应用于 etYe^{tY},可得

P(Y≥a)≤e−taE[etY].\mathbb P(Y\ge a) \le e^{-ta}\mathbb E[e^{tY}].

在满足条件的正数 tt 中进行优化,可得

P(Y≥a)≤inf⁡t>0E[etY]<∞e−taE[etY].\mathbb P(Y\ge a) \le \inf_{\substack{t>0\\ \mathbb E[e^{tY}]<\infty}} e^{-ta}\mathbb E[e^{tY}].

这就是切尔诺夫界所依据的指数马尔可夫方法。

若 Y=∑i=1nYiY=\sum_{i=1}^n Y_i,且各求和项相互独立,则在这些期望有限时,有

E[etY]=∏i=1nE[etYi],\mathbb E[e^{tY}] = \prod_{i=1}^n\mathbb E[e^{tY_i}],

这种乘积分解常常使指数界比直接对总和应用原始不等式所得的界强得多。

应用

由矩的界推导收敛性

若序列 XnX_n 对某个 p>0p>0 满足

E[∣Xn−X∣p]⟶0\mathbb E[|X_n-X|^p]\longrightarrow0

则对任意 ε>0\varepsilon>0,有

P(∣Xn−X∣≥ε)≤E[∣Xn−X∣p]εp⟶0.\mathbb P(|X_n-X|\ge\varepsilon) \le \frac{\mathbb E[|X_n-X|^p]}{\varepsilon^p} \longrightarrow0.

因此,某个正阶绝对矩意义下的收敛蕴含依概率收敛。

对于均值为 μ\mu、方差为有限值 σ2\sigma^2 的独立同分布随机变量,其样本均值 X‾n\overline X_n 的方差为 σ2/n\sigma^2/n。因此,平方偏差形式的不等式给出

P(∣X‾n−μ∣≥ε)≤σ2nε2,\mathbb P(|\overline X_n-\mu|\ge\varepsilon) \le \frac{\sigma^2}{n\varepsilon^2},

从而证明了有限方差情形下的弱大数定律。

运行时间与计数论证

若非负运行时间 TT 的期望有限,则

P(T≥c E[T])≤1c,c>1.\mathbb P(T\ge c\,\mathbb E[T])\le\frac1c, \qquad c>1.

这可以将算法的期望运行时间保证转化为尾概率保证,不过所得保证往往较为保守。

若 NN 统计不希望发生的事件的数量,则 NN 是非负整数,且

P(N≥1)≤E[N].\mathbb P(N\ge1)\le\mathbb E[N].

对于有限个事件 A1,…,AnA_1,\ldots,A_n,令

N=∑i=1n1AiN=\sum_{i=1}^n\mathbf1_{A_i}

可得

P(⋃i=1nAi)≤∑i=1nP(Ai).\mathbb P\left(\bigcup_{i=1}^n A_i\right) \le \sum_{i=1}^n\mathbb P(A_i).

因此,由马尔可夫不等式和期望的线性性可以直接推出并集界,无须假设独立性。

局限与常见误用

非负性至关重要。可取正负值的随机变量可能由于较大的正值与负值相互抵消而具有很小的均值。例如,若 YY 分别以 1/21/2 的概率取值 100100 和 −100-100,则 E[Y]=0\mathbb E[Y]=0,但

P(Y≥50)=12.\mathbb P(Y\ge50)=\frac12.

若将 YY 代入适用于非负变量的公式,就会错误地得到零这一上界。正确的替代方法包括:对 ∣Y∣|Y|、∣Y∣|Y| 的正数次幂,或对 YY 进行平移后已知非负的变量应用该不等式。

该不等式给出的是上界,而不是实际概率的估计。若 X=1X=1 几乎必然成立,则

P(X≥10)=0,\mathbb P(X\ge10)=0,

而马尔可夫不等式只能给出上界 1/101/10。

最后,仅有有限一阶矩,既不能保证存在通用的指数衰减尾界,也不能推出二阶矩有限。更强的界需要额外信息,例如有界支撑集、更高阶矩、有限指数矩,或关于随机变量之和的结构性假设。