逆向きのマルコフの不等式

マルコフの不等式とは確率の不等式を扱うときに必ずといっていいほど出てきます。

定理1 (マルコフの不等式).

$X$が非負の値をとる確率変数とする. 任意の$a>0$に対して

$$\begin{align*} \Pr[X\geq a] \leq \frac{\mathbf{E}[X]}{a}. \end{align*}$$

この不等式はChernoff boundやAzuma-Hoeffdingなど基本的な確率集中不等式の証明やunion boundの証明にも使えます. 実際, $k$個の事象$E_1,\dots,E_k$に対して$X$を$E_1,\dots,E_k$の中で発生した事象の個数を表す確率変数とすると, マルコフの不等式より

$$\begin{align*} \Pr\left[\bigcup_{i=1}^k E_i\right] = \Pr[X\geq 1] \leq \mathbf{E}[X]=\sum_{i=1}^k\Pr[E_i] \end{align*}$$

を得ます.

マルコフの不等式は$X$の期待値が小さければ$X$が小さくなりやすいというごく当たり前のことを主張する不等式です. では, 逆に期待値が大きければ$X$が大きくなりやすいという方向の不等式はないのでしょうか?

このようなことを示したいときは以下に示す「逆向きの」マルコフの不等式が使えないかを考えるのが最も基本的です：

定理2 (逆向きのマルコフの不等式)

$X$が$[0,1]$値をとる確率変数とし, $\mu=\mathbf{E}[X]$とすると,

$$\begin{align*} \Pr[X\geq \mu/2] \geq \mu/2. \end{align*}$$

証明.

マルコフの不等式より,

$$\begin{align*} \Pr[X\leq 1-a] = \Pr[1-X\geq a] \leq \frac{1-\mu}{a} \end{align*}$$

ここで$a=1-\mu/2$を代入すると

$$\begin{align*} \Pr[X\leq \mu/2] \leq \frac{1-\mu}{1-\mu/2} = 1-\frac{\mu/2}{1-\mu/2} \leq 1-\mu/2. \end{align*}$$

(証明終).