「상자에 공 넣기, 상자를 두 개씩 고르면?」 증명 보충

예전에 상자에 공 넣기 문제(balls-into-bins problem)에서 매번 상자 두 개를 균일한 확률로 골라 공의 개수가 적은 쪽에 넣으면 어떻게 되는지 소개해 드린 적이 있습니다.

2020.03.22 - [알고리즘 & 확률/Balls into bins] - 상자에 공 넣기, 상자를 두 개씩 고르면? (Power of Two Choices)

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

사실 이 글은 완전한 상태가 아닙니다. 한 정리의 증명이 잘못된 것을 나중에 발견하여 그 부분을 통째로 지웠기 때문입니다. 하지만 당시에는 올바른 증명이 무엇인지 몰랐습니다. 참조한 논문에서 해당 부분은 간단하게 증명할 수 있으니 생략하겠다고 적혀 있었기 때문인데요. 그 후, 며칠 동안 고민해 봤지만 혼자서는 증명을 못해서 나중으로 미루게 되었습니다.

 

그렇게 두 해가 지났군요. 증명을 통째로 날린 후 한동안은 마음에 걸렸던 것도 사실이지만, 이런저런 이유로 계속 미루다 보니 어느새 기억의 저편으로 사라졌다는 것을 부정할 수 없겠습니다. 하지만 간간이 사람들이 찾고, 댓글도 달리다 보니 언제부터인가 더 미루면 안 되겠다는 생각이 들었습니다. 게다가 이 년이라는 시간이 지난 지금은 과연 증명할 수 있을지 궁금하기도 했고요.

 

결론적으로는 위 글을 마무리지을 수는 있었습니다. 다만, 지난번에 실패한 정리 3의 증명을 완성한 것은 아닙니다. 대신, 증명에서 정리 3을 활용하는 정리 6을 그것의 도움 없이 증명하는 것에 성공하였습니다. 수정된 증명과 비슷한 방식으로 정리 3도 증명할 수 있을 것 같기는 합니다만, 현재로서는 잘 모르겠습니다. 그럼에도 예전에 실패하고 방치해 둔 글을 드디어 끝낼 수 있어 기쁜 마음입니다.

 

아래 증명의 기호는 모두 이전 포스트의 것을 그대로 사용하니 참고하시기 바랍니다.

---

증명할 정리는 아래와 같습니다.

[이전 글] 정리 6. 공의 높이와 이항 분포의 관계

---

