Markov 和 Chebyshev 不等式

这篇小文章讲一下概率中的几个界，也就是几个不等式。是为了给后面通信中的一些理论提供基础，例如极化码中极化特性的推导，需要用到 Chernoff-Hoeffding 不等式。

我们先讲讲这些界的出发点，即马尔可夫不等式 (Markov Inequality).

X 是一个非负的随机变量，均值是  , 那么 :

证明：

简单整理后得到公式 (1).

如果再知道方差，那么我们可以得到更好的估计（Chebyshev 不等式)：

其中  是随机变量 X 的方差。

证明：

构建一个新的随机变量

则根据方差的定义

使用 Markov 不等式：

则：

注意：

      在公式 (3) 中，不需要有 这个条件。