상자에 공 넣기, 상자를 두 개씩 고르면? (Power of Two Choices)

Photo by Rumman Amin on Unsplash

지난 포스트에서는 상자에 공 넣기 문제(balls into bins problem)를 공부했습니다.

2020/03/21 - [수학적 도구/Randomness] - 상자에 공 넣기 (Balls into Bins Problem)

상자에 공 넣기 (Balls into Bins Problem)

문제는 다음과 같았습니다. 우리에게 \(n\) 개의 공이 주어지고 우리는 이를 \(n\) 개의 상자에 담으려고 합니다. 만약 우리가 공을 하나씩 넣을 때마다 상자를 균등한 확률(uniformly at random)로 고르고 그 상자에 공을 넣는다고 합시다. 그러면 높은 확률로 모든 상자는 들어간 공의 개수가 \( \frac{3\ln n}{ \ln \ln n} \)을 넘지 않는다는 것을 보일 수 있었습니다. 이 문제는 컴퓨터과학 분야에서 중요한 역할을 담당하며, 가장 유명한 예시로는 체이닝 기법(separate chaining)을 사용하는 해시 테이블(hash table)에서 모든 엔트리에 딸린 연결 리스트의 길이의 상한을 이 문제를 잘 변형하여 얻을 수 있다는 것입니다.

 

이번에는 매번 상자를 하나씩 뽑지 말고 두 개씩 뽑아 봅시다.^[ㄱ] 그리고 둘 중에서 더 적은 개수의 공이 들어간 상자에 공을 넣어 주도록 하죠. 만약 두 상자에 담긴 공의 개수가 동일하면 아무데나 넣어주면 됩니다. 위 방법에 비해서 약간의 노력이 더 필요하긴 합니다만 그렇다고 그렇게 많은 작업도 아닙니다. 과연 이렇게 했을 때 성능을 얼마큼 좋아질까요? 놀랍게도 아주 큰 폭으로 좋아지게 됩니다.

정리 1. 두 개씩 고르는 것의 능력

---

임의의 \(n\)에 대해 \(n\) 개의 공을 \(n\) 개의 상자에 넣어야 한다고 하자. 공을 넣을 때마다 매번 두 개의 상자를 균등한 확률로 고르고 그중 더 적은 개수가 담긴 상자에 공을 넣는다고 하자.(단, 담긴 개수가 같은 경우 아무데나 넣는다.) 그러면 높은 확률로 모든 상자는 담긴 공의 개수가 \( \frac{\ln \ln n}{\ln 2} + O(1) \)을 넘지 않는다.

두 개씩 뽑는 것은 어떤 효용성이 있을까요? 이는 여전히 중요한 의미를 갖습니다. 위 해싱 예제를 다음과 같이 확장시켜 보도록 하겠습니다. 예전에는 하나의 해시 함수(hash function)를 가지고 있었다면 이번에는 두 개의 해시 함수 \(h_1\)과 \(h_2\)를 만들어 보죠. 이번 해시 테이블은 매번 데이터 \(x\)가 들어오면 \(h_1(x)\)와 \(h_2(x)\)의 값을 구하고 각 인덱스의 엔트리에 딸린 두 연결 리스트의 길이를 비교한 다음 둘 중 더 짧은 연결 리스트에 삽입합니다. 이는 우리가 이번에 고민할 문제와 매우 흡사하고 따라서 높은 확률로 각 연결 리스트의 길이가 해시 함수를 하나만 사용할 때보다 훨씬 짧다는 것을 알 수 있습니다. 반대로 데이터 \(x\)를 찾을 때는 어떻게 할까요? \(h_1(x)\)와 \(h_2(x)\)를 구한 후 두 엔트리의 연결 리스트를 모두 순회하면 됩니다. 어차피 연결 리스트의 길이가 그렇게 길지 않다는 것을 알기에, 이를 두 번 순회하는 것도 그렇게 오래 걸리지 않기 때문이죠.

배경 지식

