Chernoff bound(체르노프 유계)

 

 체르노프 유계(Chernoff bound)는 마르코프 부등식(Markov's Inequality)과 체비쇼프 부등식(Chebyshyov's Inequality)과 같이 확률분포의 평균만 주어진 경우 또는 평균값과 분산값만 주어졌을때 확률의 상한(Upperbound)을 구할수 있게 하는 것을 목표로 합니다. 다시 말해, 평균이 특정 구간 내에 포함될 확률에 대한 정보를 제공하는 것을 목표로 합니다.

 

 먼저 정의를 보인 후 간단한 증명을 한 다음 예제를 통해 체르노프 유계를 이해해보도록 합시다.

 

정의

 

\(X\)가 \(1\leq i\leq n\) 구간에서 \(X_i\in\{0,1\}\)이고 \(P(X_i=1)=p_i\)일 때 \(E[X_i]=p_i\)라고 합시다.

\(X\)가 독립 랜덤변수, 즉 \(X=\sum^n_{i=1}X_i\)일 때 \(\mu\)는 \(X\)의 평균이라 하였을때

 

$$When\;\delta>0\;\begin{cases}P(X>(1+\delta)\mu) <(\frac{e^\delta}{(1+\delta)^{(1+\delta)}})^{\mu}\\P(X<(1-\delta)\mu) < (\frac{e^{-\delta}}{(1-\delta)^{(1-\delta)}})^\mu\end{cases}$$

 

 이를 그림으로 나타내면 다음과 같습니다.

 위 그래프를 보면 아시듯이 체르노프 유계는 평균을 중심으로 하여 \(\delta\)만큼 떨어진 구간에서부터 끝부분 까지의 꼬리 분포(Tail distribution)확률을 나타낸 것입니다. 이를 통해 평균을 기준으로 확률의 상한 및 하한을 알 수 있습니다. 

 

 지금부터는 체르노프 유계를 증명하고자 합니다. 증명에 어려움을 느끼시는 분이라면 증명 부분을 건너뛰고 응용 사례를 먼저 보고 오시는 것을 추천 드립니다.

 

