8.36 체비셰프 부등식과 확률 한계

1. 마르코프 부등식(Markov’s Inequality)

비음 확률 변수 $X \geq 0$ 에 대해 $a > 0$ 이면:

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

마르코프 부등식은 가장 기본적인 확률 한계(probability bound)로, 기댓값만으로 꼬리 확률(tail probability)의 상한을 제공한다. 분포에 대한 어떤 가정도 필요하지 않다.

유한 분산 $\sigma^2$ 을 갖는 확률 변수 $X$ 에 대해:

$P(\lvert X - \mu \rvert \geq k\sigma) \leq \frac{1}{k^2}$

동치 표현: $P(\lvert X - \mu \rvert \geq \epsilon) \leq \frac{\sigma^2}{\epsilon^2}$

유도: $Y = (X - \mu)^2 \geq 0$ 에 마르코프 부등식을 적용하면 $P(Y \geq \epsilon^2) \leq \mathbb{E}[Y]/\epsilon^2 = \sigma^2/\epsilon^2$ 이다.

체비셰프 상한은 분포에 무관하게 성립하므로 매우 보수적이다. 가우시안 분포에서의 실제 확률은 상한보다 훨씬 작다.

$P(X - \mu \geq k\sigma) \leq \frac{1}{1 + k^2}$

양측 체비셰프보다 단측에서 더 긴밀한(tight) 상한을 제공한다.

적률 생성 함수를 이용한 지수적(exponential) 꼬리 한계이다.

$P(X \geq a) \leq \min_{t > 0}e^{-ta}M_X(t)$

체르노프 한계는 체비셰프 부등식보다 훨씬 긴밀한 상한을 제공하며, 지수적으로 감소하는 꼬리를 갖는 분포(가우시안, 지수 등)에서 특히 효과적이다.

$X \sim \mathcal{N}(\mu, \sigma^2)$ 에 대해:

$P(X \geq \mu + a) \leq \exp\left(-\frac{a^2}{2\sigma^2}\right)$

이 한계는 가우시안 꼬리의 지수적 감쇠를 정확히 포착한다.

유계 독립 확률 변수 $X_i \in [a_i, b_i]$ 의 합에 대한 집중 부등식(concentration inequality)이다.

$P\left(\lvert\bar{X}_n - \mu\rvert \geq t\right) \leq 2\exp\left(-\frac{2n^2t^2}{\sum_{i=1}^{n}(b_i - a_i)^2}\right)$

분산 정보 없이도 지수적 꼬리 한계를 제공하며, 유한 표본에서의 몬테카를로 추정 오차의 비확률적(non-asymptotic) 상한에 사용된다.

로봇의 위치 오차가 안전 한계를 초과하지 않을 확률을 보장해야 할 때, 분포에 무관한 체비셰프 한계가 보수적이지만 안전한 상한을 제공한다.

$P(\lVert\mathbf{e}\rVert \geq d_{safe}) \leq \frac{\text{tr}(\boldsymbol{\Sigma})}{d_{safe}^2}$

가우시안 가정이 타당하면 체르노프 한계나 카이제곱 분위수에 의한 더 긴밀한 한계를 사용할 수 있다.

확률적 제약 $P(g(\mathbf{x}) \leq 0) \geq 1 - \delta$ 를 결정론적 제약으로 변환할 때, 체비셰프 부등식 또는 체르노프 한계에 기반한 보수적 변환이 사용된다.

로봇 학습에서 유한 표본으로부터의 일반화 오차 한계가 회프딩 부등식이나 라데마허(Rademacher) 복잡도에 기반한 집중 부등식으로 도출된다.

$1 - \delta$ 의 확률로 $\epsilon$ 이하의 오차를 달성하기 위해 필요한 표본 수의 하한이 확률 한계로부터 결정된다.

Papoulis, A., & Pillai, S. U. (2002). Probability, Random Variables, and Stochastic Processes (4th ed.). McGraw-Hill.
Grimmett, G. R., & Stirzaker, D. R. (2001). Probability and Random Processes (3rd ed.). Oxford University Press.
Boucheron, S., Lugosi, G., & Massart, P. (2013). Concentration Inequalities. Oxford University Press.

version: 1.0