체르노프 부등식 (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 \geq a] \leq \frac{\mathbb{E}[X]}{a} \]를 만족한다.

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

\[ \mathbb{E}[X] = \sum_{x \geq 0} x Pr[X = x] \geq \sum_{x \geq a} x Pr[X = x] \geq \sum_{x \geq a} a Pr[X = x] = a Pr[X \geq a]\]

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

 

정리 2. 유용한 부등식

---

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

[증명] 간단히 보이자면, \( y = 1 + x \)는 \(y = e^x\)의 \(x = 0\)에서의 접선의 방정식이라서 만족합니다. 엄밀히는 \( y = e^x - x - 1 \)의 미분을 구하면 \(y' = 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 \geq 0 \)에 대해 \( \mathbb{E}[X] \leq U \)를 만족한다고 하자. 그러면 \( \delta > 0 \)에 대해, \[ Pr[X \geq (1 + \delta)U] < \left(\frac{e^\delta}{(1+\delta)^{(1+\delta)}}\right)^U\]를 만족한다.

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

\[ \mathbb{E}[X] = \sum_{i = 1}^n \mathbb{E}[X_i] = \sum_{i = 1}^n p_i \leq U \tag{1} \]

를 이끌어낼 수 있습니다.

 

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

\[ Pr[ X \geq (1 + \delta)U ] = Pr[ e^{tX} \geq e^{t(1+\delta)U} ] \leq \frac{ \mathbb{E}[e^{tX}] }{e^{t (1 + \delta) U}} \tag{2} \]

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

 

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

\[ \mathbb{E}[e^{tX_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^{tX_1}] \times \cdots \times \mathbb{E}[e^{tX_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} \leq e^{(e^t - 1)U}\]

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

\[ Pr[X \geq (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 \geq 0 \)에 대해 \( \mathbb{E}[X] \geq L \)를 만족한다고 하자. 그러면 \( 0 < \delta < 1 \)에 대해, \[ Pr[X \leq (1 - \delta)L] < \left(\frac{e^{-\delta}}{(1-\delta)^{(1-\delta)}}\right)^L\]를 만족한다.

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

 

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

\[ Pr[X \leq (1 - \delta)L] = Pr[ e^{tX} \leq e^{t(1-\delta)L} ] = Pr[ e^{-tX} \geq e^{-t(1-\delta)L} ] \leq \frac{\mathbb{E}[e^{-tX}]}{e^{-t(1-\delta)L}} \tag{3} \]

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

 

각 \(X_i\)에 대해서 정리 2를 통해 우리는

\[ \mathbb{E}[e^{-tX_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 } \leq e^{-(1-e^{-t})L} \]

을 확인할 수 있습니다. 여기서 마지막 부등식은 \( \mathbb{E}[X] = \sum_{i = 1}^n p_i \geq 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.