159종의 띠부띠부씰을 다 모으려면 포켓몬빵 몇 개를 사야 할까? 쿠폰 콜렉터 문제

포켓몬 띠부띠부씰이 유행이라고 합니다. 뉴스에서도 소식이 나오던데, 그렇다면 끝물인것 같기도하고... 어쨌든 1,500원짜리 빵에 하나 씩 들어있는 띠부띠부씰을 모두 모우기 위해서 여러 가게를 돌아다니는 사람들이 많다고 합니다. 이번 포스팅에서는 159종의 띠부띠부씰를 다 모우기 위해서는 몇 개의 포켓몬 빵을 사야하는지를 알아 보도록 하겠습니다. (이 문제는 쿠폰 콜렉터 문제 coupon collector's problem으로 확률과 통계 분야에서 유명한 문제입니다)

 

실제로는 모든 캐릭터가 나올 확률이 $\frac{1}{159}$로 동등한 것이 아니라, 잘 안오는 캐릭터는 잘 안나온다고 하는데, 각 캐릭터별 확률을 알 수 없기 때문에 공정하게 $\frac{1}{159}$ 이라고 가정하겠습니다. 

 

문제를 풀어 보도록 하겠습니다. 씰의 총 갯수를 $N$으로 두겠습니다. 당연히 $N = 159$ 입니다.

 

첫 번째 빵을 까도록 하겠습니다. 첫 번째 빵을 까기 전에 우리가 갖고 있던 씰은 하나도 없기 때문에, 첫 번째 빵에서 나오는 씰은 무조건 새로운 씰이 됩니다. 

 

두 번째 방을 까도록 하겠습니다. 두 번째 빵에서 나온 씰이 우리가 갖고 있는 씰과 서로 다를 확률은 $p = \frac{N-1}{N} = \frac{158}{159}$ 입니다. 이미 하나의 씰을 갖고 있으니, 159개의 씰 중에서 새로운 씰은 158개가 남아 있기에 확률은 $\frac{158}{159}$ 가 되는 것 입니다. $p$의 확률로 일어나는 이벤트가 일어나기 위해서는 평균적으로 $\frac{1}{p}$ 번의 시행을 반복해야 합니다. 이것은 단순한 기하 분포의 결론인데, 간단한 것이라 설명은 생략합니다. 따라서 평균적으로 $\frac{159}{158}$ 개의 빵을 까야 새로운 씰을 얻을 수 있습니다. 아직 남아 있는 씰이 158개나 되기 때문에, 두 번째 빵에서는 대부분의 경우 첫 번째 빵에서와는 다른 씰이 나올 것 입니다. 

 

세 번째 빵을 까도록 하겠습니다. 아니 정확히는 두개의 서로 다른 쿠폰을 확보한 이후에 까는 빵입니다. 새롭게 깐 빵에서 지금까지 확보한 씰과 서로 다른 씰이 나올 확률은 $p = \frac{N-2}{N} = \frac{157}{159}$ 입니다. 그리고 평균적으로 $\frac{159}{157}$ 개의 빵을 깠을 때, 처음 두개와는 다른 씰이 나오게 됩니다.

 

위 과정을 계속 반복 하면 됩니다. 

 

만일 150개의 서로 다른 씰을 확보한 경우, 이와는 다른 씰이 나올 확률은 $\frac{9}{159} = 5.6%$ 로 매우 낮습니다. 이 경우에는 대략 18개의 빵을 까야 이전 150개와는 다른 씰을 얻을 수 있습니다. 당연히 확보한 씰이 많으면 많을 수록 새로운 씰을 얻기가 어려운 법 입니다. 

 

위 과정을 수학적으로 표현하면, 

$$T = \frac{159}{159} + \frac{159}{158} + \frac{159}{157} + ... \frac{159}{2} + \frac{159}{1} = 898$$

즉, 평균적으로 봤을 때 898개의 빵을 사야 159종의 씰을 모두 모울 수 있습니다. 물론 운이 좋다면 800개 정도만 샀을 때, 159개를 모두 모울 수 있을 것이고, 반대로 운이 나쁘다면 1,000개 쯤 사야 159개를 모두 모울 수 있을 것 입니다. 

 

일반적으로 총 $N$개의 서로 다른 쿠폰이 있는 경우, $N$개의 쿠폰을 모두 모우기 위해 시행해야 하는 시행횟수의 기대값은

$$T = \frac{N}{N} + \frac{N}{N-1} + \frac{N}{N-2} + ... \frac{N}{2} + \frac{N}{1}$$

$$=N\Big(\frac{1}{1} + \frac{1}{2} + \frac{1}{3} + ... \frac{1}{N-1} + \frac{1}{N} \Big)$$

와 같습니다. 여기서 $H_N = \Big(\frac{1}{1} + \frac{1}{2} + \frac{1}{3} + ... \frac{1}{N-1} + \frac{1}{N} \Big)$은 조화수로 $N$이 매우 클 때, 대략 $\log N + \gamma$의 값을 갖게 됩니다. 여기서 $\gamma = 0.577$로 오일러-마스케로니 상수입니다. 로그 함수의 적분값과 $\sum_{n=1}^{\infty}\frac{1}{n}$의 차이를 의미합니다. 

 

898개를 산다면 159종의 씰을 다 모울 수 있다고 했는데, 정말 그럴까요? 898이라는 숫자는 단순히 기대값이기 때문에, 898개이 빵을 산다고 해서 159종을 다 모울 수 있는 것은 아닙니다. 그래서 이번에는 반대로 $T$개의 빵을 샀을 때, 평균적으로 확보할 수 있는 서로 다른 종류의 씰의 갯수를 구해보도록 하겠습니다. 이 값은 앞에서 구한 $T$와 $N$의 함수의 역함수 인데, 서로 다른 $T$에 대해서 그 값을 구하면 결과는 아래 그래프와 같습니다. 

처음에 100개의 빵에서 (평균적으로) 74개의 서로 다른 씰을 모울 수 있습니다. 그 다음 100개의 빵에서는 약 40개의 서로 다른 씰을 모울 수 있습니다. 당연히 그래프의 개형은 위와 같이 위로 볼록한 개형이 됩니다. 

 

이번에는 빵의 갯수 $T$에 따라서 159종의 씰을 모두 모울 수 있는 확률을 구해 보도록 하겠습니다. 그 결과는 아래와 같습니다. 

500개 까지는 거의 확률이 0이고, 600개 정도를 사야 0이 아닌 확률을 얻습니다. 159종을 모두 모울 수 있는 빵의 갯수의 기대값이 898이라고 했는데, 898개를 산다고 하더라도 159종의 씰을 모두 얻을 수 있는 확률은 약 50%정도 밖에 되지 않습니다. 안전하게 하기 위해서는 1,000개 이상을 사야 합니다. 

 

1,000개의 빵을 산다면 약 86%의 확률로 159종의 씰을 모두 모울 수 있습니다. 왠만한 똥손이 아니고서는 1,000개 정도면 충분한 것 같습니다. 빵 하나에 1,500원이니 150만원이 있으면 159종을 모두 모울 수 있는 샘이 됩니다. (1,000개를 샀는데 159종을 얻지 못할 확률도 14%나 됩니다. 사실 무시할 수준은 아닙니다)

 

앞에서 159종의 씰 중 특정한 씰이 나올 확률을 그냥 균등하게 $\frac{1}{159}$로 놓았습니다. 그러나 실제로는 잘 나오는 씰은 잘 나오지만, 잘 안나오는 씰은 잘 안나온다고 하더군요. 만일 확률의 분포가 균등한 분포가 아니라면 159종의 씰을 모두 모우기 위한 기대값은 더 올라갑니다. 이 경우에는 기대값이 898개가 아니라 1,000 이나 1,500과 같이 더 커질 수 있을 것 입니다.