임의의 \(i\)와 임의의 \(k\)에 대하여 \[ Pr[\mathsf{NumBinLevel}_{\geq i+1 } \geq k \mid \mathcal{E}_{\geq i}] \leq Pr[\mathsf{NumBallHeight}_{\geq i+1} \geq k \mid \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\)보다 높을 때 1의 값을 갖는 확률 변수로 정의하였습니다. 즉,

\[ 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. \]로 정의하였습니다. 아래의 정리를 보이면 이전 글의 정리 6의 증명을 모두 완성하게 됩니다.

정리 1. [이전 글] 정리 6 보충

---

위와 같이 정의된 \(\{Y_t\}_{t = 1, \cdots, n}\)에 대해서, \[ Pr \left[ \sum_{i = 1}^n Y_t \geq k \right] \leq Pr[B(n, p_i) \geq k] \]를 만족한다.

[증명] 우리를 도와 줄 새로운 확률 변수 \(Z_t \in \{0, 1\}\)을 정의해 보겠습니다. \(t\) 번째 공을 넣기 전까지의 상황을 임의로 하나 고정했을 때, \(b_{t, i}\)를 그때 실제로 \(i\) 개 이상의 공을 담고 있는 상자의 개수라고 하겠습니다. 만약 \(b_{t, i} > \beta_i\)라면, \(Y_t\)는 정의에 의해 확실히 0의 값을 갖습니다. 이때, \(Z_t\)는 \(p_i\)의 확률로 앞면이 나오는 새로운 동전을 던져서 앞면이 나오면 1, 뒷면이 나오면 0의 값을 갖습니다.

 

반대로 \(b_{t, i} \leq \beta_i\)라고 해 보겠습니다. 이때 \(Y_t\)가 1이 되기 위해서는 이번에 뽑은 상자 두 개가 모두 공을 \(i\) 개 이상 담고 있었어야 합니다. 우리는 매번 독립적으로 두 개의 상자를 균등한 확률로 선택하므로 그 확률 \(q_{t, i}\)는 \[ q_{t, i} := \frac{ \binom{b_{t, i}}{2} }{ \binom{n}{2} } = \frac{b_{t, i} (b_{t, i} - 1 )}{n (n - 1)} \]와 같습니다. 이 경우 \(Z_t\)는 다음과 같이 정해집니다.

• 만약 \(Y_t\)가 1이라면 \(Z_t\)도 1이다.
• 만약 \(Y_t\)가 0이라면, \(\frac{p_i - q_{t, i}}{1 - q_{t, i}}\)의 확률로 앞면이 나오는 새로운 동전을 던져서 앞면이 나오면 1, 뒷면이 나오면 0으로 정한다.

참고로 \(b_{t, i} \leq \beta_i\)라는 전제 덕분에 \[ q_{t, i} = \frac{b_{t, i} (b_{t, i} - 1)}{n (n - 1)} \leq \left( \frac{\beta_i}{n} \right)^2 =: p_i \]임을 쉽게 유도할 수 있으며, 따라서 위 \(Z_t\)의 정의가 실현 가능하다는 것을 보일 수 있습니다.

 

몇 가지 흥미로운 사실들을 확인해 보겠습니다. 첫 번째는 매번 상자를 어떻게 선택하고 공을 어느 상자에 넣든 \(Z_t\)의 정의에 의해 \(Y_t \leq Z_t\)를 만족한다는 것입니다. 따라서, \[ \sum_{t = 1}^n Y_t \leq \sum_{t = 1}^n Z_t \tag{1}\]도 성립합니다.

 

두 번째는 매번 상자를 어떻게 선택하고 공을 어느 상자에 넣든지 간에 \(Z_t\)는 항상 \(p_i\)의 확률로 1의 값을 갖는다는 것입니다. \(b_{t, i} > \beta_i\)인 경우는 정의에 의해 자명하게 성립합니다. 반대의 경우에는 \[ q_{t, i} + (1 - q_{t, i} ) \cdot \frac{p_i - q_{t, i}}{1 - q_{t, i}} = p_i\]가 됨을 알 수 있습니다. 좌변을 좀더 설명하겠습니다. \(q_{t, i}\)는 \(Y_t\)가 1을 가질 확률이며, 정의에 따라 이때는 \(Z_t\)도 1을 갖습니다. 반면, \(Y_t\)는 \(1 - q_{t, i}\)의 확률로 0이 되는데, 그러면 정의에 따라 \( \frac{p_i - q_{t, i}}{1 - q_{t, i}} \)의 확률로 \(Z_t\)가 1이 됩니다. 따라서 위 식이 성립하게 됩니다.

 

마지막으로 \(\{Z_t\}_{t = 1, \cdots, n}\)은 서로 독립이라는 점입니다. 각 \(Z_t\)는 \(Y_t\) 혹은 매번 새로 정의되는 동전의 던짐 결과에 따라 결정됩니다. 이때, 각 \(Y_t\)도 결국은 매번 독립적으로 두 개의 상자를 골랐을 때 얻게 되는 결과입니다. 따라서 각 \(Z_t\)에 영향을 주는 요인들은 다른 \(Z_{t'}\)에는 영향을 주지 않으므로 독립입니다.

 

앞에서 우리는 \(Z_t\)가 \(p_i\)의 확률로 1을 갖는다고 하였습니다. 그런데 그것들이 서로 독립이라는 사실도 알게 되었습니다. 따라서, \( \sum_{t = 1}^n Z_t \)는 곧 \(p_i\)의 확률로 앞면이 나오는 동전을 \(n\) 번 독립적으로 던졌을 때의 앞면이 나온 총 횟수와 동일합니다. 다시 말해, \[ \sum_{t = 1}^n Z_t = B(n, p_i)\]라고 쓸 수 있습니다. 이를 식 1과 결합하면 정리의 명제를 보일 수 있습니다. ■

---

정리 1의 증명을 곧장 하기 어려웠던 이유는 \( \{Y_t\}_{t = 1, \cdots, n} \)가 1이 될 확률이 매우 복잡하게 결정되었기 때문입니다. 이전까지 공이 어떻게 들어갔는지를 고정하지 않고서는 \(Y_t\)가 1이 될 확률을 정확히 계산하기 어렵습니다. 이를 회피하기 위해 \(Z_t\)라는 새로운 확률 변수를 도입했습니다. 이 변수는 식 1과 같이 \(Y_t\)와 매우 밀접한 관계를 가지지만, 내부 동작을 무시한 채 바라보면 그냥 매번 \(p_i\)의 확률로 앞면이 나오는 독립된 동전을 던지는 것과 다름없었습니다. 이를 통해 \(\{Y_t\}_{t = 1, \cdots, n}\)를 잘 연구된 이항 분포와 비교할 수 있었습니다.

 

이렇게 복잡한 확률 변수를 잘 정의된 새로운 확률 변수와 엮고, 결과적으로 새로운 확률 변수가 잘 알려진 확률 변수와 다르지 않음을 보임으로써 복잡한 확률 변수에 관한 흥미로운 성질들을 이끌어 내는 기법을 커플링 기법(coupling method)이라고 부릅니다. 저번 포스트에서는 이 기법에 대한 이해가 부족하여 증명을 올바르게 쓰지 못하였습니다. 그래도 두 해가 지난 지금, 이 기법을 이해하고 보충 글을 적을 수 있어서 만족스럽습니다. 그동안 놀아 재끼지만은 않은 것 같아 괜히 으쓱해지기도 합니다.

 

읽어 주셔서 고맙습니다.