체비쇼프 부등식

역사 raw
대문 랜덤 문서 최근 토론
분류
1. 개요2. 증명3. 기타

1. 개요[편집]

Chebyshev inequality

러시아의 수학자 파프누티 체비쇼프(Pafnuty Chebyshev)가 발견한 절대부등식으로 그의 이름을 땄다. 확률 분포를 정확히 모를 때 해당 확률 분포의 평균과 표준편차의 값만으로 특정한 확률의 최솟값만큼은 알아낼 수 있는 부등식이다.

확률 분포의 평균을 μ\mu, 표준편차를 σ\sigma라 하면 다음이 성립한다. 이를 체비쇼프 부등식이라고 한다. 단, kk는 양의 상수이다.

P[∣X−μ∣<kσ]=P[μ−kσ<X<μ+kσ]≥1−1k2\begin{aligned}P[|X-\mu|<k\sigma]&=P[\mu-k\sigma<X<\mu+k\sigma]\\&\geq1-\dfrac1{k^2}\end{aligned}

예를 들어 k=2k=2이면, 확률변수 XX가 μ±2σ\mu\pm 2\sigma 내에 있을 확률은 확률 분포에 관계없이 1−1/22=3/41-1/{2^2}=3/4 이상이다.

2. 증명[편집]

집합 판별 함수의 활용으로 다음처럼 증명할 수 있다.

P[∣X−μ∣≥kσ]=E[1∣X−μ∣≥kσ]≤E[1∣X−μ∣≥kσ⋅∣X−μ∣2k2σ2]≤1k2σ2E[∣X−μ∣2]=1k2\begin{aligned} P[|X-\mu|\ge k\sigma] &= \mathbb{E} [ 1_{|X-\mu|\ge k \sigma} ] \\&\le \mathbb{E} \left[ \mathbf{1}_{|X-\mu| \ge k \sigma} \cdot \frac{|X-\mu|^2}{k^2 \sigma^2} \right] \\ &\le \frac{1}{k^2 \sigma^2} \mathbb{E} [ |X-\mu|^2 ] \\&= \frac{1}{k^2} \end{aligned}

연속확률변수에 대해서 비슷한 아이디어의 증명을 다음과 같이 풀어쓸 수 있다. 확률 분포의 평균을 μ\mu, 표준편차를 σ\sigma, 함수를 f(x)f(x)라 하면
σ2=E[(X−μ)2]=∫−∞∞(x−μ)2f(x) dx=∫−∞μ−kσ(x−μ)2f(x) dx+∫μ−kσμ+kσ(x−μ)2f(x) dx+∫μ+kσ∞(x−μ)2f(x) dx≥∫−∞μ−kσ(x−μ)2f(x) dx+∫μ+kσ∞(x−μ)2f(x) dx(∵∫μ−kσμ+kσ(x−μ)2f(x) dx≥0)\begin{aligned}\sigma^2&=E[(X-\mu)^2]=\displaystyle\int_{-\infty}^{\infty}(x-\mu)^2f(x)\,{\rm d}x\\&=\int_{-\infty}^{\mu-k\sigma}(x-\mu)^2f(x)\,{\rm d}x+\int_{\mu-k\sigma}^{\mu+k\sigma}(x-\mu)^2f(x)\,{\rm d}x+\int_{\mu+k\sigma}^{\infty}(x-\mu)^2f(x)\,{\rm d}x\\&\geq\int_{-\infty}^{\mu-k\sigma}(x-\mu)^2f(x)\,{\rm d}x+\int_{\mu+k\sigma}^{\infty}(x-\mu)^2f(x)\,{\rm d}x \quad \biggl(\because\int_{\mu-k\sigma}^{\mu+k\sigma}(x-\mu)^2f(x)\,{\rm d}x\geq 0\biggr) \end{aligned}[1]
한편 (x−μ)2≥k2σ2 (↔ x≤μ−kσ or x≥μ−kσ)(x-\mu)^2\geq k^2\sigma^2\,(\leftrightarrow\,x\leq\mu-k\sigma\,\textsf{or}\,x\geq\mu-k\sigma)일 때는 다음이 성립한다.
σ2≥∫−∞μ−kσ(x−μ)2f(x) dx+∫μ+kσ∞(x−μ)2f(x) dx≥∫−∞μ−kσk2σ2f(x) dx+∫μ+kσ∞k2σ2f(x) dx\begin{aligned}\sigma^2&\geq\displaystyle\int_{-\infty}^{\mu-k\sigma}(x-\mu)^2f(x)\,{\rm d}x+\int_{\mu+k\sigma}^{\infty}(x-\mu)^2f(x)\,{\rm d}x\\&\geq\int_{-\infty}^{\mu-k\sigma}k^2\sigma^2f(x)\,{\rm d}x+\int_{\mu+k\sigma}^{\infty}k^2\sigma^2f(x)\,{\rm d}x\end{aligned}
양 끝 식을 k2σ2k^2\sigma^2으로 나누면
1k2≥∫−∞μ−kσf(x) dx+∫μ+kσ∞f(x) dx(∵k2σ2≥0)\begin{aligned}\dfrac1{k^2}\geq\displaystyle\int_{-\infty}^{\mu-k\sigma}f(x)\,{\rm d}x&+\int_{\mu+k\sigma}^{\infty}f(x)\,{\rm d}x \quad (\because k^2\sigma^2\geq 0)\end{aligned}
f(x)f(x)는 확률 밀도 함수이기 때문에 ∫−∞∞f(x) dx=1\int_{-\infty}^{\infty}f(x)\,{\rm d}x=1이므로
1−1k2≤∫μ−kσμ+kσf(x) dx=P[μ−kσ≤X≤μ+kσ]=P[∣X−μ∣<kσ]\begin{aligned}1-\dfrac1{k^2}\leq\displaystyle\int_{\mu-k\sigma}^{\mu+k\sigma}f(x)\,{\rm d}x&=P[\mu-k\sigma\leq X\leq\mu+k\sigma]\\&=P[|X-\mu|<k\sigma]\end{aligned}