증명

 

 먼저 마르코프 부등식(Marcov's Inequality)에 대한 이해가 필요합니다. 여기서는 체르노프 유계를 이해하기 위한 중요한 부분만을 보여드리고자 하오니 마르코프 부등식에 대해 좀 더 자세하게 알아보고자 하시는 분은 아래의 링크를 통해 확인해주시길 바랍니다.

 

m.blog.naver.com/PostView.nhn?blogId=mykepzzang&logNo=220838855204

[확률과 통계] 28. 마르코프 부등식과 체비쇼프 부등식, Markov's Inequality & Chebyshev's Inequality

 

 마르코프 부등식에서 랜덤 변수 X가 주어졌을 때

$$For\:any\:random\:variable\:X\geq0$$

$$P(X>\lambda)<\frac{E[X]}{\lambda}$$

$$P(f(X)>f(\lambda))<\frac{E[f(X)]}{f(\lambda)}$$

 

만약 \(f\)가 감소하지 않는 함수일 때 다음과 같은 공식이 성립됩니다.

$$P(X>\lambda)=P(f(X)>f(\lambda))<\frac{E[f(X)]}{f(\lambda)}$$

 

 다음으로 적률생성함수(Moment Generating Function)을 통해 체르노프 유계를 이해해보도록 하겠습니다. 여기서는 체르노프 유계를 증명하기 위한 방법만 소개드리고자 하오니 적률생성함수에 대해 자세히 알고 싶으신 분은 아래의 자료를 참조해주시기 바랍니다.

m.blog.naver.com/mykepzzang/220846464280

[확률과 통계] 45. 적률과 적률생성함수, Moment & Moment-Generating Function

 

 적률생성함수를 통해 상한값을 구할 때 다음과 같은 식을 유도할 수 있습니다. 만약 확률변수 X가 베르누이 분포라 가정하였을 때 다음과 같은 식을 유도할 수 있습니다.

$$\begin{split}
E[e^{tX}]&= E[e^{t\sum X_{i}}] \\
&=\sum^n_{x=0}e^{tx}\left(\begin{array}{c}n\\ x\end{array}\right)p^x(1-p)^{n-x}\\
&=\sum^n_{x=0}\left(\begin{array}{c}n\\x\end{array}\right)(pe^t)^x(1-p)^{n-x}\\
&\leq\prod_ie^{p_i(e^t-1)}\\
&=e^{\sum_ip_i(e^t-1)}\\
&=e^{(e^t-1)\mu}
\end{split}$$

 

 ※증명

 이제 본격적으로 체르노프 유계를 증명해보도록 하겠습니다. 위에서 보여드렸던 마르코프 부등식에 \(\lambda\)를 \((1+\delta)\mu\)로 대입하면 다음과 같은 식이 구해집니다.

 

$$\begin{split}
P(X>(1+\delta)\mu)&=P(e^{tX}>e^{t(1+\delta)\mu})\\
&\leq\frac{E[e^{tX}]}{e^{t(1+\delta)\mu}}\\
&\leq\frac{e^{(e^t-1)\mu}}{e^{t(1+\delta)\mu}}
\end{split}$$

 

 위의 식을 최소화시키기 위해 t에 다음과 같은 값을 대입합니다.

$$t=ln(1+\delta)$$

이를 식에 넣어 정리하면 다음과 같습니다.

$$\begin{split}
P(X>(1+\delta)\mu)
&\leq\frac{e^{(e^{ln(1+\delta)}-1)\mu}}{e^{(1+\delta)ln(1+\delta)\mu}}\\
&=\left(\frac{e^{(e^{ln(1+\delta)}-1)}}{e^{(1+\delta)ln(1+\delta)}}\right)^\mu\\
&=\left(\frac{e^\delta}{(1+\delta)^{1+\delta}}\right)^\mu
\end{split}$$

 

 위 식을 통해 체르노프 유계의 한쪽 끝부분인 상한을 증명하였습니다. 하한 또한 위의 식으로 갈음할 수 있으므로 주어진 체르노프 유계의 정의는 증명되었음을 확인하였습니다. 

 

응용

 

  지금까지 체르노프 유계의 정의와 증명과정을 살펴보았습니다. 이번에는 체르노프 유계가 어떻게 적용될 수 있는지 살펴보도록 하겠습니다.

 

 아래의 그림은 하나의 집단에서 야구와 축구를 좋아하는 사람들을 나타낸 것입니다.

 

 위 집단에서 좋아하는 운동에 대해 물어보았을 때 축구를 좋아할 확률을 \(p\)라고 하였을 때, 몇명이 축구를 좋아할까요?

 

 그림상으로는 총 인원수가 적기 때문에 금방 알아낼 수 있지만 만약 1만명 이상의 인원을 대상으로 한 사람씩 물어보는 것은 상당히 많은 시간이 소요되기 때문에 사실상 불가능합니다.

 최대한 균등하고 독립적으로 임의의 표본으로 n명을 뽑은 다음 \(X=\widetilde{p}n\)으로 계산하여 축구를 좋아하는 인원수를 구할 수 있을 것입니다. 즉, \(\widetilde{p}=\frac{X}{n}\)을 통해 확률 \(p\)를 예측할 수 있을 것으로 기대됩니다.

 

 X가 이항 랜덤 변수로 n회의 베르누이 수행을 하였고 성공확률이 p라고 예상하였을 때 모집단이 표본집단의 크기 n보다 충분히 클 때 다음이 성립됨을 알 수 있습니다.

$$E[X]=np$$

 다음과 같이 분포에서 평균 np의 위치를 쉽게 알 수 있습니다. 그렇다면 우리가 예상한 \(p\)가 실제 확률 \(\tilde{p}\)에 얼마나 근접한지 알 수 있을까요?

 

 \(p\)의 신뢰구간 \(1-\gamma\)을 \([\widetilde{p}-\delta,\tilde{p}+\delta]\)라 하였을 때 \(\gamma>0,\:\delta>0\)의 조건에서 다음과 같이 나타낼 수 있습니다.

$$P(p\in[\tilde{p}-\delta,\tilde{p}+\delta])\geq1-\gamma$$

즉 위의 식을 \(\gamma\)에 대해 다음과 같이 나타낼 수 있습니다.

$$P(p<\tilde{p}-\delta)+P(p>\tilde{p}+\delta)<\gamma$$

 

 이번에는 위에서 정의한 \(\gamma\)값에 대해 알아보도록 하겠습니다. 먼저 하한 구간에 대해 다음과 같이 구할 수 있습니다.

 

$$\begin{split}
P(p<\tilde{p}-\delta) &= P(\tilde{p}>p+\delta)\\
&= P(X>n(p+\delta)) \\
&= P(X>E[X](1+\frac{\delta}{p}))\\
&< e^{-\frac{np(\frac{\delta}{p})^2}{3}}\\
&= e^{-\frac{n\delta^2}{3p}}\\
&\leq e^{-\frac{n\delta^2}{3}}
\end{split}$$

 

 다음으로 상한 구간에 대해 다음과 같이 구할 수 있습니다.

 

\begin{split}
P(p>\tilde{p}+\delta) &= P(\tilde{p}<p-\delta)\\
&= P(X<n(p-\delta)) \\
&= P(X<E[X](1-\frac{\delta}{p}))\\
&< e^{-\frac{np(\frac{\delta}{p})^2}{2}}\\
&= e^{-\frac{n\delta^2}{2p}}\\
&\leq e^{-\frac{n\delta^2}{2}}
\end{split}

 

 위의 식을 통해 우리는 \(\gamma\)값을 다음과 같이 알아낼 수 있습니다.

$$\gamma=e^{-\frac{n\delta^2}{2}}+e^{-\frac{n\delta^2}{3}}$$

 

 위의 식을 보았을 때 갑자기 자연상수 e의 지수의 분모가 뜬금없이 2 혹은 3이 되어있는 것을 확인하실 수 있습니다. 앞에서 말씀드렸듯이 \(\delta\)는 매우 작은 값이고 위의 부등식을 통해 2 혹은 3을 대입하였을 때 \(\gamma\)의 값이 약간 넓어지면서 예측값 p의 범위가 더욱 타이트해졌음을 보실 수 있습니다. 즉, 편의상 간단하게 2 혹은 3을 대입하여 범위를 한정시킬 수 있어 2 혹은 3으로 대체해도 무방하다는 의미입니다.

 

 즉, 예측값 p를 구하기 위해 우리는 \(\gamma\), \(\delta\)와 n의 값을 조절함으로서 신뢰구간을 조정하여 범위를 한정함으로서 궁극적인 목표인 평균의 특정 구간을 한정함으로서 원하는 결과를 얻을 수 있음을 확인할 수 있습니다.