## Plus Magazine

Submitted by plusadmin on March 1, 2006## 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 *X _{0}*,

*X*, etc, up to

_{1}*X*. Each random variable

_{N-1}*X*counts how many purchases you have to make to get a new card if you already have

_{i}*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 *X _{i}*, the probability that you have to make

*j*purchases to get a new card is

*X*has the well-known

_{i}*geometric probability distribution*with parameter

This distribution has variance

*X*is the sum of the

*N*random variables

*X*,

_{0}*X*, ... ,

_{1}*X*, then the variance of

_{N-1}*X*is

Dividing through by *N ^{2}* gives

*N*gets large, the first term tends to , as was stated in the hint, while the second term tends to zero. This proves that the standard deviation for large

*N*is close to which is approximately

*1.3 N*— QED.

Back to Outer space