과자 봉지마다 들어 있는 스티커를 모아 본 적이 있다면, 처음에는 봉지를 뜯을 때마다 새 스티커가 나와 금방 다 모을 것 같았던 기억이 있을 겁니다. 그런데 앨범이 거의 다 찰 무렵부터는 이미 가진 스티커만 계속 나오고, 마지막 한두 장은 좀처럼 나오지 않습니다. 운이 나빠서가 아니라 확률이 원래 그렇게 움직이기 때문입니다. 이 현상을 수학으로 풀어낸 것이 바로 ‘쿠폰 수집가 문제(Coupon Collector’s Problem)’입니다.

쿠폰 수집가 문제란 쉽게 말해 ‘여러 종류 가운데 하나가 무작위로 나올 때, 모든 종류를 적어도 한 번씩 모으려면 평균 몇 번을 뽑아야 하는가’를 묻는 확률 문제를 의미합니다. 답은 생각보다 훨씬 크고, 그 대부분이 마지막 몇 종류를 기다리는 데 쓰인다는 점이 핵심입니다.

본 자료에서는 쿠폰 수집가 문제가 무엇인지부터, 평균 횟수를 계산하는 원리, 숫자로 보는 구체적인 예시, 그리고 이 문제가 실생활과 기술에서 쓰이는 곳과 주의할 점까지 차례로 살펴보겠습니다.

---

마지막 한 장이 가장 비싸다, 쿠폰 수집가 문제

쿠폰 수집가 문제란 무엇인가

이 문제의 이름은 시리얼 상자마다 쿠폰을 한 장씩 넣고, 모든 종류를 모으면 상품을 주던 판촉 행사에서 왔습니다. 수학적으로는 다음과 같은 조건을 둡니다.

(1) 종류의 수가 정해져 있다
모아야 할 쿠폰은 모두 n가지이며, 수집가는 이 수를 미리 알고 있습니다.

(2) 한 번에 한 장씩 무작위로 나온다
상자를 하나 살 때마다 n가지 가운데 하나가 같은 확률로 나오고, 앞에서 무엇이 나왔는지는 다음 결과에 영향을 주지 않습니다.

(3) 중복이 생긴다
이미 가진 쿠폰이 다시 나올 수 있습니다. 같은 쿠폰을 여러 번 받는 일이 바로 수집을 길게 만드는 원인입니다.

주사위로 바꿔 말하면 ‘여섯 면이 모두 한 번씩 나올 때까지 주사위를 평균 몇 번 던져야 하는가’라는 질문과 같습니다.

---

평균 횟수는 어떻게 계산할까

수집 과정을 ‘새 종류를 하나 얻을 때까지’의 구간으로 나누어 보면 계산이 쉬워집니다.

(1) 처음에는 무엇이든 새것이다
아무것도 없을 때는 첫 번째 뽑기가 반드시 새 종류이므로 한 번이면 충분합니다.

(2) 모을수록 새것이 나올 확률이 줄어든다
이미 k가지를 가지고 있다면 새 종류가 나올 확률은 (n – k) / n입니다. 성공 확률이 p인 일을 성공할 때까지 반복하면 평균 1 / p번이 걸리므로, 이 구간에는 평균 n / (n – k)번이 필요합니다.

(3) 구간들을 모두 더한다
각 구간의 평균을 더하면 전체 평균은 n × (1 + 1/2 + 1/3 + … + 1/n)이 됩니다. 괄호 안의 합을 조화수라고 부르며, n이 커지면 대략 n × (n의 자연로그) + 0.577 × n 정도로 늘어납니다. 프랑스의 수학자 피에르시몽 라플라스(Pierre-Simon Laplace)도 1812년 확률론 저서에서 이 문제를 다루었습니다.

주사위로 직접 따져 보면 이해가 쉽습니다. 첫 면은 1번, 두 번째 새 면은 6/5번, 세 번째는 6/4번, 네 번째는 6/3번, 다섯 번째는 6/2번, 마지막 여섯 번째는 6/1번이 평균적으로 걸립니다. 이를 모두 더하면 약 14.7번이 되며, 그중 마지막 한 면을 기다리는 데만 평균 6번이 들어갑니다.

이 식에서 보듯 마지막 구간, 즉 딱 한 종류만 남았을 때는 혼자서 평균 n번을 기다려야 합니다. 앞에서 모은 종류가 많을수록 새것을 만나기 어려워지는 구조가 수집 기간을 길게 늘리는 것입니다.

---

숫자로 보는 수집의 현실

계산 결과를 구체적인 숫자로 보면 직관과 얼마나 다른지 분명해집니다.

• 주사위(Die): 앞에서 계산했듯 여섯 면을 모두 보려면 평균 약 14.7번을 던져야 합니다. 여섯 번이면 될 것 같지만 두 배가 넘습니다.
• 쿠폰 10종(Ten Coupons): 평균 약 29.3번이 필요합니다.
• 쿠폰 50종(Fifty Coupons): 평균 약 225번이 필요합니다. 그중 앞의 25종을 모으는 데는 약 34번이면 되지만, 나머지 25종을 모으는 데는 약 191번이 듭니다.
• 쿠폰 100종(One Hundred Coupons): 평균 약 519번으로, 종류 수의 다섯 배가 넘습니다.

여기서 말하는 숫자는 평균일 뿐이라 실제로는 훨씬 더 오래 걸리는 사람도 많습니다. 또 일부 종류를 일부러 적게 넣는 ‘희귀 카드’가 있다면, 같은 확률일 때보다 기대 횟수는 더 커집니다.

---

쿠폰 수집가 문제가 쓰이는 곳과 주의할 점

이 문제는 스티커 앨범을 넘어 여러 분야에서 쓰입니다.

(1) 판촉과 소비 설계
무작위로 나오는 수집형 상품은 마지막 몇 종류를 얻기 위해 같은 상품을 반복해서 사게 만드는 구조입니다. 소비자 입장에서는 기대 비용을 미리 계산해 보는 것만으로도 충동 구매를 줄일 수 있습니다.

(2) 컴퓨터 과학과 알고리즘
무작위로 고른 요소가 모든 경우를 한 번씩 거치기까지 걸리는 시간을 따질 때 이 계산이 쓰이며, 무작위 알고리즘 교과서에서 대표 예제로 다룹니다.

(3) 교환이 답이 될 수 있다
여러 사람이 함께 모으며 중복된 것을 서로 바꾸면, 혼자 모을 때보다 한 사람이 사야 할 양이 크게 줄어듭니다. 남는 중복이 다른 사람에게는 필요한 한 장이 되기 때문입니다.

(4) 남은 횟수를 가늠하는 기준
이미 여러 종류를 모았다면 남은 종류에 대해서만 같은 방식으로 계산하면 됩니다. 예를 들어 50종 가운데 49종을 모았다면, 마지막 한 장을 얻기까지 평균 50번을 더 뽑아야 한다는 뜻입니다.

다만 실제 상품은 종류마다 나오는 비율이 다르거나 공개되지 않는 경우가 많아, 계산은 어디까지나 출발점으로 삼아야 합니다.

---

쿠폰 수집가 문제는 모으면 모을수록 새것을 얻기가 어려워진다는 단순한 사실이 얼마나 큰 차이를 만드는지 보여 줍니다. 마지막 한 장이 유독 안 나오는 것은 불운이 아니라 확률이 정해 둔 길입니다.

수집을 시작하기 전에 몇 번이 필요할지 한 번쯤 계산해 보고, 중복을 나눌 친구를 찾아보는 것, 그것이 현명한 수집의 첫걸음입니다.