Markov's Inequality

음수가 아닌 값들의 평균의

k

배 이상인 값들이 전체에서

\frac{1}{k}

만큼의 비율 이상을 차지 할 수 없다는 이론.

P (∣ X ∣ \geq a) \leq \frac{E [ ∣ X ∣ ]}{a}

⇒ 어떠한 확률분포에 대해서도 성립한다. 우변이 1보다 커서 큰 의미가 없는 경우도 종종 있다.

단순히 생각해서, 평균을 $μ$ 라고 하고 절반( $k = 2$ )이 평균의 2배보다 크자고 하면 $\frac{N}{2} \times 2 μ$ 로 데이터 총합을 넘어서게 된다.

위는 이를 정리한 식으로, $a = k μ = k E [X]$ 라고 치환해 생각하면 동일하다.

P (∣ X ∣ \geq k E [X]) \leq \frac{E [ X ]}{k E [ X ]} = \frac{1}{k}

다시 정리해서, 평균의 $k$ 보다 클 확률은 아무리 커도 $\frac{1}{k}$ 를 넘을 수 없다.

Proof

지시확률변수의 기대값은 확률과 동일하므로

P (∣ X ∣ \geq a) = E [I (∣ X ∣ \geq a)] \leq \frac{E [ X ]}{a}

위에서 양변에 $a$ 를 곱하고 기대값을 벗겨내면

a I (∣ X ∣ \geq a) \leq ∣ X ∣

$∣ X ∣ < a$ ⇒ $a I (∣ X ∣ \geq a) \leq ∣ X ∣ = a \cdot 0 \leq ∣ X ∣$ 가 되어서 항상 참.
$∣ X ∣ \geq a$ ⇒ $a I (∣ X ∣ \geq a) \leq ∣ X ∣ = a \cdot 1 \leq ∣ X ∣$ : 조건 그 자체이므로 참.

따라서 성립한다.