Expected value of a sum of random events

Question

Suppose there's a market that has decided to award its most loyal customers. The market sells a certain type of breakfast cereals with a single token in each box. There are n different types of tokens. During production of each box, a token is chosen at random and placed in the box. In order to be awarded a prize, one must collect all different tokens. If each box of cereal costs x dollars, what is the expected amount of money (in terms of x) one would have to pay in order to win the prize?

Answer 1

Let $X_{k}$ denote the number of boxes that are to be bought to come in possession of $k+1$ tokens, counting from the moment that one is in possession of exactly $k$ different tokens.

Then $X=1+X_{1}+\cdots+X_{n-1}$ boxes must be bought.

Here $X_{k}$ has geometric distribution with parameter $p_{k}=1-\frac{k}{n}$ so that $\mathbb{E}X_{k}=\frac{1}{p_{k}}=\frac{n}{n-k}$.

We find $\mathbb{E}X=\sum_{k=0}^{n-1}\frac{n}{n-k}=n\sum_{k=1}^{n}\frac{1}{k}$

The expected amount of money to be paid is $nx\sum_{k=1}^{n}\frac{1}{k}$.