Solution: Coupon drawing

Original problem here: http://dharmath.thehendrata.com/2010/01/12/coupon-drawing/

A container holds $N$ coupons. You draw successive coupons from the container, observe the coupon drawn, and then replace the coupon. What is the expected number of draws needed until all $N$ coupons have been seen at least once?

Challenge: what is the probability that the process ends after exactly $M$ draws?

Solution

Answer: $N + N/2 + N/3 + \cdots + N/(N-1) + 1$

Proof:

Fix $N$, and let $f(m)$ be the expected number of draws until we see all coupons, provided that we have seen $m$ coupons so far. The number that we are looking for is $f(0)$, and we know that $f(N) = 0$.

Observe that when we draw a random coupon, we have a $m/N$ chance of drawing a coupon we have seen, and thus wasting our draw. After that draw, the expected number of draws is still $f(m)$. But we also have a $1-m/N$ chance of drawing a new coupon, after which our expected number becomes $f(m+1)$.

So $f(m) = \frac{m}{N}(1 + f(m)) + (1-\frac{m}{N})(1 + f(m+1))$

which is equivalent to $f(m) = f(m+1) + \frac{N}{N-m}$

Since $f(N) = 0$, one can inductively prove that $f(m) = \frac{N}{1} + \frac{N}{2} + \cdots + \frac{N}{N-m}$

Solution to challenge problem

In order for the $M$-th draw to be the last draw, it must be the first occurrence of the last coupon needed. Let's say the last draw is $N$, then the first $M-1$ draws must be formed solely by coupons $1, \cdots, N-1$ where each coupon appears at least once.

Let $a_r$ be the number of strings with length $r$ where each letter can be one of $1, \cdots, N-1$. Then the probability in question is $Na_{M-1}/ N^M$


Also, we have the following relationship (think Exponential Generating Function):

$ \sum_{r=0}^{\infty} \frac{a_r}{r!}x^r = ( \sum_{r=1}^{\infty} \frac{1}{r!}x^r ) ^{N-1}$

so

$ RHS = (e^x - 1)^{N-1} = \sum_{k=0}^{N-1} \binom{N-1}{k} e^{kx} (-1)^{n-k-1}$

Now, the coefficient of $x^r$ in the binomial expansion is

$\sum_{k=0}^{N-1} \binom{N-1}{k}\frac{k^r}{r!} (-1)^{n-k-1}$

so that

$ a_r = \sum_{k=0}^{N-1}\binom{N-1}{k} k^r (-1)^{n-k-1}$

There is (as far as I know) no known simplification for the above form.