expected number of cards drawn exactly once (with replacement) [closed]

Suppose there are $N$ cards, $1,2,\dots,N$. We start drawing cards (with replacement), until each card has been drawn at least once (we stop when the last card is drawn for the first time). Let $x$ be the number of cards that have been drawn exactly once. What is the expected value of $x$?

The answer is supposed to be $1 + \frac{1}{2} +\dots+ \frac{1}{N}$.

Solution 1:

The card $c_k$ that is drawn as the $k$-th last has a probability $\frac1k$ of being drawn exactly once. To see this, focus on the $k$ cards that had not yet been drawn when this card was drawn. In the remaining draws, each of the $k$ has the same probability of being drawn last of the $k$, so this probability is $\frac1k$. The card $c_k$ will not be drawn again if and only if it would have been the last of the $k$ to be drawn.

Solution 2:

Intriguing question, that corresponds to many equivalent combinatoric schemes, and which all fall into what is known as "the coupon's collector" problem. Re. for instance to the paper:

http://arxiv.org/abs/math/0304229v1

which contains an exhaustive examination of some particular cases, including that of "coupons drawn only once (singletons)" and the proof that the expected value of x is as you indicated, which, interestingly, is $1/N$*(expected total No. of draws).