마르코프 부등식

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

확률론에서 마르코프 부등식(영어: Markov inequality)은 확률 변수함수가 어떤 양수 상수 이상일 확률에 대한 상계를 제시하는 부등식이다. 단, 이 함수는 음이 아니어야 한다. 마르코프 부등식이란 이름은 러시아 수학자 안드레이 마르코프의 이름에서 따온 것이다. (그러나 이 부등식은 마르코프의 스승인 파프누티 체비쇼프가 먼저 발견하였다)

마르코프 부등식은 다른 비슷한 부등식들과 함께 확률과 기댓값의 관계를 설명하고, 확률 변수의 누적 분포 함수에 대해 느슨한 경우가 많지만 유용한 한계를 제공한다.

설명[편집]

측도론 관점에서 보면 마르코프 부등식은 이런 뜻이다. (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에 대해서, IEE의 정의 확률 변수라 하자. 즉, E가 일어나면 IE = 1이고 일어나지 않으면 IE = 0이다. 따라서 사건 |X| ≥ a가 일어나면

I(|X| ≥ a) = 1

이고, 사건 |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로 나누면 마르코프 부등식을 얻는다.

일반적인 경우: 측도 이론을 이용한 증명[편집]

가측 집합 A에 대해서 1AA지시함수라 하자. 다시 말해서 xA일 때 1A(x) = 1이고, 다른 경우에는 0이다. AtAt = {xX| |f(x)| ≥ t}로 정의되면,

0\leq t\,1_{A_t}\leq |f|1_{A_t}\leq |f|.

따라서,

\int_X t\,1_{A_t}\,d\mu\leq\int_{A_t}|f|\,d\mu\leq\int_X |f|\,d\mu.

이제 이 부등식의 왼쪽이 다음 식과 같다는 것을 생각하면,

t\int_X 1_{A_t}\,d\mu=t\mu(A_t).

따라서 다음 식을 얻고,

t\mu(\{x\in X|\,|f(x)|\geq t\}) \leq \int_X|f|\,d\mu,

t > 0이므로 양변을 t로 나누어 다음 식을 얻을 수 있다.

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

응용[편집]

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