맨위로가기

마르코프 부등식

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

마르코프 부등식은 측도 공간과 확률 공간에서 가측 함수 및 확률 변수의 확률에 대한 부등식이다. 임의의 양의 실수 a에 대해, |f(x)|가 a 이상일 확률은 |f|의 적분 값을 a로 나눈 값보다 작거나 같다는 것을 의미하며, 확률 변수 X에 대해서는 Pr(|X| ≥ a) ≤ E(|X|)/a가 성립한다. 이 부등식은 체비쇼프 부등식, 크라메르 부등식, 그리고 다양한 확장 및 변형의 기초가 되며, 소득 분포, 시험 실수 확률 등 다양한 분야에 응용된다. 마르코프 부등식은 안드레이 마르코프의 이름을 따서 명명되었지만, 그의 스승인 파프누티 체비쇼프가 먼저 발견했다.

2. 정의

측도 공간 (X,\Sigma,\mu) 위의 가측 함수 f\colon X\to(\bar\mathbb R,\mathcal B(\bar\mathbb R))가 주어졌다고 하자. '''마르코프 부등식'''에 따르면, 임의의 양의 실수 a\in\mathbb R^+에 대하여, 다음이 성립한다.[7]

:\mu(\{x\in X\colon|f(x)|\ge a\})\le\frac 1a\int_X|f|\mathrm d\mu

특히, 확률 공간 (\Omega,\mathcal F,\operatorname{Pr}) 위의 확률 변수 X\colon\Omega\to(\bar\mathbb R,\mathcal B(\bar\mathbb R))가 주어졌다고 하자. 그렇다면, 임의의 양의 실수 a\in\mathbb R^+에 대하여, 다음이 성립한다.

:\operatorname{Pr}(|X|\ge a)\le\frac{\operatorname E(|X|)}a

여기서 \operatorname E(|X|)기댓값이다.

만약 X가 음수가 아닌 확률 변수이고 a > 0이면, X가 적어도 a일 확률은 X의 기댓값을 a로 나눈 값보다 작거나 같다.[1]

:\operatorname{P}(X \geq a) \leq \frac{\operatorname{E}(X)}{a}.

\operatorname{E}(X) > 0일 때, a = \tilde{a} \cdot \operatorname{E}(X) 로 놓고 \tilde{a} > 0 을 대입하면 위 부등식을 다음과 같이 쓸 수 있다.

:\operatorname{P}(X \geq \tilde{a} \cdot \operatorname{E}(X)) \leq \frac{1}{\tilde{a}}.

측도론의 언어로 표현하면, 마르코프 부등식은 (X, \Sigma, \mu)가 측도 공간이고, f가측 함수이며 확장된 실수선 값을 갖는 함수이고, \varepsilon > 0일 때, 다음이 성립한다는 것이다.

: \mu(\{x\in X:|f(x)|\geq \varepsilon \}) \leq \frac 1 \varepsilon \int_X |f|\,d\mu.

이 측도론적 정의는 때때로 체비쇼프 부등식으로 불리기도 한다.[2]

마르코프 부등식은, 측도론적으로, (X, \Sigma, \mu)를 측도 공간으로 하고, 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}

3. 증명

마르코프 부등식은 측도론과 확률론, 두 가지 방식으로 증명할 수 있다. 측도론적 증명은 일반적인 측도 공간에서 부등식이 성립함을 보이고, 확률론적 증명은 확률 변수기댓값과 관련된 부등식으로 표현한다. 하위 섹션에서 자세한 증명을 다루므로, 여기서는 증명의 핵심 아이디어만 간략하게 제시한다.
측도론적 증명의 핵심은 적분 영역을 나누어 부등식을 유도하는 것이다. 함수 f의 절댓값이 특정 값 a 이상인 영역과 그렇지 않은 영역으로 나누어 르베그 적분을 계산하고, 이를 통해 부등식을 얻는다.
확률론적 증명은 확률 변수의 기댓값 정의를 이용하여 부등식을 유도한다. 확률 변수가 특정 값 a 이상일 때와 그렇지 않을 때로 나누어 기댓값을 계산하고, 이를 통해 마르코프 부등식을 얻는다.

3. 1. 측도론적 증명

측도 공간 (X,\Sigma,\mu) 위의 가측 함수 f\colon X\to(\bar\mathbb R,\mathcal B(\bar\mathbb R))가 주어졌다고 하자. '''마르코프 부등식'''에 따르면, 임의의 양의 실수 a\in\mathbb R^+에 대하여, 다음이 성립한다.[7]

