浅谈概率集中不等式

这里面真的只有概率矩阵不等式基础，但是我确实也是第一次正经写某些 bound 。

Markov Inequality

• 对于非负的随机变量 ，对于任意 有：

• 证明比较简单，做截断即可。

Chebyshev Inequality

• 对于随机变量 与任意的 ，有：

• 之前我给过另一个证明，是直接按定义展开积分然后用方差的定义。现在我们给出一个更简洁的证明，考虑：

Chernoff Bound

• 我们在 CS2701 的作业里面其实用过这个技巧，不过现在我们将正式介绍它。对于均值为 的随机变量 ，我们希望衡量其集中的程度，我们希望利用比一阶矩（Markov）或是二阶矩（Chebyshev）更强的条件，也就是 的矩生成函数。为此我们要做特地的构造，即：