Reply to comment
A collector's piece: solution
In last issue's outer space we worked out how many pruchases you would expect to have to make in order to obtain every one of a set of N distinct cards. The puzzle was to show that the standard deviation of this result is close to 1.3N for large N. To work out the expectation, we considered N random variables X0, X1, etc, up to XN-1. Each random variable Xi counts how many purchases you have to make to get a new card if you already have i distinct cards. The overall expectation is then just the sum of the individual expectations of the N variables.
You can use the same technique to work out the standard deviation (which is of course the square root of the variance): since the N random variables are independent of each other, the overall variance is simply the sum of the individual values.
For each individual variable Xi, the probability that you have to make j purchases to get a new card is
This distribution has variance
Dividing through by N2 gives
Back to Outer space