체르노프 부등식 (Chernoff Bounds)

Photo by Kelli McClintock on Unsplash

여러분의 눈 앞에 총 $n$개의 서로 다른 상자가 놓여 있다고 합시다. 각 상자 안에는 흰 공과 검은 공으로만 차 있습니다. 여러분은 각 상자의 흰 공과 검은 공의 비율이 얼마나 되는지 모두 알고 있습니다. 즉, $i$ 번째 상자에는 $p_i$의 비율로 흰 공이 있다고 해 보겠습니다. 여러분이 상자에서 각각 공을 하나씩 뽑는다면 과연 흰 공은 몇 개를 뽑게 될까요? 그 기댓값은 구하기 쉽습니다. 바로 기댓값의 선형성(linearity of expectation)에 의해 $\sum _{i=1}^n{p}_i$ 개가 될 것입니다.

 

그렇다면 실제로 공을 뽑았을 때, 과연 흰 공의 개수가 기댓값 혹은 기댓값 부근의 값이 될 확률은 얼마나 될까요? 이는 신뢰의 문제입니다. 만약 그 값이 들쭉날쭉하다면 우리는 해당 기댓값을 믿기 어려울 것입니다. 이 질문에 대한 답을 주는 것이 오늘 소개할 체르노프 부등식(Chernoff bounds)입니다. 이 부등식은 확률 변수(random variable)가 그 기댓값으로부터 벗어날 확률이 항상 그리 크지 않음을 보여줍니다. 랜덤 알고리즘(randomized algorithm) 및 확률적 분석(probabilistic analysis)뿐만 아니라 컴퓨터 과학 전반에 걸쳐 요긴하게 활용되는 개념이어서 이번에 정리하게 되었습니다.

---

다음은 체르노프 부등식을 증명할 때 필요한 정리들입니다.

