随机算法常用不等式

随机算法常用不等式,持续更新中。

Markov 不等式

定理

对于任意非负随机变量 XX,有:

P(Xt)E(X)tP(X \ge t) \le \frac{E(X)}{t}

对任意的 t>0t>0 成立。

从直观上可以理解为,某高中生平时成绩已知的情况下,高考即使发挥超常或者失误平均分都变化不会太大。我们可以根据平时的平均分判断该考生分数超过给定分数 tt 的概率。

证明

关键用到了积分、放缩法。

P(Xt)=x=tP(X=x)dxxtx=txtP(X=x)dx=1tx=txP(X=x)dx1tx=0xP(X=x)dx=E(X)t\begin{aligned} P(X \ge t) &= \int_{x=t}^{\infty}P(X=x)dx \\ &利用 x \ge t \\ &\le \int_{x=t}^{\infty}\frac{x}{t}P(X=x)dx \\ &= \frac{1}{t}\int_{x=t}^{\infty}xP(X=x)dx \\ &\le \frac{1}{t}\int_{x=0}^{\infty}xP(X=x)dx \\ &= \frac{E(X)}{t} \end{aligned}

推广:

P(Xt)1E(X)tP(X \le t) \ge 1-\frac{E(X)}{t}

Chebyshev 不等式

定理

对任意随机变量 XX,有:

P(XE(X)t)D(X)t2P(|X-E(X)| \ge t) \le \frac{D(X)}{t^2}

对任意 t0t \ge 0 成立。

从直观上可以理解为,在已知方差的的情况下,随机变量与均值的偏差超过一定值的概率不会超过确定值。平时成绩越稳定的同学,考试时出现失误的概率就会比较小。

证明

Y=[XE(X)]2Y = [X-E(X)]^2YY 是非负随机变量,

XE(X)t    Yt2|X-E(X)| \ge t \iff Y \ge t^2

利用 Markov 不等式即可得出结论:

E(Yt2)E(Y)t2=D(X)t2E(Y \ge t^2) \le \frac{E(Y)}{t^2} = \frac{D(X)}{t^2}

文章作者: upupming
文章链接: https://blog.upupming.site/2019/03/20/inequality-in-randomized-algorithm/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 upupming 的博客