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

作者: _与谁同坐_ | 来源:发表于2019-07-03 20:57 被阅读0次

不等式(二)-Hoeffding不等式
不等式(一)-Markov与Chebyshev不等式
马尔可夫不等式和切比雪夫不等式
Cauchy-Schwarz不等式、Hölder不等式与Mink
柏舟日記｜辭舊迎新
【高等数学】不等式的解和解集
高考数学真题篇：正难则反的数学思想，反证法在不等式中的应用
高中数学题型五十六《解不等式》
数学笔记：不等式
柯西-施瓦茨不等式

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

《All of Statistics: A Concise Course in Statistical Inference》by Wasserman, Larry
The Markov and Chebyshev Inequalities

不等式(二)-Hoeffding不等式
接着上一节的那些不等式们(一)-Markov与Chebyshev不等式本节将学习Hoeffding不等式。 Hoe...
不等式(一)-Markov与Chebyshev不等式
有些量很难计算，不等式可以对这些量给出一个界。例如，我们没有足够的信息来计算所需的量（例如事件的概率或随机变量的预...
马尔可夫不等式和切比雪夫不等式
Markov's Inequality 中文叫马尔科夫不等式或马尔可夫不等式。若随机变量只取非负值，则，有证明...
Cauchy-Schwarz不等式、Hölder不等式与Mink
本文介绍几个常用的与期望有关的不等式。 1 Cauchy–Schwarz不等式 Cauchy–Schwarz不等式...
柏舟日記｜辭舊迎新
2022年01月31日深夜“均值不等式，柯西不等式，权方和不等式，舒尔不等式，琴生不等式，贝努利不等式，契比雪夫...
【高等数学】不等式的解和解集
不等式概念：式子中有解不等式：解不等式的过程称之为不等式，解不等式的值的取值范围成为解值，解不等式的未知数的值称...
高考数学真题篇：正难则反的数学思想，反证法在不等式中的应用
考点:数列与不等式的综合，整体思想，综合法的应用，考查不等式的证明与应用，等比数列的求和公式，放缩法证明不等式，属...
高中数学题型五十六《解不等式》
我们通常遇到的解不等式有一元二次不等式、含绝对值不等式、分式不等式，这里解的不等式是利用导数求单调性，再结合函数的...
数学笔记：不等式
三角不等式伯努利不等式二项不等式均值不等式调和平均数、集合平均数、算术平均数和二次平均数杨氏不等式施瓦...
柯西-施瓦茨不等式
Cauchy-Schwarz 不等式这是一个非数考研经常会遇到的不等式 Cauchy-Schwarz 不等式接...