马尔可夫不等式
证明：基于指示器
对于任意非负随机变量$X$，对于任意的$a>0$恒有：
$$
Pr\left( X\ge a \right) \le \frac{\mathbb{E}\left( X \right)}{a}
$$
$Proof$：令$I=I\left( X\ge a \right) $，易知：
$$
I\le \lfloor \frac{X}{a} \rfloor \le \frac{X}{a}
$$
故可得：
$$
Pr\left( X\ge a \right) =\mathbb{E}\left( I \right) \le \mathbb{E}\left( \frac{X}{a} \right) =\frac{\mathbb{E}\left( X \right)}{a}
$$
证明：基于全期望公式
$Proof$：由全期望公式：
$$
\mathbb{E}\left( X \right) =\mathbb{E}\left[ X|X< a \right] \cdot Pr\left( X< a \right) +\mathbb{E}\left[ X|X\ge a \right] \cdot Pr\left( X\ge a \right)
$$
易得：
$$
\mathbb{E}\left[ X|X\ge a \right] \ge a;\ \mathbb{E}\left[ X | X < a \right] \ge 0
$$
即：
$$
\mathbb{E}\left( X \right) \ge a\cdot Pr\left( X\ge a \right) +0\cdot Pr\left( X < a \right)
$$
进而有：
$$
Pr\left( X\ge a \right) \le \frac{\mathbb{E}\left( X \right)}{a}
$$
拓展
方差补充
