マルコフの不等式

マルコフの不等式

マルコフの不等式は、確率論における基本的な結果であり、非負の確率変数がある値を超える確率の上限を提供します。

非負の確率変数 XX とその期待値 E[X]\mathbb{E}[X] に対して、任意の a>0a > 0 について次が成り立ちます：

P(X≥a)≤E[X]a.P(X \geq a) \leq \frac{\mathbb{E}[X]}{a}.

証明

期待値の定義より：

E[X]=∫0∞x dP(x).\mathbb{E}[X] = \int_{0}^{\infty} x \, dP(x).

積分を [0,a)[0, a) と [a,∞)[a, \infty) に分ける：

E[X]=∫0ax dP(x)+∫a∞x dP(x)≥∫a∞x dP(x).\begin{align*} \mathbb{E}[X] &= \int_{0}^{a} x \, dP(x) + \int_{a}^{\infty} x \, dP(x) \\ &\geq \int_{a}^{\infty} x \, dP(x). \end{align*}

x≥ax \geq a であることから：

∫a∞x dP(x)≥a∫a∞dP(x)=aP(X≥a).\int_{a}^{\infty} x \, dP(x) \geq a \int_{a}^{\infty} dP(x) = a P(X \geq a).

よって：

E[X]≥aP(X≥a).\mathbb{E}[X] \geq a P(X \geq a).

両辺を aa で割ると：

P(X≥a)≤E[X]a.P(X \geq a) \leq \frac{\mathbb{E}[X]}{a}.

□\square

Reverse Markov’s Inequality

最大値 MM を持つ確率変数 XX に対して、以下が成り立つ：

P(X≤a)≤M−E[X]M−aP(X\le a) \le \frac{M-\mathbb E[X]}{M-a}

証明

確率変数 Y=M−XY = M - X を考える。YY は非負確率変数で、E[Y]=M−E[X]\mathbb{E}[Y] = M - \mathbb{E}[X] である。

マルコフの不等式を YY に適用すると、任意の b>0b > 0 について：

P(Y≥b)≤E[Y]b=M−E[X]bP(Y \geq b) \leq \frac{\mathbb{E}[Y]}{b} = \frac{M - \mathbb{E}[X]}{b}

ここで b=M−ab = M - a とすると：

P(Y≥M−a)≤M−E[X]M−aP(M−X≥M−a)≤M−E[X]M−aP(X≤a)≤M−E[X]M−a\begin{align*} P(Y \geq M - a) &\leq \frac{M - \mathbb{E}[X]}{M - a} \\ P(M - X \geq M - a) &\leq \frac{M - \mathbb{E}[X]}{M - a} \\ P(X \leq a) &\leq \frac{M - \mathbb{E}[X]}{M - a} \end{align*}

□\square

References