马尔可夫不等式 & 切比雪夫不等式

首先，让我们回顾马尔可夫不等式。

P[ X \ge \epsilon ]\le \frac{E[ X^r]} {\epsilon^r}\space (\epsilon > 0)

Markov 不等式衡量了随机变量大于某个正数 \epsilon 概率的上界（由期望限制）。

将 上式 的 X 替换为另一个随机变量： \lvert X-E(X)\rvert ，再令 r = 2 即可得到切比雪夫不等式。

P[ \lvert X-E(X)\rvert \ge \epsilon ] \le \frac{D(X)}{\epsilon^2}

这个不等式对于分布没有具体要求，可以用来求得 随机变量 X 离散程度的上界（受 D(X) 约束）。

矩生成函数

矩生成函数按如下方式定义：
M_{X}(s)=\mathbb{E}[e^{sX}]= \int e^{sx}f_X(x)dx

其拥有下述性质：
\frac{d}{ds}M_{X}(s)=\mathbb{E}[Xe^{sX}]

切尔诺夫限

切尔诺夫限是 马尔可夫不等式 的直接应用。
对于 \lambda > 0 ，
P[ X \ge \epsilon ] = P[ e^{\lambda X} \ge e^{\lambda\epsilon} ]\le \frac{\mathbb{E}[e^{\lambda X}]}{e^{\lambda \epsilon}} （应用 r = 1 的马尔可夫不等式）

假设 X_{i}(1\le i\le n) 的均值为 \mu_i(1\le i \le n) 且这 n 个随机变量相互独立。
则
P[\sum_{i=1}^n(X_i-\mu_i) \ge \epsilon]\le \frac{\mathbb{E}[e^{\lambda\sum_{i=1}^n(X_i-\mu_i)}]}{e^{\lambda \epsilon}}=\frac{\prod_{i=1}^n\mathbb{E}[e^{\lambda(X_i-\mu_i)}]}{e^{\lambda\epsilon}}

上式被称为 切尔诺夫不等式，用来求 n 个独立的随机变量和 大于 某个整数概率的上界。

例子：bound l2 norm

假设 X_{i}\sim \mathcal{N}(0, 1)(1\le i\le n) 且这 n 个随机变量相互独立。
则二范数的平方 Y=\sum_{i=1}^n X_i^2 。应用切尔诺夫不等式易知

P[\sum_{i=1}^n X_i^2 \ge \epsilon]\le \frac{\prod_{i=1}^n M_{X_i^2}(\lambda)}{e^{\lambda\epsilon}}

又由于卡方分布的矩生成函数为 \frac{1}{\sqrt{1-2\lambda}} 。

所以最后有：
P[\sum_{i=1}^n X_i^2 \ge \epsilon]\le \frac{1}{(1-2\lambda)^{\frac{n}{2}}e^{\lambda\epsilon}} 对任意的 \lambda > 0 均成立。

我们还可将不等式右侧看作 \lambda 的函数，找到使得函数值最小的 \lambda_0 ，进一步加强不等式。