다음과 같은 상황을 생각해 보죠. 여러분의 눈 앞에는 \(n\) 개의 상자가 있고 옆에는 \(n\) 개의 공이 있습니다. 여러분은 공을 상자에 넣어야 합니다. 항상 특별한 일상을 원하는 여러분은 좀 독특한 방식으로 공을 상자에 담아 보고자 합니다. 바로 공 하나를 넣을 때 상자를 균등한 확률(uniformly at random)로 선정하여 거기에 담는 것이죠. 과연 이런 방식으로 넣었을 때 상자에 담긴 공의 개수 중 가장 큰 값은 무엇일까요?
최악의 경우에는 당연히 \(n\)이 됩니다. 상자 하나에 모두 담기는 것이죠. 하지만 이런 경우가 많이 일어날까요? 각각의 공이 각 상자에 담길 확률이 \( \frac{1}{n} \)이고 이전에 공을 어떻게 넣었느냐가 이번에 넣을 공을 어떻게 넣을지 영향을 주지 않으므로(즉, 독립 시행이므로) 특정 상자 하나에 공이 모두 담길 확률은 \( \frac{1}{n^n} \)이 됩니다. 상자의 총 개수는 \(n\)이기 때문에 어떤 상자에 공이 \(n\) 개 들어갈 확률은 \( \frac{1}{n^{n - 1}} \)이 됩니다. 이 확률을 보자니 아무래도 상자 하나에 모두 담기는 일은 영 일어날 법하지 않아 보이는 군요.
반대로 최선의 경우는 상자 하나에 공이 하나씩 들어가는 것이므로 \(1\)입니다. 이것의 확률은 어떨까요? 만약 공을 넣은 순서대로 공이 몇 번째 상자에 들어갔는지를 매겨보면, 모든 상자에 공이 하나씩 들어간 경우에는 그 수열은 \(1, \cdots ,n\)의 순열(permutation)이 됩니다. 예를 들어, \(n = 3\)일 때, 1 번 공은 2 번 상자에, 2 번 공은 1 번 상자에, 3 번 공은 3 번 상자에 들어가면 이것을 \( (2, 1, 3) \)으로 나타낼 수 있고 이 수열은 \(1, 2, 3\)의 순열이 됩니다. 모든 순열의 개수는 \(n!\)이고 각각이 일어날 확률은 \(\frac{1}{n^n}\)이므로 상자에 공이 정확히 하나씩 들어갈 확률은 \( \frac{n!}{n^n} \)이 됩니다. 물론 최악의 경우보다는 낫겠지만, 이 확률도 \[ \frac{n!}{n^n} \approx \frac{\sqrt{2 \pi n}}{e^n} \]이 되어 그다지 가망이 있어보이지는 않습니다.(이 식의 유도는 아래 스털링 근사(Striling's approximation)를 참조하세요.)
그러면 그 값은 높은 확률로 얼마 정도가 될까요? 이것이 이번 포스트에서 함께 공부해 볼 내용입니다.
정리 1. 상자에 담긴 공의 최대 개수
충분히 큰 \(n\)에 대해 \(n\) 개의 공과 \(n\) 개의 상자가 주어질 때, 각각의 공을 균등한 확률로 상자를 골라 그 상자에 넣었다고 하자. 그러면 최소한 \( 1 - \frac{1}{n} \)의 확률로 상자에 담긴 공의 최대 개수는 \( \frac{3 \ln n}{ \ln \ln n } \)이 된다.
들어가기에 앞서서 왜 이런 문제를 고민하는 것인지 의아해 하실 분들이 계실 것 같습니다. 저 또한 그랬거든요. 굳이 상자에 공을 "확률적"으로 넣어야 한다는 것이 실생활에서 어떤 쓸모가 있는 것인지 처음에는 영 이해가 되지 않았습니다.
하지만 놀랍게도 이 문제는 컴퓨터과학에서 꽤 중추적인 역할을 담당하고 있습니다. 가장 유명한 예시는 바로 해싱(hashing)입니다. 학부 자료구조 시간에 모두 공부하셨으리라 생각합니다만 간략히 설명하자면, 어떤 자료 \(x\)를 저장하기 위해 특정한 해시 함수(hash function) \(h\)를 만들고 그 자료를 해시 테이블의 \(h(x)\) 인덱스에 저장하는 기법을 말합니다. 이러면 해시 함수를 한 번 계산하는 것으로 \(x\)가 어디에 저장되어있는지 바로 찾아낼 수 있습니다.
문제는 두 자료가 동일한 해시값을 갖는 경우입니다. 이를 해결하는 방법 중 하나는 각 해시값마다 연결 리스트(linked list)를 구성하여 충돌(collision)이 발생한 경우 해당 연결 리스트에 저장하는 것입니다. 이는 해시 테이블의 성능에 직접적인 영향을 끼치게 됩니다. 만약 어떤 자료가 길이가 긴 연결 리스트에 저장되어 있다면, 그 자료를 찾기 위해서 해당 리스트를 처음부터 끝까지 모두 훑어봐야 할 수도 있기 때문입니다.
따라서 해시 테이블의 성능을 평가하는 척도 중에 해시 함수가 얼마큼 자료를 잘 흩뜨려 놓는지가 있습니다. 만약 해시 테이블의 크기가 \(n\)일 때 임의의 자료를 \(\frac{1}{n}\)의 확률로 각 엔트리에 넣는 해시 함수가 있다면, 이 함수는 꽤 괜찮은 성능을 가질 것으로 보입니다. 과연 이 해시 함수를 갖는 해시 테이블에는 가장 긴 연결 리스트의 길이는 어떻게 될까요? 이 질문은 여기서 우리가 고민하고자 하는 내용과 매우 흡사하다는 사실을 쉽게 유추할 수 있을 것입니다.
배경 지식
먼저 이번 포스트에서 요긴하게 사용될 사실들을 정리해 보죠. 첫 번째는 순열의 개수인 \(n!\)의 근사치입니다.
정리 2. 스털링 근사(Stirling's approximation)
충분히 큰 \(n\)에 대해 \[ n! \approx \sqrt{2 \pi n} \left( \frac{n}{e} \right)^n \]가 성립한다. 좀더 정확히는 모든 양의 정수 \(n\)에 대해 \[ \sqrt{2 \pi} \cdot n^{n + \frac{1}{2}} \cdot e^{-n} \leq n! \leq e \cdot n^{n + \frac{1}{2}} \cdot e^{-n} \tag{1} \]이 성립한다.
증명은 생략합니다.(저도 모릅니다. 허허.) 인터넷에 이와 관련된 내용을 많이 있으니 궁금하시면 참조해 보시는 것을 추천드립니다. 이를 활용하여 \(n\) 개 중에 \( k \) 개를 뽑는 것의 개수인 \( n \choose k \)에 대해서도 유용한 부등식을 얻을 수 있습니다.
정리 3. 조합(combination)에 대한 부등식
임의의 양의 정수 \(n\)에 대하여 \[ {n \choose k} \leq \left( \frac{en}{k} \right)^k \]가 성립한다.
[증명] 먼저 \( \frac{n!}{(n-k)!} \)에 대해서, \[ \frac{n!}{(n-k)!} = n \times (n - 1) \times \cdots \times (n - k + 1) \leq n^k\]를 얻을 수 있습니다. 따라서 \[ {n \choose k} = \frac{n!}{k! (n-k)!} \leq \frac{n^k}{k!} \leq \frac{n^k}{\sqrt{2 \pi} k^{k + \frac{1}{2}} e^{-k}} \leq \left( \frac{en}{k} \right)^k \]가 성립하게 됩니다. 여기서 두 번째 부등식은 식 1에서 유도할 수 있습니다. ■
다음은 여러 사건의 확률에 관한 내용입니다.
정리 4. Union bound
어떤 사건들 \( \mathcal{E}_1, \cdots, \mathcal{E}_k \)에 대해 이 사건들 중 하나라도 일어날 확률은 각각의 사건이 일어날 확률의 합보다 작거나 같다. 즉, \[ Pr \left[ \bigvee_{i = 1}^k \mathcal{E}_i \right] \leq \sum_{i = 1}^k Pr \left[ \mathcal{E}_i \right] \]가 성립한다.
이 정리는 union bound 혹은 Boole's inequality 등으로 불리기는 합니다만 어찌 보면 너무 당연한 얘기를 하고 있습니다. 하지만 확률을 통해 무언가를 보이고자 할 때 매우 많이 사용되는 식입니다. 증명은 생략하도록 하겠습니다.
상자에 담긴 공 개수의 최댓값
이제 본론으로 들어가 보도록 하겠습니다. 혼란을 방지하기 위해서 \(n\) 개의 상자에 \(1\)부터 \(n\)까지 이름을 붙여주도록 하겠습니다. 우리의 목표는 모든 상자가 어떤 값 \(k\) 개보다 적은 수의 공을 담고 있는 확률을 구하는 것입니다. 다시 말해 \(k\) 개 이상의 공을 담고 있는 상자 \(i\)가 존재하는 사건의 여사건에 대한 확률을 구하는 것과 마찬가지죠. 따라서 임의의 상자 \(i\)가 \(k\) 개 이상의 공을 담고 있을 확률에 대해 의미 있는 부등식을 얻는다면 우리가 원하는 식에 한 걸음 다가갈 수 있을 것입니다. 간단히 쓰기 위해서 이제부터 상자 \(i\)가 \(k\) 개 이상의 공을 담고 있을 확률을 \(\mathcal{E}_i\)라고 부르겠습니다.
정리 5. 어떤 상자에 공이 많이 담길 확률
임의의 상자 \(i\)에 공이 \(k\) 개 이상 담길 확률은 \( \left( \frac{e}{k} \right)^k \)를 넘지 않는다.
[증명] 공의 집합을 \( B \)라고 하겠습니다. 또, 크기가 정확히 \(k\)인 \(B\)의 부분집합 \(S \subseteq B\)에 대하여, \(S\)의 모든 공이 상자 \(i\)에 담기는 사건을 \( \mathcal{F}_S \)라고 부르겠습니다. 이를 정의한 이유는 상자 \(i\)에 공이 \(k\) 개 이상 담겼다면 분명 상자 \(i\)에 몽땅 담긴 크기가 \(k\)인 어떤 부분집합이 존재하기 때문입니다. 즉 이를 다시 쓰면 \[ Pr \left[ \mathcal{E}_i \right] \leq Pr \left[ \bigvee_{S \subseteq B : |S| = k} \mathcal{F}_S \right] \]가 됩니다. 이때 임의의 \(S \subseteq B, |S| = k\)에 대해 \( Pr \left[ \mathcal{F}_S \right] = \left( \frac{1}{n} \right)^k \)이고, 크기가 정확히 \(k\)인 \(B\)의 부분집합의 개수는 \(n \choose k\)이므로 \[ Pr \left[ \bigvee_{S \subseteq B : |S| = k} \mathcal{F}_S \right] \leq {n \choose k} \left( \frac{1}{n} \right)^k \leq \left( \frac{e}{k} \right)^k \]를 만족하게 됩니다. 이때 첫 번째 부등식은 정리 4에 의해, 두 번째는 정리 3에 의해 쉽게 유도할 수 있습니다. ■
따라서 만약 \( \left( \frac{e}{k} \right)^k \approx \frac{1}{n^2} \)를 만족하는 \(k\)를 구한다면 우리는 높은 확률로 모든 상자에 \(k\)보다 적은 개수의 공이 들어간다는 것을 보일 수 있게 됩니다. 그 이유를 간략히 말씀드리면, 임의의 상자 \(i\)에 \(k\)보다 많거나 같은 개수가 들어있을 확률이 \( \left( \frac{e}{k} \right)^k \approx \frac{1}{n^2} \)를 넘지 못하고, 상자의 개수가 \(n\) 개이므로 그러한 상자가 존재할 확률이 union bound(정리 4)에 의해 \( \frac{1}{n} \)을 넘지 못하기 때문입니다. 이를 만족하는 \(k\)는 바로 다음과 같습니다.
정리 6. 정리 1의 증명
충분히 큰 \(n\)에 대해 최소 \(1 - \frac{1}{n}\)의 확률로 모든 상자에는 \( \frac{3 \ln n}{\ln \ln n} \)보다 적은 개수의 공이 들어간다.
[증명] 위에서 설명한 대로, \(k := \frac{3 \ln n}{\ln \ln n}\)으로 잡겠습니다. 정리 5에 의해, 임의의 상자 \(i\)에 대해 \[ Pr \left[ \mathcal{E}_i \right] \leq \left( \frac{e}{k} \right)^k = e^{k \ln \left( \frac{e}{k} \right)} = e^{k \ln \left( \frac{e \ln \ln n}{ 3 \ln n} \right) } \]을 얻을 수 있습니다.(첫 번째 등식은 \(x = e^{\ln x}\)를 통해 얻을 수 있습니다.) 이때, \(e \approx 2.719 < 3\)이므로 \[ e^{k \ln \left( \frac{e \ln \ln n}{3 \ln n} \right)} < e^{k \ln \left( \frac{\ln \ln n}{\ln n} \right)} = e^{k \left( \ln \ln \ln n - \ln \ln n \right)} = e^{\left( -3 \ln n + \frac{3 \ln n \cdot \ln \ln \ln n}{\ln \ln n} \right)} \]을 이끌어낼 수 있습니다. 그러면 \( \frac{3 \ln \ln \ln n}{\ln \ln n} \leq 1\)을 만족하는 "충분히" 큰 \(n\)에 대해서 \[ Pr \left[ \mathcal{E}_i \right] \leq e^{-2 \ln n} = \frac{1}{n^2} \]임을 얻을 수 있습니다. 따라서 그러한 상자가 하나라도 존재할 확률은 정리 4에 의해 \(n \times \frac{1}{n^2} = \frac{1}{n}\)을 넘을 수 없습니다. 따라서 모든 상자에 \(k\) 개보다 적은 공이 들어갈 확률은 \(1 - \frac{1}{n}\)보다 크거나 같습니다. ■
마치며
이번 시간에는 \(n\) 개의 상자에 \(n\) 개의 공을 매번 균등하게 뽑힌 상자에 넣었을 때 상자에 들어간 공의 최대 개수를 구해 보았습니다. 최악의 경우는 상자 하나에 모든 공이 몰리는 것이고, 최선의 경우는 모든 상자에 한 개씩 들어가는 것이지만 각각이 일어날 확률은 그렇게 크지 않았습니다. 대신 높은 확률로 모든 상자에 \( \frac{3\ln n}{\ln \ln n} \) 개의 공이 들어갈 수 있음을 보였습니다. 근데 직접 \( \frac{3 \ln \ln \ln n}{\ln \ln n} \leq 1\)을 \(n\)에 대해 정리해 보니 한 \(n \geq e^{e^{4.536}}\) 정도 되는데 이 값은 \(3.365 \times 10^{40} \) 정도 입니다. 음, 그렇게 실용적인 수치는 아닌 것으로 보이네요. 참고로 좀더 엄밀한 분석을 통해 \(\frac{\ln n}{\ln \ln n}\) 정도 까지 줄일 수 있다고 합니다. 다만 여기에 대해서 제대로 찾아 보지는 않았습니다.
한 가지 더 생각해 봅시다. 만약에 매번 공을 넣을 때 한 개의 상자만 균등하게 고르는 것이 아니라, 두 개의 상자를 균등하게 고르고 둘 중 더 적은 공이 들어간 상자에 공을 넣는다면 어떻게 될까요?(단, 같은 경우에는 아무데나 넣습니다.) 놀랍게도 이번에는 높은 확률로 모든 상자에 \( \frac{\ln \ln n}{\ln 2} \) 정도의 개수가 들어가게 됩니다. \( \frac{\ln n}{ \ln \ln n} \)도 그렇게 큰 수치는 아니지만, \( \frac{\ln \ln n}{\ln 2} \)에는 비할 바가 못 됩니다. 이를 power of two choices라고 부릅니다. 다음번에는 이에 대해 알아보도록 하겠습니다.
궁금하신 점이나 글 내용에 틀린 점이 있으면 알려주시기 바랍니다. 고맙습니다. :)
참조 자료
[1] 전반적 증명 과정 : http://pages.cs.wisc.edu/~shuchi/courses/787-F09/scribe-notes/lec7.pdf
[2] 스털링 근사 정의 : https://en.wikipedia.org/wiki/Stirling%27s_approximation
[3] 정리 3 증명 : https://math.stackexchange.com/questions/132625/inequality-n-choose-k-leq-left-fracen-k-rightk
'알고리즘 & 확률 > Balls into bins' 카테고리의 다른 글
| 「상자에 공 넣기, 상자를 두 개씩 고르면?」 증명 보충 (0) | 2022.06.06 |
|---|---|
| 상자에 공 넣기, 상자를 두 개씩 고르면? (Power of Two Choices) (8) | 2020.03.22 |
