2022年2月24日木曜日

Markovの不等式とChebyshevの不等式

今後の記事で参照できるようにするために, 確率に関する非常に基礎的な不等式であるMarkovの不等式とChebyshevの不等式を紹介します. Markovの不等式さえ覚えていればChebyshevの不等式は非常に簡単に導出できます.

定理 (Markovの不等式). $X$を平均が有限であるような非負の確率変数$X$とする. 任意の$a>0$に対し$\Pr[X\geq a]\leq \mathrm{E}[X]/a$.

証明(概要). 簡単のため$X$を離散値をとる確率変数とする. 任意の$a>0$に対し,
$$\mathrm{E}[X] \geq \sum_{i\geq a} i\Pr[X=i] \geq a\sum_{i\geq a} \Pr[X=i]=a\Pr[X\geq a].$$
$X$が連続値をとる場合でも同様に証明できる.
(証明終)


定理 (Chebyshevの不等式). $X$を平均と分散が有限な実数値確率変数とする. 任意の$a>0$に対し, $\Pr[|X-\mathrm{E}|\geq a] \leq \frac{\mathrm{Var}[X]}{a^2}$.

証明. 確率変数$(X-\mathrm{E}[X])^2$は非負なので, Markovの不等式より
$$\Pr[|X-\mathrm{E}[X]|>\lambda] = \Pr[(X-\mathrm{E}[X])^2>\lambda^2] \leq \frac{\mathrm{Var}[X]}{\lambda^2}.$$
(証明終)


0 件のコメント:

コメントを投稿

解の個数を減らす帰着 (Valiant--Vaziraniの定理)

2月に 冬のLA に参加してこれまで5,6年くらい常に取り組みようやく身を結んだ共同研究を発表してきました. 2月のLAではD2辺りからずっと取り組んでいた個人的未解決問題がある程度解決できたことについて発表させていただきます。 — Nobutaka Shimizu (@kn...