:\mu(\{x\in X\colon|f(x)|\ge a\})\le\frac 1a\int_X|f|\mathrm d\mu

특히, 확률 공간 (\Omega,\mathcal F,\operatorname{Pr}) 위의 확률 변수 X\colon\Omega\to(\bar\mathbb R,\mathcal B(\bar\mathbb R))가 주어졌다고 하자. 그렇다면, 임의의 양의 실수 a\in\mathbb R^+에 대하여, 다음이 성립한다.

:\operatorname{Pr}(|X|\ge a)\le\frac{\operatorname E(|X|)}a

여기서 \operatorname E(|X|)기댓값이다.

다음과 같이 증명할 수 있다.

:\int_X|f|\mathrm d\mu

\ge\int_{\{x\in X\colon|f(x)|\ge a\}}|f|\mathrm d\mu

\ge\int_{\{x\in X\colon|f(x)|\ge a\}}a\mathrm d\mu

=a\mu(\{x\in X\colon|f(x)|\ge a\})



확률론의 언어로는 다음과 같이 증명할 수 있다.

:\operatorname E(|X|)

\ge\operatorname E(|X1_{\{\omega\in\Omega\colon|X(\omega)|\ge a\}}|)

\ge\operatorname E(a1_{\{\omega\in\Omega\colon|X(\omega)|\ge a\}})

=a\operatorname{Pr}(|X|\ge a)



함수 f의 절댓값만 방정식에 들어가므로, 함수 f가 음수가 아니라고 가정할 수 있다. 이제 다음과 같이 정의된 ''X'' 위의 실수 값 함수 ''s''를 고려해 보자.

:

s(x) =

\begin{cases}

\varepsilon, & \text{if } f(x) \geq \varepsilon \\

0, & \text{if } f(x) < \varepsilon

\end{cases}



그러면 0\leq s(x)\leq f(x)이다. 르베그 적분의 정의에 의해

:

\int_X f(x) \, d\mu \geq \int_X s(x) \, d \mu = \varepsilon \mu( \{ x\in X : \, f(x) \geq \varepsilon \} )



이며, \varepsilon >0 이므로, 양변을 \varepsilon로 나누면

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

