Plus Magazine

Share this page
March 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 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

  \[ \frac{N-i}{N} \times \left(1 - \frac{N-i}{N}\right)^{j-1}. \]    
So each individual Xi has the well-known geometric probability distribution with parameter
  \[ p = \frac{N-i}{N}. \]    

This distribution has variance

  \[ \frac{1-p}{p^2} = \frac{iN}{(N-i)^2}. \]    
Now if X is the sum of the N random variables X0, X1, ... , XN-1, then the variance of X is
  \[ variance(X) = \sum _{i=0}^{N-1} \frac{iN}{(N-i)^2} = N \sum _{i=0}^{N-1} \frac{i}{(N-i)^2}. \]    
A little thought shows that this sum can be expressed as
  \[ N \sum _{i=1}^{N} \frac{N-i}{i^2} = N\sum _{i=1}^ N \frac{N}{i^2} - N\sum _{i=1}^ N \frac{i}{i^2}, \]    
which is equal to
  \[ N^2 \sum _{i=1}^ N \frac{1}{i^2} - N \sum _{i=1}^ N \frac{1}{i}. \]    

Dividing through by N2 gives

  \[  \frac{variance(X)}{N^2} = \sum _{i=1}^ N \frac{1}{i^2} - 1/N \sum _{i=1}^ N \frac{1}{i}. \]    
As N gets large, the first term tends to $\pi ^2/6$, 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 $\sqrt{\pi ^2 N^2/6},$ which is approximately 1.3 N — QED.

Back to Outer space
Read more about...
  • Want facts and want them fast? Our Maths in a minute series explores key mathematical concepts in just a few words.

  • As COP28, the 2023 United Nations Climate Change Conference, kicks off we look at how maths can help understand the climate crisis.

  • How do you create dramatic film out of mathematics? We find out with writer and director Timothy Lanzone.

  • Mathematics plays a central role in understanding how infectious diseases spread. This collection of articles looks at some basic concepts in epidemiology to help you understand this fascinating and important field, and set you up for further study.

  • Find out why the formula we use to work out conditional probabilities is true!

  • We talk about a play that explores the fascinating mathematical collaboration between the mathematicians GH Hardy and Srinivasa Ramanujan.