정리 1. 마르코프 부등식(Markov's inequality)

---

만약 $X$가 음이 아닌 수만을 갖는 확률 변수라고 하면, 어떤 상수 $a>0$에 대해, $$Pr[X\ge a]\le \frac{\mathbb{E}[X]}{a}$$를 만족한다.

[증명] $X$가 음이 아닌 수만을 갖는다고 하였으므로,

$$\mathbb{E}[X]=\sum _{x\ge 0}xPr[X=x]\ge \sum _{x\ge a}xPr[X=x]\ge \sum _{x\ge a}aPr[X=x]=aPr[X\ge a]$$

를 이끌어낼 수 있습니다. 양변을 $a>0$로 나누면 모든 증명이 완료됩니다. ■

 

정리 2. 유용한 부등식

---

모든 $x\in \mathbb{R}$에 대하여, $1+x\le e^x$를 만족한다. 특히, 등식은 $x=0$일 때만 만족한다.

[증명] 간단히 보이자면, $y=1+x$는 $y=e^x$의 $x=0$에서의 접선의 방정식이라서 만족합니다. 엄밀히는 $y=e^x-x-1$의 미분을 구하면 $y^{\prime }=e^x-1$이 되어, $y=e^x-x-1$이 $x<0$에서는 단조 감소, $x>0$에서는 단조 증가하고, $x=0$에서 극점을 이루는 함수라는 것을 확인할 수 있습니다. $e^0-0-1=0$이므로 정리의 명제가 모두 만족한다는 사실을 보일 수 있습니다. ■

위 도식은 $y=e^x$를 빨간색 선으로 $y=1+x$를 파란색 선으로 나타낸 것입니다.

---

이제 체르노프 부등식이 무엇인지 소개하도록 하겠습니다.

정리 3. 체르노프 부등식 1

---

$X_1,\cdots ,X_n$을 0 혹은 1의 값을 가지면서 서로 독립(independent)인 확률 변수라고 하자. 각 $X_i$는 $p_i$의 확률로 1의 값을 갖는다. 이때, $p_i>0$을 만족하며, $p_i$가 서로 같을 필요는 없다. $X:=\sum _{i=1}^n{X}_i$가 어떤 상수 $U\ge 0$에 대해 $\mathbb{E}[X]\le U$를 만족한다고 하자. 그러면 $\delta >0$에 대해, $$Pr[X\ge (1+\delta )U]<{\left(\frac{e^{\delta }}{(1+\delta {)}^{(1+\delta )}}\right)}^U$$를 만족한다.

[증명] 먼저 기댓값의 선형성에 의해

$$\begin{array}{}\text{(1)}& \mathbb{E}[X]=\sum _{i=1}^n\mathbb{E}[X_i]=\sum _{i=1}^n{p}_i\le U\end{array}$$

를 이끌어낼 수 있습니다.

 

양수의 값을 갖는 아무 $t>0$에 대해, $y=e^{tx}$는 모든 $x\in \mathbb{R}$에 대해 단조 증가하면서 항상 0보다 큰 값을 가지므로

$$\begin{array}{}\text{(2)}& Pr[X\ge (1+\delta )U]=Pr[e^{tX}\ge e^{t(1+\delta )U}]\le \frac{\mathbb{E}[e^{tX}]}{e^{t(1+\delta )U}}\end{array}$$

를 이끌어낼 수 있습니다. 여기서 마지막 부등식은 마르코프 부등식(정리 1)을 적용하여 얻을 수 있습니다.

 

이제 $\mathbb{E}[e^{tX}]$에 대해서 정리해 보겠습니다. 먼저 각 $X_i$는 $p_i$의 확률로 1을 갖고 $1-p_i$의 확률로 0을 가지므로,

$$\mathbb{E}[e^{t{X}_i}]=(1-p_i)e^{t\cdot 0}+p_i{e}^{t\cdot 1}=1+p_i(e^t-1)<e^{p_i(e^t-1)}$$

임을 확인할 수 있습니다. 특히 마지막은 $p_i>0$, $t>0$이라는 가정에 의해 $p_i(e^t-1)>0$이고 이를 정리 2의 $x$에 대입하면 이끌어낼 수 있습니다.

 

따라서, $X$의 정의에 의해,

$$\mathbb{E}[e^{tX}]=\mathbb{E}[e^{t(X_1+\cdots +X_n)}]=\mathbb{E}[e^{t{X}_1}]\times \cdots \times \mathbb{E}[e^{t{X}_n}]<e^{p_1(e^t-1)}\times \cdots \times e^{p_n(e^t-1)}=e^{(e^t-1)\sum _{i=1}^n{p}_i}\le e^{(e^t-1)U}$$

가 됩니다. 여기서 마지막 부등식은 식 1에서 유도할 수 있습니다. 이를 식 2에 대입하면,

$$Pr[X\ge (1+\delta )U]<\frac{e^{(e^t-1)U}}{e^{t(1+\delta )U}}$$

를 얻을 수 있습니다. 위 식은 임의의 $t>0$에 대해서 성립하기 때문에, $t=\ln (1+\delta )>0$으로 잡으면 정리의 식을 이끌어낼 수 있습니다. ■

 

위 정리를 통해 확률 변수 $X$가 기댓값보다 훨씬 커질 확률이 그렇게 크지 않다는 것을 알 수 있습니다. 그러면 작아지는 경우는 어떨까요? 위와 비슷한 방식으로 우리는 $X$가 기댓값보다 훨씬 작아질 확률도 그리 크지 않음을 보일 수 있습니다.

정리 4. 체르노프 부등식 2

---

$X_1,\cdots ,X_n$을 0 혹은 1의 값을 가지면서 서로 독립(independent)인 확률 변수라고 하자. 각 $X_i$는 $p_i$의 확률로 1의 값을 갖는다. 이때, $p_i>0$을 만족하며, $p_i$가 서로 같을 필요는 없다. $X:=\sum _{i=1}^n{X}_i$가 어떤 상수 $L\ge 0$에 대해 $\mathbb{E}[X]\ge L$를 만족한다고 하자. 그러면 $0<\delta <1$에 대해, $$Pr[X\le (1-\delta )L]<{\left(\frac{e^{-\delta }}{(1-\delta {)}^{(1-\delta )}}\right)}^L$$를 만족한다.

[증명] 많은 부분은 정리 3의 증명과 비슷하며, 따라서 바뀌는 부분을 집중적으로 설명하도록 하겠습니다.

 

임의의 양수 $t>0$에 대해 $y=e^{tx}$는 단조 증가하면서 $0$보다 항상 큽니다. 따라서 우리는

$$\begin{array}{}\text{(3)}& Pr[X\le (1-\delta )L]=Pr[e^{tX}\le e^{t(1-\delta )L}]=Pr[e^{-tX}\ge e^{-t(1-\delta )L}]\le \frac{\mathbb{E}[e^{-tX}]}{e^{-t(1-\delta )L}}\end{array}$$

을 이끌어낼 수 있습니다. 이때 두 번째 등식은 역수를 취한 것입니다.

 

각 $X_i$에 대해서 정리 2를 통해 우리는

$$\mathbb{E}[e^{-t{X}_i}]=(1-p_i)+p_i{e}^{-t}=1-p_i(1-e^{-t})<e^{-p_i(1-e^{-t})}$$

임을 알 수 있습니다. 따라서,

$$\mathbb{E}[e^{-tX}]<e^{-(1-e^{-t})\sum _{i=1}^n{p}_i}\le e^{-(1-e^{-t})L}$$

을 확인할 수 있습니다. 여기서 마지막 부등식은 $\mathbb{E}[X]=\sum _{i=1}^n{p}_i\ge L$에서 얻을 수 있습니다. 이를 식 3에 대입한 후, $t=\ln \frac{1}{1-\delta }>0$으로 잡으면 정리의 식이 나온다는 것을 알 수 있습니다. ■

---

이것으로 체르노프 부등식에 대한 정리를 마칩니다. 체르노프 부등식은 위에서 소개한 형식 외에도 무수히 많은 변형과 일반화된 버전이 존재합니다. 실례로 위에서는 $\{X_i{\}}_{i=1,\cdots ,n}$가 서로 독립이라고 가정하였으나, 음의 상관관계(negatively correlated)를 갖는 경우에도 성립하는 것으로 알고 있습니다. 이를 사용하여 알고리즘을 분석한 논문을 몇 번 본 기억이 있습니다. 여하튼 이 부등식은 다른 분야에서와 마찬가지로 컴퓨터 과학에서도 매우 요긴하게 사용되니 잘 알아 두시면 좋겠죠.

 

글의 내용에 잘못된 점이 있거나, 궁금하신 사항이 있으시면 알려 주시기 바랍니다. 고맙습니다.

출처

[1] Rajeev Motwani and Prabhakar Raghavan. Randomized algorithms. Cambridge university press, 1995.

 

[2] David P. Williamson and David B. Shmoys. The design of approximation algorithms. Cambridge university press, 2011.