N종류의 쿠폰을 모두 모으기 위한 뽑기 횟수의 기댓값

뽑기를 할 때마다 N종류의 쿠폰 가운데 하나가 무작위로 나오고, N종류의 쿠폰을 모두 모으면 상품을 주는 복권이 있다. N종류의 쿠폰을 모두 한 장 이상씩 모으기 위해서는 뽑기를 평균적으로 몇 번 해야 할까? 이는 매우 초보적인 조합론 문제이지만, 풀이 과정을 정리해 보려고 한다.

현재 가지고 있는 서로 다른 쿠폰의 개수를 X라고 하자. 초기에 $X=0$이고, $X=N$까지 가는 데의 뽑기 횟수 기댓값을 구해야 한다. 이는 $X=k$에서 $X=k+1$까지 가는 데의 기댓값 $E_k$을 모든 $0\leq k\leq N-1$에 대해 더하면 된다.

이제 $E_k$를 계산하자. $X=k$이므로 하나를 뽑았을 때 아직 뽑지 않은 쿠폰일 확률은 $(N-k)/N$이다. 그러면 왠지 직감적으로 이걸 뽑기 위해서는 확률의 역수인 $N/(N-k)$개를 뽑아야 될 거 같다는 느낌이 든다. 이는 아래 접은글에서 증명해 두었다.

편의상 뽑지 않을 쿠폰일 확률 $(N-k)/N$를 p라고 두자.

j번 만에 되려면, 처음 j-1번에서는 1-p의 확률로 뽑은 쿠폰이 나와야 하고, 마지막에는 p의 확률로 아직 뽑지 않은 쿠폰이 나와야 한다. 그러므로 구하는 기댓값은 다음과 같다. $$E_k=\sum _{j=1}^\infty jp(1-p)^{j-1}$$

이 식을 계산하기 위해, 항등식 $$\sum_{j=1}^\infty x^j=x+x^2+x^3+...=\frac{x}{1-x}$$ 의 양변을 미분하면, $$\sum_{j=1}^\infty jx^{j-1}=1+2x+3x^2+...=\frac{1}{(1-x)^2}$$

이 식에 $x=1-p$를 대입하고 양변에 p를 곱하면 구하는 $E_k$ 가 된다. $$E_k=p\times\frac{1}{p^2}=\frac{1}{p}=\frac{N}{N-k}$$

이제 $E_k$를 다 더하면, 구하는 기댓값 E는 $$E=\sum _{k=0}^{N-1}\frac{N}{N-k}=N\left(\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{N} \right )$$

이다. 괄호 안은 직접 계산하기는 어렵지만, N이 클 때는 적분으로 근사할 수 있다. $$E\approx N\int_{1}^{N+1}\frac{dt}{t}=N\ln(N+1)\approx N\ln N$$

이렇게 해서 상품을 받으려면 뽑기를 N번만 하면 되는 것이 아니라, 평균적으로는 거기에 log N을 곱한 것만큼 해야 한다는 사실을 알게 되었다. N종류의 쿠폰을 모두 $K(\geq2)$장씩 모으려면 몇 번의 뽑기를 해야 할까? K=1을 풀었으니 이제 일반화해서 풀어보고 싶다는 생각이 자연스럽게 드는데, 나는 초보적인 방법으로는 모르겠다. 나중에 알게 되면 다시 글을 올리도록 하겠다.