Markov / Chebyshev / Hoeffding Inequality

The Markov Inequality

If $X \geq 0$ and $a>0$, $P(X\geq a)\leq \frac{E[X]}{a}$

 

Expectation만 알고 있을때 확률변수가 상수 a보다 클 확률에 대해,

어느 정도의 upper bound를 예측할 수 있게 해줌.

Bound가 tight하지 않을 수 있기 때문에 정보량이 크지는 않음.

 

- 큰 값에 대한 기준 a가 커질 수록 확률은 줄어듦 (더 rare한 event)

- E[X]가 커질 수록 큰 값 a(고정)가 나올 확률은 늘어남

 

증명 1.

증명2. 

예시.

- 첫번째 예시의 경우 exponential distribution가 a보다 클 확률은 a에 대해서 exponential한 속도로 감소하는데 비해, 1/a는 linear한 속도로 감소함. 즉 a가 커질 수록 bound는 loose해짐. -> 더 타이트한 바운드의 필요성 (e.g. Chebyshev)

 

The Chebyshev inequality

 

수학적으로는 Markov inequality의 application. 

분산도 알고 있을때 사용. 정보가 더 많으므로 더 tight한 bound를 제공.

 

- variance가 작으면 확률변수가 평균으로부터 일정 거리 c이상 떨어질 확률도 줄어든다.

- 거리의 판단 기준 c가 커지면 확률변수가 평균으로부터 그만큼 떨어질 수 있는 확률도 줄어든다.

- c는 양수로 가정. c가 음수일 경우 거리는 무조건 양수이므로 무조건 확률은 1이된다. 아무 의미가 없음. 

 

증명.

부등호 양변을 제곱 후에 Markov inequality를 이용하면 쉽게 증명 가능.

예시.

같은 예제에 대해서 Chebyshev inequality의 꼴로 변형하면 더 tight한 바운드를 구할 수 있음.

 

Hoeffding's inequality

 

$X$를 bernoulli random variable로 가정하고

$Y= X_1 + X_2 + ... + X_n$ 라고 정의하면,

Central limit theorem에 의해서 Y는 approximately gaussian을 따르게 되고,

$P(frac{Y}{\sqrt{n}}\geq a)\approx 1-\Phi(a)$로 구할 수 있음. ($\Phi$는 standard normal CDF)

이로 인해, $P(Y\geq \sqrt{n}a)$의 upper bound를 계산 가능. 

그러나 우리가 원하는 bound는 $P(Y\geq na)$에 대한 것임.

 

Chebyshev inquality를 이용하면, upper bound를 구할 수 있음: $P(Y\geq na) \leq \frac{1}{na^2}$

Hoeffding's inequality는 이보다 더 타이트한 bound를 제공: $P(Y\geq na) \leq e^{-na^2/2}$

증명:

$X_i$가 i.i.d.라고 가정해야만 아래와 같이 유도 가능.

 

유도하다 보면, $P[Y\geq na]\leq \rho^n$의 꼴로 나타낼 수 있음.

파란색 그래프에서 (각각 왼쪽 식의 분자 / 분모를 나타냄) 충분히 작은 $s$를 택할 경우,

($s>0$이고 0에 가까운 영역에서) 해당 값($=\rho$)이 1보다 작아지게 되어야만,

확률 $P[Y\geq na]$의 lower bound가 $n$이 증가함에 따라 $\rho^n$ 값이 수렴할 수 있게 된다.

이를 만족하는 적당한 $s$의 값을 $s=a$라고 하면, $\leq e^{-na^2/2}$라는 최종 bound가 나오게 됨.

 

$X_i$가 bernoulli distribution 이외에 다른 분포를 따르게 될 경우, 

$E[e^{sx_i}]$가 다르게 표현될 수는 있지만, 파란 그래프와 같은 수렴성은 똑같이 보장되며,

이렇게 추가적으로 일반화된 것을 Chernoff bound라고 함.

 

그렇다면 $s=a$일 때, 다음 inequality가 만족하는지에 대한 수학적 증명을 살펴보자.

$[\frac{\frac{1}{2}(e^s+e^{-s})}{e^{sa}}]^n \leq e^{-na^2/2}$ (위에서는 intuitive하게 살펴보았음)

요약하면, 분모를 $e^s$에 대한 taylor expansion을 이용해서 치환하고,

그 안에서 나오는 factorial에 대해서 upperbound를 구한 뒤,

정리한 식에서 $s=a$를 대입하면,

우리가 위에서 보았던 inequality가 그대로 나옴을 볼 수 있음.

 

동영상 출처:

https://www.youtube.com/playlist?list=PL9nlf3JtLINpZLAOktCI-2KggSYdrm_11