不等式(一)-Markov与Chebyshev不等式

有些量很难计算，不等式可以对这些量给出一个界。例如，我们没有足够的信息来计算所需的量（例如事件的概率或随机变量的预期值）；又或者，问题可能很复杂，精确计算可能非常困难；还有些情况，我们可能希望提供一个通用的、适用于广泛问题的结果。
本节将学习两个不等式：Markov与Chebyshev不等式。

直观理解Markov不等式

我们凭直觉大致可以理解，观察值不会偏离期望值太多。Markov不等式和Chebyshev不等式把这种直觉放在坚实的数学基础上。接下来我们利用下面的图帮助我们理解这两个不等式：

其中，t是一个正数。蓝线（函数，输入小于t时，值是0，否则是t）在绿线（恒等函数）之下，我们可以得出以下不等式：
0 + ... + 0 + t + t + ... \leq 0 + 1 + 2 + ...
设随机变量X取非负数，p(i)表示i出现的概率，对上面不等式对应第i项乘p(i)得到：
0(p(0) + ... + p(t-1)) + t(p(t) + p(t+1) + ...) \leq 0(p0) + 1p(1) + 2p(2) + ...
即得到Markov不等式:
tP[X \ge t] \leq E(X)

从上面的图也可以看出等号成立的条件，即对所有i \neq 0,n时，p(i) = 0。不等式可以推广到所有取非负数的随机变量。

Markov不等式：
令X为非负随机变量，且假设E(X)存在，则对任意t>0，有
P[X \ge t] \leq \frac{E(X)}{t}

此外，当 t = k\mu，\mu = E(X)，P(X>k\mu) \leq \frac{1}{k}：

  • 当 k>1时，表示随机变量的取值离期望不会太远（离期望较远的概率很小，小于\frac{1}{k}）。P(X>2\mu)\leq 0.5 ,P(X>3\mu)\leq 0.33；
  • 当0 <k \leq 1时，1/k \geq 1，上式总成立表示P(A) \leq 1。

Morkov不等式的数学证明

对于1.1中的不等式关系进行证明如下：

\begin{eqnarray} E(X) = \int_{0}^{\infty} x f(x) dx &=& \int_{0}^{t} x f(x) dx + \int_{t}^{\infty} x f(x) dx \\ & \ge & \int_{t}^{\infty} x f(x) dx \\ & \ge & t\int_{t}^{\infty} f(x) dx \\ &=& t P(X > t) \end{eqnarray}

Chebyshev不等式

Chebyshev不等式：
令\mu = E(X), \sigma^{2} = D(X)，则：
P(|X - \mu| \geq t) \leq \frac{\sigma^2}{t^2} \qquad (1)
令Z = \frac{X-\mu}{\sigma}，
P(|Z| \ge k) \leq \frac{1}{k^2} \qquad (2)

对于(1)式的证明，借助Morkov不等式如下：
P(|X-\mu| \ge t) = P((X-\mu)^2 \ge t^2) \leq \frac{E( X - \mu )^2}{t^2} = \frac{\sigma^2}{t^2}

对于(2)式的证明：
P(|Z| \ge k) = P(|\frac{X-\mu}{\sigma}| \ge k) = P(|X-\mu| \ge k\sigma) \le \frac{\sigma^2}{k^2\sigma^2} = \frac{1}{k^2}
如P(|Z| \ge 2) \leq 1/4，P(|Z| \ge 3) \leq 1/9

X在其期望附近（t邻域）的概率与方差\sigma^2有关：

  • \sigma^2越大，随机变量离期望的概率越大（方差用于度量随机变量围绕均值的散布程度）；
  • \sigma^2越大，随机变量在期望附近，远离期望的概率越小。

需要注意的是，Chebyshev不等式没有限定分布的形式，所以应用广泛，但这个界很松，对某些具体的分布来说，可以得到更紧致的界，如高斯分布 Z ～N(0,1)
\begin{eqnarray} P(Z \geq t) &=& \frac {1}{\sqrt{2\pi}} \int_{t}^{\infty} x e^{-x^2/2}dx \\ &\leq& \frac {1}{\sqrt{2\pi}} \int_{t}^{\infty} \frac{x}{t} e^{-x^2/2}dx \\ &=& \frac {1}{t \sqrt{2\pi} } \lbrack - e^{-x^2/2}\rbrack_{t}^{\infty} \\ &=& \frac {1}{\sqrt{2\pi} } \frac{ e^{-t^2/2} }{t}\\ \end{eqnarray}
得到米尔不等式（Mill's inequality）：
P(|Z| \geq t) = 2P(Z \geq t) \leq \sqrt{ \frac {2}{\pi} } \frac{ e^{-t^2/2} }{t}
同样算P(|Z| \geq 3) = 0.00295，比Chebyshev不等式算出来的1/9要小。

例题：假设我们在一个有n个测试样本的测试集上测试一个预测方法（以神经网络为例）。若预测错误则设置X_i = 1，预测正确则设置X_i = 0。则\overline{X_n} = n^{-1}\sum_{i=1}^{n}X_i为观测到的错误率。每个X_i可视为有未知均值p的Bernoulli分布。我们想支持真正的错误率p。直观地，我们希望\overline{X_n}接近p。但\overline{X_n}有多大可能不在p的\epsilon邻域内？
D(\overline{X}) = D(X_1)/n^2 = p(1-p)n，
P(|\overline{X_n} - p| \geq \epsilon ) \leq \frac{D(\overline{X}) }{\epsilon^{2}} = \frac{p(1-p)}{n\epsilon^2} \leq \frac{1}{4n\epsilon^2}
由于对任意p有p(1-p) \leq 1/4，所以当\epsilon = 0.2，n=100 时，边界为0.0625。

Reference

  1. 《All of Statistics: A Concise Course in Statistical Inference》by Wasserman, Larry
  2. The Markov and Chebyshev Inequalities
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 203,937评论 6赞 478
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 85,503评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 150,712评论 0赞 337
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,668评论 1赞 276
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,677评论 5赞 366
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,601评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 37,975评论 3赞 396
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,637评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,881评论 1赞 298
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,621评论 2赞 321
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,710评论 1赞 329
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,387评论 4赞 319
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,971评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,947评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,189评论 1赞 260
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 44,805评论 2赞 349
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,449评论 2赞 342

推荐阅读更多精彩内容