포켓몬 빵을 기억하시나요? 지금도 파는지는 잘 모르겠습니다만, 제가 어릴 적만 하더라도 큰 인기가 있던 빵이었습니다. 특히 그 빵이 인기가 있던 이유는 빵을 사면 그 안에 동봉되어 있던 포켓몬 "띠부띠부 씰" 때문이었다고 생각합니다. 대개는 플라스틱 책받침에 씰을 모았고, 개중에서 모으는 데 진심인 친구들은 클리어 파일에다가 씰을 붙여서 모았죠. 저도 책받침에다가 몇 개 모았던 기억이 있습니다.
씰을 모으던 아이들의 목표는 당연히 모든 씰을 모으는 것이었을 겁니다. 당시 포켓몬은 255마리였던 것으로 기억합니다. 여기서 한 가지 의문점이 생기죠. 과연 아이들은 몇 개의 빵을 사 먹어야 모든 포켓몬 씰을 모을 수 있었을까요? 정말로 운이 좋은 경우라면 사는 족족 다른 포켓몬이 나와서 255개면 충분합니다. 하지만 그럴 가능성은 매우 희박하겠죠. 반대로 정말로 운이 없다면 10,000개를 사도 모두 못 모을 수도 있습니다. 그러나 그 상황도 그렇게 높은 확률로 일어날 것 같지는 않습니다. 그렇다면 과연 몇 개의 빵을 사면 모든 포켓몬 띠부띠부 씰을 모을 것으로 기대할 수 있을까요?
이번 시간의 주제인 쿠폰 수집가 문제(coupon collector problem)는 위 질문에 적절한 해답을 제시하여 줍니다. 결론부터 말씀드리자면 \(n\)개 종류의 포켓몬 씰이 빵에 균등한 확률(uniformly at random)로 독립적(independently)으로 들어가 있다면, 모든 포켓몬 씰을 모을 때까지 사야하는 빵 개수의 기댓값은 \( n \ln n \)이 됩니다. 따라서 이 환경에서는 1414개 정도의 빵을 사면 255개의 포켓몬 씰을 모두 모을 것으로 기대할 수 있겠습니다. 당시에 빵 가격이 500원 정도였을테니, 어언 70만원 정도가 되겠군요. 어린 아이에게는 큰 돈이 아닐 수 없군요.
각설하고, 쿠폰 수집가 문제를 다시 한 번 정의해 보도록 하죠. 우리는 \(n\)개의 서로 다른 종류의 쿠폰을 모두 모아야 합니다. 쿠폰은 제품에 균등한 확률로 하나씩 들어가 있고 각 제품끼리도 독립적입니다. 문제의 목표는 우리가 모든 쿠폰을 모을 때까지 사는 제품의 개수의 기댓값은 구하는 것입니다.
처음 제품을 사면 무엇이 될지는 모르겠지만 일단 쿠폰 하나를 얻게 됩니다. 이제, 두 번째 제품에는 어떤 쿠폰이 들어있을지 생각해 봅시다. 쿠폰은 모든 제품에 균등한 확률로 하나씩 들어갔으므로 분명 \(\frac{1}{n}\)의 확률로 미리 뽑은 쿠폰과 같은 쿠폰이 나올 것이고, 나머지 \( \frac{n-1}{n} \)의 확률로 새로운 쿠폰을 얻을 것입니다.
이 논의를 좀 더 확장해 보죠. 만약 우리가 여태까지 \(i\) 종류의 쿠폰을 모았다고 하겠습니다. 그러면 다음 제품에서 새로운 종류의 쿠폰이 나올 확률은 얼마가 될까요? 바로 \( \frac{n-i}{n} \)일 것입니다. 따라서 \( X_i \)를 \(i\) 종류의 쿠폰을 갖고 있는 중에 새로운 쿠폰을 뽑을 때까지 구매한 제품의 개수라고 한다면, 우리의 목표는
\[ \mathbb{E} [ X_0 + X_1 + \cdots + X_{n - 1} ] = \mathbb{E}[X_0] + \mathbb{E}[X_1] + \cdots + \mathbb{E}[X_{n - 1}] \tag{1} \]
로 표현이 됩니다. 여기서 등식은 기댓값의 선형성(linearity of expectation)을 통해서 유도할 수 있습니다. 이를 통해 알 수 있는 사실은 각 상황에서의 기댓값을 따로 구한 다음에 이를 모두 더하는 것으로 원하는 값을 구할 수 있다는 것이죠.
각 상황은 다음과 같은 상황으로 표현할 수 있습니다. 우리에게 앞면이 \(p\)의 확률로 나오고 뒷면은 \(q := 1 - p\)의 확률로 나오는 편향된(biased) 동전이 있다고 합시다. 이 동전을 던져서 앞면이 나오면 던지는 것을 멈추고, 반대로 뒷면이 나오면 한 번 더 던지는 작업을 한다고 하겠습니다. 과연 몇 번 던져야 앞면이 나와서 작업을 멈출까요? 먼저 이 질문이 위 상황을 잘 표현하고 있다는 것을 먼저 확인하시기 바랍니다. \(X_i\)는 곧 \( p := \frac{n - i}{n} \)인 동전을 앞면이 나올 때까지 던진 횟수와 동일하기 때문이죠.
자, 그러면 과연 던지는 횟수의 기댓값은 어떻게 될까요? 첫 번째 던졌을 때 앞면이 나올 확률은 \(p\)입니다. 두 번째에 나올 확률은 어떨까요? 먼저 첫 번째에 뒷면이 나와야 하고 다음 앞면이 나와야 하므로 확률은 \(qp\)가 되겠습니다. 세 번째에 나올 확률은 첫 번째와 두 번째에 뒷면이 나오고 다음에 앞면이 나오는 상황이므로 \(q^2p\)의 확률을 갖습니다. 여기서 패턴을 찾으면 \(t\) 번째에 앞면이 나오는 확률은 \( q^{t - 1}p \)가 된다는 것을 알 수 있고, 따라서 던지는 횟수의 기댓값은
\[ S := \sum_{t = 1}^\infty q^{t - 1}p \cdot t \]
가 됩니다. 이 멱급수를 풀어주도록 하죠. 양변에 \(q\)를 먼저 곱하면
\[ qS = \sum_{t = 1}^\infty q^t p \cdot t \]
가 되고, 위에서 아래를 빼면 다음을 얻게 됩니다.
\[ (1 - q)S = \sum_{t = 1}^\infty q^{t -1}p = \frac{p}{1-q} = 1\]
이때 두 번째 등식은 무한급수를 구한 것이고 마지막 등식은 \( q = 1 - p \)에서 얻을 수 있습니다. 따라서 앞면이 나올 때까지 던진 횟수의 기댓값 \( S = \frac{1}{p} \)가 됩니다. 참고로 이때 동전을 던지는 횟수가 만족하는 확률 분포가 바로 기하 분포(geometric distribution)입니다.
이제 우리의 목표인 식 1을 구할 수 있습니다. 앞에서 각 \(X_i\)는 \(p := \frac{n - i}{n}\)인 동전을 앞면이 나올 때까지 던진 횟수와 동일하다고 했습니다. 그리고 그 기댓값은 \( \frac{1}{p} = \frac{n}{n - i} \)입니다. 따라서,
\[ \sum_{i = 0}^{n - 1} \mathbb{E}[X_i] = \sum_{i = 0}^{n - 1} \frac{n}{n - i} = n \cdot \left[ \frac{1}{n} + \frac{1}{n - 1} + \cdots + \frac{1}{1} \right] = n H_n \]
임을 알 수 있습니다. 여기서 \(H_n\)은 \(n\)번째 조화수(harmonic number)이며, \( H_n \approx \ln n \)이라는 것은 잘 알려진 사실입니다. 이를 통해 \(n\)개의 쿠폰을 모두 모으기 위해서 사야하는 제품 개수의 기댓값은 \( n \ln n \)임을 증명하였습니다.
이것으로 쿠폰 수집가 문제에 대해서 알아 보았습니다. 이 문제는 그 자체로 확률론에서 중요한 문제이기도 하지만, 특정한 알고리즘의 성능을 분석하는 데 요긴하게 사용되기도 합니다. 사실 이 내용을 정리한 이유도 이 문제에서 사용된 기법이 특정한 상황 아래서 안정 매칭(stable matching)을 구하는 알고리즘의 수행 시간을 개선하는데 쓰이기 때문입니다. 다음에는 이에 대해서 알아 보도록 하겠습니다.
글에 잘못된 내용이 있거나 궁금하신 점이 있으시면 언제든 알려주시기 바랍니다. 고맙습니다. :)