3. 기타[편집]

  • 등호조건이 존재하는데, 확률변수가 1/(2k2)1/(2k^2)의 확률로 값 μ±kσ\mu \pm k\sigma를 가지고, 나머지 확률로 값 μ\mu를 가지면 된다.
  • 체비쇼프 부등식은 다양한 확률부등식의 기초이긴 하지만 실전에선 최약체(...)로 평가받는데, 확률론을 조금만 배우면 Hoeffding's inequality, Chernoff bound 등등 훨씬 강한 유계를 주는 확률부등식들을 배우기 때문이다. 물론 모든 확률분포에 대해 성립하는 범용적인 부등식이 강력한 유계를 줄 수 있을 리도 없고, 실전에선 주로 등장하는 모종의 확률변수에 한정적으로 적용되는 특별한 부등식을 개발해 쓰는 것이니 이는 당연하다. 오히려 이런 대부분의 확률부등식들을 증명하기 위해서 이 체비쇼프 부등식과 젠센 부등식이 기본으로 사용되고, 이 둘의 역할을 서로 다른 것으로 대체할 수 없다는 점 때문에[2] 중요성이 꽤나 큰 부등식이다.
  • LpL^p-공간 버전으로 다음과 같은 일반화를 생각할 수 있다. 이때 체비쇼프 부등식은 p=2p=2, z=kσz=k\sigma인 경우이다.

P[∣X−μ∣≥z]≤∥X−μ∥pzp\begin{aligned}P[|X-\mu| \ge z] \le \frac{\|X-\mu\|_p}{z^p} \end{aligned}
  • 경시대회 등에 주로 등장하는 체비쇼프 합 부등식과는 다르다.
[1] ∫μ−kσμ+kσf(x) dx\displaystyle\int_{\mu-k\sigma}^{\mu+k\sigma}f(x)\,{\rm d}x는 확률의 값이므로 0 이상이고 (x−μ)2≥0(x-\mu)^2\geq 0이므로 ∫μ−kσμ+kσ(x−μ)2f(x) dx≥0\displaystyle\int_{\mu-k\sigma}^{\mu+k\sigma}(x-\mu)^2f(x)\,{\rm d}x\geq 0이다.[2] 확률변수 XX에 대한 정보로 f(X)f(X)에 대한 부등식을 이끌어낸다고 생각할 때, 체비쇼프 부등식은 f(x)=1∣x−μ∣>kσf(x) = \mathbf{1}_{|x-\mu|>k \sigma}의 경우로 간주할 수 있지만, 저 계단 함수는 볼록이 아니다. 즉 체비쇼프 부등식은 이런 유형의 문제에서 젠센 부등식과는 본질적으로 다른 접근을 취한다고 볼 수도 있다.