이번에도 증명을 위해서는 여러 알려진 기법들을 습득할 필요가 있습니다. 먼저 이항 분포(binomial distribution)는 \(p\)의 확률로 앞면이 나오고 \(1 - p\)의 확률로 뒷면이 나오는 편향된 동전(biased coin)을 총 \(n\) 번 던져 동전의 앞면이 나온 횟수가 따르는 분포입니다. 이는 간단히 \(B(n, p)\)로 나타냅니다. 아래의 글에서는 \(B(n, p)\) 자체가 해당 분포를 따르는 확률 변수로 사용되기도 합니다. 다음은 본 증명에서 사용될 이항 분포에 관한 유용한 성질입니다.

정리 2. Tail bound of binomial distribution

---

\(Pr \left[ B(n,p) \geq e \cdot np \right] \leq e^{-np}\)를 만족한다.

[증명] 임의의 확률 변수 \(X\)에 대해 그것의 기댓값을 \(\mu := \mathbb{E}[X]\)라고 하였을 때, 임의의 \(\delta > 0\)에 대해 \[ Pr\left[ X \geq (1 + \delta) \mu \right] \leq \left( \frac{e^\delta}{(1 + \delta)^{(1 + \delta)}} \right)^\mu \]가 항상 성립합니다. 이는 유명한 체르노프 부등식(Chernoff's bound)입니다.(증명은 [3]을 참조하세요.) 여기에 \(\delta := e - 1\), \(\mu := np\)를 대입하면 원하는 식을 얻게 됩니다. ■

 

다음은 아래 증명에서 나올 특정한 성질을 갖는 확률 변수의 나열(sequence)과 이항 분포의 관계를 규명합니다. 참고로 이 정리는 복잡한 확률 변수의 성질을 잘 알려진 확률 변수의 것과 비교하는 coupling method를 사용하면 쉽게 증명할 수 있다고 합니다. 하지만 개인적으로 증명했다가 완전히 잘못되었음을 알고 지웁니다. 나중에 증명을 성공하면 그때 다시 올리도록 하겠습니다. 

정리 3. 특정 성질의 확률 변수 나열과 이항 분포의 관계

---

임의의 확률 변수 \(X_1, \cdots, X_n\)이 주어지고, 그에 따른 확률 변수 \(Y_t\)(단, \(t = 1, \cdots, n\))가 다음의 성질을 만족한다고 하자.

• \(Y_t\)는 0 아니면 1의 값을 갖는다. 즉, \(Y_i \in \{0, 1\}\)이다.
• \(Y_t\)는 \(X_1, \cdots, X_{t - 1}\)에 의존한다.
• \(Pr \left[ Y_t = 1 | X_1, \cdots, X_{t - 1} \right] \leq p \)를 만족한다.

그러면 \( Pr \left[ \sum_{t = 1}^n Y_i \geq k \right] \leq Pr \left[ B(n, p) \geq k \right] \)를 만족한다.

두 개씩 고르기 증명

이제 본론으로 들어가 보죠. 먼저 증명의 아이디어가 무엇인지 간략히 알아 보도록 하겠습니다. 다만 이 설명은 어디까지나 큰 그림을 그리는 것이기 때문에 세세한 부분은 다를 수 있습니다. 우리의 목표는 그리 크지 않은 \(i^\star\)에 대해 높은 확률로 모든 상자에 담긴 공의 개수가 \(i^\star\)보다 작거나 같음을 보이는 것입니다. 우리 방법이 동작하는 것을 잘 따져 보면, 어떤 공을 어떤 상자에 넣을 때 이번에 높이(즉, 해당 상자에 이미 담겨있는 공의 개수에 1을 더한 값)가 \(i + 1\) 이상이 되기 위해서는 \(i\) 개 이상 담긴 상자 두 개를 선택했어야 합니다.

 

이를 종합해 보면, 공을 \(i\) 개 이상 갖는 상자의 개수가 어떤 역치값 \(\beta_i\)를 높은 확률로 넘지 않도록 \(\beta_i\)를 잘 설정하면 분석에 큰 도움이 된다는 것을 알 수 있습니다. 만약 어떤 \(i\)에 대해 공을 \(i\) 개 이상 갖는 상자의 개수가 현재 \(\beta_i\)를 넘지 않았다면, 이번에 넣은 공의 높이가 \(i + 1\)이 될 확률은 최대 \( \left( \frac{\beta_i}{n} \right)^2 \)이 됩니다. 따라서 \(\beta_{i + 1}\)은 \(\beta_i\)보다 훨씬 작은 숫자로 잡을 수 있을 것입니다. 그렇게 \(\beta\)를 만들면 마지막에 \(\beta_{i^\star} < 1\)이 되는 때에 우리가 원하는 \(i^\star\)가 될 것으로 보입니다.

 

이를 위해 우리 증명에서 유용하게 사용될 것들을 정의하고 가겠습니다.

• \( \mathsf{Height}(t) \) : \(t\) 번째 공의 높이. 여기서 높이는 상자를 스택(stack)처럼 생각한다면, 이번 공이 들어갔을 때 그 공이 해당 스택에서의 높이라고 생각할 수 있습니다.
• \( \mathsf{NumBinLevel}_{\geq i}(t) \) : \(t\) 번째 공을 넣은 후에 공을 \(i\) 개 이상 갖고 있는 상자의 개수. 상황에 따라서는 \( \mathsf{NumBinLevel}_{\geq i} \)를 \( \mathsf{NumBinLevel}_{\geq i}(n) \) 대신 쓸 수 있습니다.
• \( \mathsf{NumBallHeight}_{\geq i}(t) \) : \(t\) 번째 공을 넣은 후에 높이가 \(i\) 이상인 공의 총 개수. 마찬가지로 \( \mathsf{NumBallHegiht}_{\geq i}(n) \) 대신 \( \mathsf{NumBallHeight}_{\geq i} \)로 쓸 수 있습니다.
• \( \mathcal{E}_{\geq i} \) : \( \mathsf{NumBinLevel}_{\geq i}(n) \leq \beta_i \)를 만족하는 사건.
• \(p_i := \left(\frac{\beta_i}{n}\right)^2\). 직관적인 의미는 공이 \(i\) 개 이상 들어있는 상자의 개수가 \(\beta_i\)를 넘지 않을 때 이번에 넣을 공의 높이가 \(i + 1\)이 될 확률의 상한입니다.

남은 것은 \(\beta_i\)를 정하는 일입니다. 이는 \(i \geq 6\)에 대해 다음과 같은 점화식 \[ \beta_i = \left\{ \begin{array}{ll} \frac{n}{2e}, & \text{if } i = 6, \\ \frac{e}{n} \beta_{i - 1}^2, & \text{if } i > 6, \end{array} \right. \]로 정의하겠습니다. 참고로 \(i \leq 5\)인 경우는 상수항으로 충분히 처리할 수 있으므로 고려하지 않습니다.

 

이제부터 최종 증명에 필요한 정리들을 차근히 보이도록 하겠습니다. 첫 번째는 초항 \(\beta_6\)이 적절하게 선택되었다는 점을 보여줍니다.

정리 4. 초항의 확실성

---

사건 \(\mathcal{E}_{\geq 6}\)은 항상 일어난다. 즉, \( \mathsf{NumBinLevel}_{\geq 6} \leq \frac{n}{2e} \)이다.

[증명] 총 \(n\) 개의 상자에서 공을 \(6\) 개 이상 담고 있는 상자의 개수는 비둘기집의 원리(pigeonhole principle)에 의하여 최대 \( \frac{n}{6} \)입니다. \(6 > 2e\)이므로 \( \frac{n}{6} < \frac{n}{2e} \)가 됩니다. ■

 

이번에는 \(\beta_i\)의 값의 상한을 구해보도록 하겠습니다.

정리 5. \(\beta_i\)의 상한

---

임의의 \(i \geq 6\)에 대해, \[ \beta_i = \frac{n e^{2^{i - 6} - 1}}{(2e)^{2^{i - 6}}} \leq \frac{n}{2^{2^{i - 6}}} \]이 성립한다.

[증명] 위에서 부등식은 쉽게 보일 수 있으므로 등식이 성립함을 보이겠습니다. 수학적 귀납법을 쓰겠습니다. 먼저 \(i = 6\)인 경우는 \[ \beta_6 = \frac{n}{2e} = \frac{n e^0}{(2e)^{2^0}} \]이 되므로 성립하게 됩니다. 이보다 큰 경우에는 \[ \beta_{i + 1} = \frac{e}{n} \beta_i^2 \leq \frac{e}{n}  \left( \frac{n e^{2^{i - 6} - 1}}{(2e)^{2^{i - 6}}} \right)^2 = \frac{n e^{2^{i - 5} - 1}}{(2e)^{2^{i - 5}}} \]가 성립하는 것을 보일 수 있습니다. ■

 

다음은 \(\mathcal{E}_{\geq i}\)에서 \( \mathcal{E}_{\geq i + 1} \)을 이끌어낼 때 중요하게 사용되는 정리입니다. 위에서 본 정리 3이 이를 증명하는데 사용됩니다.

정리 6. 공의 높이와 이항 분포의 관계

---

임의의 \(i\)와 임의의 \(k\)에 대하여 \[ Pr [ \mathsf{NumBinLevel}_{\geq i + 1} \geq k | \mathcal{E}_{\geq i} ] \leq Pr[ \mathsf{NumBallHeight}_{\geq i + 1} \geq k | \mathcal{E}_{\geq i} ] \leq \frac{ Pr[B(n, p_i) \geq k]  }{Pr[ \mathcal{E}_{\geq i} ]} \]를 만족한다.

[증명] 첫 번째 부등식은 자명하므로 두 번째 부등식만 보이도록 하겠습니다. 임의의 \(t\)에 대해 \(Y_t\)를 \(t\) 번째 공을 담기 전에 \(i\) 이상의 공을 갖는 상자의 개수가 \(\beta_i\)를 넘지 않지만 \(t\) 번째 공의 높이는 \(i\)보다 큰 상황을 나타내는 변수라고 합시다. 다시 말해, \[ Y_t := \left\{ \begin{array}{ll} 1, & \text{if } \mathsf{NumBinLevel}_{\geq i}(t - 1) \leq \beta_i \text{ and } \mathsf{Height}(t) \geq i + 1, \\ 0, & \text{otherwise, } \end{array}\right. \]로 정의하겠습니다. 지금까지의 공이 들어간 상자를 \(\omega_1, \cdots, \omega_{t - 1}\)로 나타내겠습니다. 모든 \(t\)에 대해 \(Y_t = 1\)이 되기 위해서는 \(t\) 번째 공을 넣을 당시 공을 \(i\) 개 이상 담고 있는 상자를 두 개 뽑아야 합니다. 그때, 공을 \(i\) 개 이상 담고 있는 상자의 개수는 \(\beta_i\)를 넘지 않으므로 \[Pr[Y_t = 1 | \omega_1, \cdots, \omega_{t - 1}] \leq \left( \frac{\beta_i}{n} \right)^2 = p_i \]라는 사실을 알 수 있습니다. 그러면 정리 3에 의해 \[ Pr \left[ \sum_{i = 1}^n Y_t \geq k \right] \leq Pr [B(n, p_i) \geq k] \]를 얻을 수 있습니다.

 

만약 \( \mathcal{E}_{\geq i} \)가 만족한다는 전제 아래에서는 \(\mathsf{NumBinLevel}_{\geq i}(t - 1) \leq \mathsf{NumBinLevel}_{\geq i} \leq \beta_i\)가 되므로 \(t\) 번째 공의 높이가 \(i + 1\) 이상이 되면 반드시 \(Y_t = 1\)이 됩니다. 따라서 같은 전제 하에 \( \mathsf{NumBallHeight}_{\geq i} = \sum_{t = 1}^n Y_t \)가 되며 \[ Pr[\mathsf{NumBallHeight}_{\geq i} \geq k | \mathcal{E}_{\geq i}] = Pr \left[\sum Y_t \geq k | \mathcal{E}_{\geq i}\right] \leq \frac{Pr[\sum Y_t \geq k]}{Pr[\mathcal{E}_{\geq i}]} \leq \frac{Pr[ B(n, p_i) \geq k ]}{Pr[\mathcal{E}_{\geq i}]} \]를 만족하게 됩니다.(첫 번째 부등식은 \( P(A | B) = \frac{P(A \wedge B)}{P(B)} \leq \frac{P(A)}{P(B)} \)를 통해 얻을 수 있습니다.) ■

 

이번에는 만약 \(\beta_i\)가 충분히 큰 경우, 다시 말해 \(i\)가 작은 경우에는 높은 확률로 \(\mathcal{E}_{\geq i}\)가 발생한다는 것을 보여줍니다.

정리 7. 작은 \(i\)에 대한 부등식

---

임의의 \(i\)가 \( n p_i \geq 2 \ln n \)을 만족한다면, \( Pr[\neg \mathcal{E}_{\geq i + 1}] \leq \frac{1}{n^2} + Pr[\neg \mathcal{E}_{\geq i}]\)이다.

[증명] 이를 보이기 위해 \[ \begin{array}{ll} Pr[\neg \mathcal{E}_{\geq i + 1}] & = Pr[\neg \mathcal{E}_{\geq i + 1} | \mathcal{E}_{\geq i}] \times Pr[\mathcal{E}_{\geq i}] + Pr[\neg \mathcal{E}_{\geq i+1}|\neg \mathcal{E}_{\geq i}] \times Pr[\neg \mathcal{E}_{\geq i}] \\ & \leq Pr[\neg \mathcal{E}_{\geq i + 1} | \mathcal{E}_{\geq i}] \times Pr[\mathcal{E}_{\geq i}] + Pr[\neg \mathcal{E}_{\geq i}] \end{array} \]를 이용하겠습니다. 정리 6에다 \(k = \beta_{\geq i + 1}\)을 넣어 적용하면 \[ Pr[\neg \mathcal{E}_{\geq i + 1} | \mathcal{E}_{\geq i}] \leq \frac{Pr[B(n, p_i) \geq \beta_{i + 1}]}{Pr[\mathcal{E}_{\geq i}]}\]를 얻을 수 있습니다. 이때, \(\beta\)와 \(p_i\)의 정의에 의해 \(\beta_{i + 1} = \frac{e}{n} \beta_i^2 = e \cdot np_i \)이기 때문에 정리 2에 의해 \[ Pr[B(n, p_i) \geq e \cdot n p_i ] \leq e^{- n p_i} \leq e^{- 2 \ln n} = \frac{1}{n^2} \]가 됩니다. 여기서 두 번째 부등식은 본 정리의 가정에서 유추할 수 있습니다. 위 식들을 조합하면 정리 7을 이끌어낼 수 있습니다. ■

 

이 정리는 앞에서 보인 정리 4와 함께 \(n p_i \geq 2 \ln n\)을 만족하는 모든 \(i\)에 대해 \[ Pr[\neg \mathcal{E}_{\geq i + 1}] \leq \frac{i + 1}{n^2} \tag{3} \]라는 사실도 말해줍니다.

 

그렇다면 \( n p_i < 2 \ln n \)인 \(i\)는 어떻게 될까요? 그때야말로 끝이 나게 됩니다. 왜냐하면 이 경우에는 높은 확률로 \(i + 2\)보다 높은 높이의 공이 존재하지 않기 때문이죠. 먼저 그러한 조건을 만족하는 \(i\) 중 가장 작은 값을 \(i^\star\)라고 할 때 \(i^\star\)가 그렇게 크지 않다는 것을 보이겠습니다.

정리 8. 공의 최대 높이에 대한 부등식

---

\(n p_i < 2 \ln n\)을 만족하는 가장 작은 정수 \(i^\star\)는 \( \frac{\ln \ln n}{\ln 2} + O(1) \)을 넘지 않는다.

[증명] \(i^\star\)가 가장 작은 정수이므로 \(i^\star - 1\)에 대해서는 \(n p_{i^\star - 1} \geq 2 \ln n\)가 성립하고, 따라서 \( \beta_{i^\star - 1}^2 \geq 2 n \ln n \)이 됩니다. 정리 5에 의해 \[ \beta_{i^\star - 1} \leq \frac{n}{2^{2^{i^\star - 7}}} \Rightarrow \beta_{i^\star - 1}^2 \leq \frac{n^2}{2^{2^{i^\star - 6}}}\]입니다. 이를 조합하면 \( i^\star \leq \frac{\ln \ln n}{\ln 2} + 6\)임을 유도할 수 있습니다. ■

 

마지막으로 앞에서 말했던 대로 \(i^\star + 2\)보다 큰 높이를 갖는 공은 거의 존재하지 않는다는 것을 보이도록 하겠습니다. 이것을 보이면 모든 증명이 완성됩니다.

정리 9. 큰 \(i\)에 대한 부등식

---

\( Pr[ \mathsf{NumBallHeight}_{\geq i^\star + 2} \geq 1 ] \leq \frac{(6 \ln n)^2}{n} + \frac{i^\star + 1}{n^2} \)이다. 이때 우변의 값은 \(n\)의 크기가 커질 수록 \(0\)에 수렴한다.

[증명] 정리 7의 증명과 비슷하게 \(Pr[\mathsf{NumBallHeight}_{\geq i^\star + 2} \geq 1]\)의 값이 아래의 식보다 작거나 같기 때문에 \[ \begin{array}{l} Pr[\mathsf{NumBallHeight_{\geq i^\star + 2}} \geq 1 | \mathsf{NumBinLevel}_{\geq i^\star + 1} \leq 6 \ln n] \times Pr[ \mathsf{NumBinLevel}_{\geq i^\star + 1} \leq 6 \ln n ] \\ + Pr[\mathsf{NumBinLevel}_{\geq i^\star + 1} \geq 6 \ln n] \end{array} \]으로 나누어서 생각하겠습니다. 우변의 첫 번째 항을 \(r_1\), 두 번째 항을 \(r_2\)라고 하였을 때, \(r_1 \leq \frac{(6 \ln n)^2}{n}\)과 \(r_2 \leq \frac{i^\star + 1}{n}\)임을 보이면 증명이 끝납니다.

 

두 번째를 먼저 보이겠습니다. 정리 6에다가 \(k = 6 \ln n\)을 대입하면 \[ Pr[ \mathsf{NumBinLevel}_{\geq i^\star + 1} \geq 6 \ln n | \mathcal{E}_{i^\star} ]  \leq \frac{Pr[B(n, p_{i^\star}) \geq 6 \ln n] }{Pr[\mathcal{E}_{i^\star} ]} \]를 얻을 수 있습니다. \(i^\star\)의 정의에 의하여 \( p_{i^\star} < \frac{2 \ln n}{n} \)이고 \( 6 \ln n > 2e \ln n \)이므로 \[ Pr[ B(n, p_{i^\star}) \geq 6 \ln n ] \leq Pr \left[ B\left(n, \frac{2 \ln n}{n} \right) \geq 2e \ln n \right] \leq \frac{1}{n^2} \]를 유도해낼 수 있습니다. 여기서 마지막 부등식은 위에서 본 것과 마찬가지로 정리 2를 통해 얻을 수 있습니다. \(i^\star - 1\)은 식 3을 만족하므로 이를 조합하면 \[ r_2 \leq Pr[ \mathsf{NumBinLevel}_{\geq i^\star + 1} \geq 6 \ln n | \mathcal{E}_{i^\star}] \times Pr[\mathcal{E}_{i^\star}] + Pr[\neg \mathcal{E}_{i^\star}] \leq \frac{i ^\star + 1}{n^2} \]임을 알 수 있습니다.

 

첫 번째는 직접 계산하여 유도할 수 있습니다. 정리 6의 증명에서 사용된 방식을 알맞게 적용하면 \[ r_1 \leq Pr \left[ B \left( n, \left( \frac{6 \ln n}{n} \right)^2 \right) \geq 1 \right] \leq n \left(\frac{6 \ln n}{n}\right)^2 \]를 얻을 수 있습니다.(따로 보이지는 않겠습니다. 직접 구해 보세요!) 여기서 마지막 부등식은 \(n\) 번의 시행 동안 한 번이라도 성공할 확률은 매 시행마다 성공할 확률을 모두 더한 값보다는 작다는 union bound를 통하면 쉽게 얻을 수 있습니다. ■

마치며

이것으로 상자를 매번 두 개씩 균등하게 골라 더 적은 수의 공이 담긴 상자에 넣는 방법은 높은 확률로 모든 상자의 공의 개수를 \(\frac{\ln \ln n}{\ln 2} + O(1)\)보다 크지 않게 만든다는 사실을 보였습니다. 사실 위에서 보여드린 증명을 확장하면 매번 \(d\) 개씩(단, \(d \geq 2\)) 균등하게 골라 가장 작은 수의 공이 담긴 상자에 넣는 방법은 높은 확률로 최대 개수를 \( \frac{\ln \ln n}{\ln d} + O(1) \)로 만든다는 것을 증명할 수 있습니다. 하지만 하나씩 고르는 것과 두 개씩 고르는 방법의 격차에 비해 그 이상은 정도가 미미하기에 이러한 특징을 power of two choices라고 부릅니다.

 

사실 최근에 글을 너무 많이 적어 좀 쉬려고 했습니다. 한 다섯 개는 몰아 적은 것 같습니다. 제 성격 상 한번 글을 적기 시작하면 끝이 날 때까지 주구장창 적다 보니 더욱 글쓰기를 쉴 필요가 있었습니다. 다른 것도 해야죠. 그런데 이번에 power of two choices 관련 서베이를 읽어 보면서 이것은 한번 정리할 필요가 있겠다고 생각했습니다. 제가 익숙하지 않은 분야일 뿐더러 매우 흥미로운 기법들이 많이 사용됐기 때문입니다. 심지어는 확률론이 꽤 아름답다고 느꼈을 정도입니다. 혹여나 이 글을 읽으시는 분들에게도 도움이 되었으면 합니다.

 

궁금하신 점이나 글에 이상이 있는 경우 알려 주시면 감사하겠습니다. 고맙습니다.

참조

[1] Yossi Azar, Andrei Z. Broder, Anna R. Karlin, and Eli Upfal. Balanced allocations. SIAM journal on computing 29(1):180-200, 1999.

 

[2] Michael Mitzenmacher, Andréa W. Richa, Ramesh Sitaraman. The power of two random choices: A survey of techniques and results. Combinatorial Optimization 9:255-304, 2001.

 

[3] Chernoff bound 증명 : http://math.mit.edu/~goemans/18310S15/chernoff-notes.pdf

주석

[ㄱ] 본문에서 상자를 두 개 뽑는 방법은 균등한 확률(uniformly at random)로 두 번 독립적으로 뽑는 것입니다. 즉, 모든 상자를 각각 \(\frac{1}{n}\)의 확률로 하나 뽑은 후에 앞에서 뽑은 것은 전혀 생각하지 않고 다시 모든 상자를 각각 \(\frac{1}{n}\)의 확률로 뽑는 것이죠. 이렇게 하면 처음에 뽑은 상자와 다음에 뽑은 상자가 동일할 수 있습니다만 이 경우에는 상자에 든 공의 개수가 동일한 것으로 보면 됩니다.