마르코프 부등식

확률론에서 마르코프 부등식은 확률 변수의 함수가 어떤 양수 상수 이상일 확률에 대한 상계를 제시한다. 단, 이 함수는 음이 아니어야 한다. 마르코프 부등식이란 이름은 러시아 수학자 안드레이 마르코프의 이름에서 따온 것이다.

마르코프 부등식은 확률을 기대값과 연관짓고, 느슨하기는 하지만 확률 변수의 누적 분포 함수에 대한 유용한 한계를 제공한다. (이는 다른 비슷한 부등식의 특징이기도 하다.)

설명

측도 이론의 언어로 보면 마르코프 부등식은 이런 뜻이다. (X,Σ,μ)가 측도 공간이고 f는 잴 수 있는 확장된 실수값 함수이고 t > 0이면

$\mu (\{x\in X|\,|f(x)|\geq t\})\leq {1 \over t}\int _{X}|f|\,d\mu .$

특별한 경우로 측도가 1인 공간(확률 공간)에서는 이렇게 말할 수 있다. X가 확률 변수이고 a > 0일 때

${\textrm {Pr}}(|X|\geq a)\leq {\frac {{\textrm {E}}(|X|)}{a}}.$

증명

측도 공간이 확률 공간인 경우를 따로 증명한다. 일반적인 증명에서 이 경우만 떼어낸 것은 일반 독자가 읽기 쉽도록 하기 위해서이다.

특수한 경우: 확률론

어떤 사건 E에 대해서, I_E를 E의 정의 확률 변수라 하자. 즉, E가 일어나면 I_E = 1이고 일어나지 않으면 I_E = 0이다. 따라서 사건 |X| ≥ a가 일어나면 I_{(|X| ≥ a)} = 1이고, 사건 if |X| < a가 일어나면 I_{(|X| ≥ a)} = 0이다. 그러면 a > 0인 a가 주어질 때,

$aI_{(|X|\geq a)}\leq |X|.\,$

이다. 따라서

$\operatorname {E} (aI_{(|X|\geq a)})\leq \operatorname {E} (|X|).\,$

이다. 이제 부등식 왼쪽이 아래 식과 같으므로

$a\operatorname {E} (I_{(|X|\geq a)})=a\Pr(|X|\geq a).\,$

다음 식을 얻는다.

$a\Pr(|X|\geq a)\leq \operatorname {E} (|X|)\,$

그리고 a > 0이므로, 양변을 a로 나눌 수 있다.

일반적인 경우: 측도 이론

Q.E.D.

응용

• 마르코프 부등식은 체비쇼프 부등식을 증명하는 데 사용한다.
• X가 음이 아닌 정수값을 갖는 확률 변수라면(조합론에서 이런 경우가 많다), a = 1일 때 마르코프 부등식은 ${\textrm {Pr}}(X\neq 0)\leq {\textrm {E}}(X)$ 꼴이 된다. X가 어떤 집합의 크기라면 이 부등식을 써서 그 집합이 비어 있지 않다는 것을 증명할 수 있다. 존재성을 증명할 때 쓴다.