임의의 가측 집합 ''A''에 대해, 1''A''를 그 특성 함수, 즉 ''x'' ∈ ''A''이면 1''A''(''x'') = 1, 그렇지 않으면 0으로 하자. ''At''를 ''At'' = {''x'' ∈ ''X''| |''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

가 된다.

3. 2. 확률론적 증명

확률 공간 (\Omega,\mathcal F,\operatorname{Pr}) 위의 확률 변수 X\colon\Omega\to(\bar\mathbb R,\mathcal B(\bar\mathbb R))와 임의의 양의 실수 a\in\mathbb R^+에 대하여, 다음 부등식이 성립한다.[7]

:\operatorname{Pr}(|X|\ge a)\le\frac{\operatorname E(|X|)}a

여기서 \operatorname E(|X|)기댓값이다.
증명::\operatorname E(|X|)

\ge\operatorname E(|X1_{\{\omega\in\Omega\colon|X(\omega)|\ge a\}}|)

\ge\operatorname E(a1_{\{\omega\in\Omega\colon|X(\omega)|\ge a\}})

=a\operatorname{Pr}(|X|\ge a)



만약 X가 음수가 아닌 확률 변수이고 a > 0이면, X가 적어도 a일 확률은 X의 기댓값을 a로 나눈 값보다 작거나 같다.[1]

:\operatorname{P}(X \geq a) \leq \frac{\operatorname{E}(X)}{a}.

\operatorname{E}(X) > 0일 때, a = \tilde{a} \cdot \operatorname{E}(X) 로 놓고 \tilde{a} > 0 을 대입하면 위 부등식을 다음과 같이 쓸 수 있다.

:\operatorname{P}(X \geq \tilde{a} \cdot \operatorname{E}(X)) \leq \frac{1}{\tilde{a}}.

다음은 두 가지 다른 증명 방법이다.
방법 1:기댓값의 정의와 X가 음이 아닌 확률 변수라는 사실로부터 다음이 성립한다.

:\operatorname{E}(X)=\int_{-\infty}^\infty xf(x) \, dx = \int_0^\infty xf(x) \, dx

이를 통해 다음을 유도할 수 있다.

:\operatorname{E}(X)=\int_0^a xf(x) \, dx + \int_a^\infty xf(x) \, dx \ge \int_a^\infty xf(x) \, dx \ge\int_a^\infty af(x) \, dx = a\int_a^\infty f(x) \, dx= a \operatorname{Pr}(X \ge a)

여기에서, a로 나누면,

:\Pr(X \ge a) \le \operatorname{E}(X)/a

임을 알 수 있다.
방법 2:임의의 사건 E에 대해, I_E E 의 지시 확률 변수라고 하자. 즉, E가 발생하면 I_E=1이고, 그렇지 않으면 I_E=0이다.

사건 X\geq a가 발생하면 I_{(X\geq a)}=1이고, X이면 I_{(X\geq a)}=0이다. a>0일 때,

:aI_{(X \geq a)} \leq X

가 성립한다. X이면, I_{(X\geq a)}=0이므로 a I_{(X\geq a)}=0\leq X이다. 그렇지 않으면, X\geq a이고, 이 경우 I_{X\geq a}=1이므로 aI_{X\geq a}=a\leq X이다.

\operatorname{E}는 단조 증가 함수이므로, 부등식의 양변에 기댓값을 취해도 부등식의 방향은 바뀌지 않는다. 따라서,

:\operatorname{E}(aI_{(X \geq a)}) \leq \operatorname{E}(X).

기댓값의 선형성에 의해,

:a\operatorname{E}(I_{(X \geq a)}) = a(1\cdot\operatorname{P}(X \geq a) + 0\cdot\operatorname{P}(X < a)) = a\operatorname{P}(X \geq a).

따라서,

:a\operatorname{P}(X \geq a) \leq \operatorname{E}(X)

이고, a로 나누면

:\operatorname{P}(X \geq a) \leq \frac{\operatorname{E}(X)}{a}

이다.

4. 확장 및 변형

만약 X영어가 음수가 아닌 확률 변수이고 이면, X영어가 적어도 일 확률은 X영어의 기댓값을 로 나눈 값보다 작거나 같다.[1]

:\operatorname{P}(X \geq a) \leq \frac{\operatorname{E}(X)}{a}.

\operatorname{E}(X) > 0일 때, a = \tilde{a} \cdot \operatorname{E}(X) 로 놓고 \tilde{a} > 0 을 대입하면 위 부등식을 다음과 같이 쓸 수 있다.

:\operatorname{P}(X \geq \tilde{a} \cdot \operatorname{E}(X)) \leq \frac{1}{\tilde{a}}.

측도론의 언어로 표현하면, 마르코프 부등식은 가 측도 공간이고, f가측 함수이며 확장된 실수선 값을 갖는 함수이고, 일 때, 다음이 성립한다는 것이다.

: \mu(\{x\in X:|f(x)|\geq \varepsilon \}) \leq \frac 1 \varepsilon \int_X |f|\,d\mu.

이 측도론적 정의는 때때로 체비쇼프 부등식으로 불리기도 한다.[2]

이후 확장된 내용들은 하위 섹션에서 다루고 있다.

4. 1. 증가 함수에 대한 확장

확률 공간 (\Omega,\mathcal F,\operatorname{Pr}) 위의 확률 변수 X\colon\Omega\to(\bar\mathbb R,\mathcal B(\bar\mathbb R)) 및 증가 가측 함수 \phi\colon(\mathbb R^+,\mathcal B(\mathbb R^+))\to(\mathbb R^+,\mathcal B(\mathbb R^+))가 주어졌다고 하자. 그렇다면, 임의의 양의 실수 a\in\mathbb R^+에 대하여, 다음 부등식이 성립한다.[7]

:\operatorname{Pr}(|X|\ge a)\le\frac{\operatorname E(|\phi(X)|)}{\phi(a)}

이는 다음과 같이 증명할 수 있다.

:\operatorname{Pr}(|X|\ge a)

=\operatorname{Pr}(|\phi(X)|\ge\phi(a))

\le\frac{\operatorname E(|\phi(X)|)}{\phi(a)}



만약 \phi\colon x\mapsto x^r (r\in\mathbb R^+)일 경우, 다음이 성립한다.[7]

:\operatorname{Pr}(|X|\ge a)\le\frac{\operatorname E(|X|^r)}{a^r}

만약 \phi\colon x\mapsto\exp(rx) (r\in\mathbb R^+)일 경우, 이는 다음과 같다. 이를 '''크라메르 부등식'''(Cramer’s inequality영어)이라고 한다.[7]

:\operatorname{Pr}(|X|\ge a)\le\frac{M_X(r)}{\exp(ra)}

여기서 M_X(r)모멘트 생성 함수이다.

만약 \varphi가 단조 감소하지 않는 음이 아닌 함수이고, X가 (반드시 음이 아닌 것은 아닌) 확률 변수이며, \varphi(a) > 0이면, 다음이 성립한다.[3]

:\operatorname P (X \ge a) \le \frac{\operatorname E(\varphi(X))}{\varphi(a)}.

0보다 큰 값에 대한 X의 고차 모멘트를 사용하면 다음 따름 정리를 얻는다.

:\operatorname P (|X| \ge a) \le \frac{\operatorname E(|X|^n)}{a^n}.

4. 2. 균등분포 확률 변수를 사용한 확장

X영어가 음이 아닌 확률 변수이고, a > 0이며, U영어[0,1]에서 균등 분포를 따르는 X영어와 독립인 확률 변수라면, 다음이 성립한다.[4]

:\operatorname{P}(X \geq Ua) \leq \frac{\operatorname{E}(X)}{a}.

U영어는 거의 확실하게 1보다 작으므로, 이 경계는 마르코프 부등식보다 엄격하게 강하다. 놀랍게도, U영어는 1보다 작은 어떤 상수로도 대체될 수 없으며, 이는 마르코프 부등식에 대한 결정론적 개선이 일반적으로 존재할 수 없음을 의미한다. 마르코프 부등식은 \{0,a\}에서 지지되는 분포에 대해 등식으로 성립하지만, 위의 확률화된 변형은 [0,a]에서 경계가 있는 모든 분포에 대해 등식으로 성립한다.

5. 따름정리

체비쇼프 부등식분산을 사용하여 확률 변수가 평균에서 멀리 벗어날 확률의 경계를 정하는 정리이다.[3] 체비쇼프 부등식은 확률 변수 (X - \operatorname{E}(X))^2 와 상수 a^2를 고려하여 마르코프 부등식에서 유도된다.

"단조" 결과는 다음과 같이 증명할 수 있다.

:\operatorname P (|X| \ge a) = \operatorname P \big(\varphi(|X|) \ge \varphi(a)\big) \,\overset{\underset{\mathrm{MI}}{}}{\leq}\, \frac{\operatorname E(\varphi(|X|))}{\varphi(a)}

양의 값을 갖는 확률 변수 X에 대해, X의 분위수 함수는 다음을 만족한다.

:Q_X(1-p) \leq \frac {\operatorname E(X)}{p},

증명은 다음과 같다.

:p \leq \operatorname P(X \geq Q_X(1-p)) \,\overset{\underset{\mathrm{MI}}{}}{\leq}\, \frac {\operatorname E(X)}{Q_X(1-p)}.

M \succeq 0 을 자기 수반 행렬 값의 확률 변수, A \succ 0 이라고 하면, 다음이 성립한다.

:\operatorname{P}(M \npreceq A) \leq \operatorname{tr}(\operatorname E (X) A^{-1})

5. 1. 체비쇼프 부등식

확률 공간 (\Omega,\mathcal F,\operatorname{Pr}) 위의 적분 가능 확률 변수 X\colon\Omega\to(\bar\mathbb R,\mathcal B(\bar\mathbb R))가 주어졌을 때, 임의의 양의 실수 a\in\mathbb R^+에 대하여 다음 부등식이 성립한다.

:\operatorname{Pr}(|X-\operatorname E(X)|\ge a)\le\frac{\operatorname{Var}(X)}{a^2}

여기서 \operatorname{Var}(X)분산이다.

체비쇼프 부등식분산을 사용하여 확률 변수가 평균에서 멀리 벗어날 확률의 상한을 구한다. 구체적으로,

:\operatorname{P}(|X-\operatorname{E}(X)| \geq a) \leq \frac{\operatorname{Var}(X)}{a^2},

a > 0 인 모든 경우에 적용된다.[3] 여기서 Var(X)는 X의 분산이며, 다음과 같이 정의된다.

: \operatorname{Var}(X) = \operatorname{E}[(X - \operatorname{E}(X) )^2].

체비쇼프 부등식은 확률 변수

: (X - \operatorname{E}(X))^2

와 상수 a^2, 를 고려하여 마르코프 부등식으로부터 유도된다. 마르코프 부등식은 다음과 같다.

: \operatorname{P}( (X - \operatorname{E}(X))^2 \ge a^2) \le \frac{\operatorname{Var}(X)}{a^2}.

이 논증은 다음과 같이 요약할 수 있다 (여기서 "MI"는 마르코프 부등식의 사용을 나타낸다):

:\operatorname{P}(|X-\operatorname{E}(X)| \geq a) =

\operatorname{P}\left((X-\operatorname{E}(X))^2 \geq a^2\right) \,\overset{\underset{\mathrm{MI}}{}}{\leq}\,

\frac {\operatorname{E} \left( (X-\operatorname{E}(X))^2 \right)}{a^2} =

\frac{\operatorname{Var}(X)}{a^2}.

5. 2. 크라메르 부등식

만약 \phi\colon x\mapsto\exp(rx) (r\in\mathbb R^+)일 경우, 다음 공식이 성립한다. 이를 '''크라메르 부등식'''(Cramer’s inequality영어)이라고 한다.[7]

:\operatorname{Pr}(|X|\ge a)\le\frac{M_X(r)}{\exp(ra)}

여기서 M_X(r)모멘트 생성 함수이다.

5. 3. 기타 따름정리

"단조" 결과는 다음과 같이 증명할 수 있다.

:\operatorname P (|X| \ge a) = \operatorname P \big(\varphi(|X|) \ge \varphi(a)\big) \,\overset{\underset{\mathrm{MI}}{}}{\leq}\, \frac{\operatorname E(\varphi(|X|))}{\varphi(a)}

양의 값을 갖는 확률 변수 X에 대해, X의 분위수 함수는 다음을 만족한다.

:Q_X(1-p) \leq \frac {\operatorname E(X)}{p},

증명은 다음과 같다.

:p \leq \operatorname P(X \geq Q_X(1-p)) \,\overset{\underset{\mathrm{MI}}{}}{\leq}\, \frac {\operatorname E(X)}{Q_X(1-p)}.

M \succeq 0 을 자기 수반 행렬 값의 확률 변수, A \succ 0 이라고 하자. 그러면

:\operatorname{P}(M \npreceq A) \leq \operatorname{tr}(\operatorname E (X) A^{-1})

유사하게 증명할 수 있다.

6. 응용

마르코프 부등식은 체비쇼프 부등식 증명에 사용되며, 어떤 집합공집합이 아님을 증명하는 등 존재 증명에도 응용된다.

6. 1. 일반적인 응용

소득이 음수가 아니라고 가정하면, 마르코프 부등식에 의해 인구의 10% (1/10)를 초과하는 사람이 평균 소득의 10배 이상을 가질 수 없다.[6]

또 다른 예로, 앤드류가 통계학 시험에서 평균 4개의 실수를 한다고 하자. 앤드류가 최소 10개 이상의 실수를 할 확률에 대한 최댓값은 0.4이다. 앤드류가 정확히 10개의 실수를 할 확률이 0.4이고, 실수를 전혀 하지 않을 확률이 0.6이라면, 기대값은 정확히 4개의 실수가 된다.

  • 마르코프 부등식은 체비쇼프 부등식의 증명에 사용된다.
  • ''X''를 비음의 정수값 확률 변수라고 하고 (조합론에서 자주 사용되는 것처럼), 마르코프 부등식에서 ''a'' = 1로 하면, \textrm{Pr}(X \neq 0) \leq \textrm{E}(X)를 얻을 수 있다. ''X''를 어떤 집합의 농도라고 하면, 이로부터 이 집합이 공집합이 아님을 증명할 수 있다. 이처럼 존재 증명에도 응용할 수 있다.

7. 역사

마르코프 부등식이란 이름은 러시아 수학자 안드레이 마르코프의 이름에서 따온 것이다. 그러나 이 부등식은 마르코프의 스승인 파프누티 체비쇼프가 먼저 발견하였다.

참조

[1] 논문 Halving the Bounds for the Markov, Chebyshev, and Chernoff Inequalities Using Smoothing https://www.tandfonl[...] 2019-11-26
[2] 서적 Real Analysis
[3] 서적 Probability inequalities Springer
[4] 간행물 Randomized and Exchangeable Improvements of Markov's, Chebyshev's and Chernoff's Inequalities 2023
[5] 웹사이트 Markov's Inequality for Matrices https://stephentu.gi[...] 2024-05-27
[6] 서적 5.4 Probability inequalitlies {{!}} An Introduction to Probability and Simulation https://bookdown.org[...]
[7] 서적



본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com