チェビシェフの不等式
チェビシェフの不等式:$ xを確率変数とする。任意の非負の実数$ \varepsilonに対して次式が成り立つ。
$ \mathrm{Pr}(|x - E[x]| \ge \varepsilon) \ \le \ \frac{\mathrm{Var}[x]}{\varepsilon^2}
証明: マルコフの不等式より
$ \mathrm{Pr}(|x - E[x]| \ge \varepsilon) = \mathrm{Pr}(|x - E[x]|^2 \ge \varepsilon^2) \le \frac{E[|x - E(x)|^2]}{\varepsilon^2} = \frac{\mathrm{Var}[x]}{\varepsilon^2}
-------
この定理は、確率分布からサンプル$ x を引いてきたときに、それが期待値から$ \varepsilon 以上離れている確率の上限が $ \frac{\mathrm{Var}[x]}{\varepsilon^2} であると述べている。