The Mean and Variance of the Number of Matches

Java Applet Simulation of the matching experiment

The mean and variance of the number of matches could be computed directly from the distribution. However, it is much better to use the representation in terms of indicator variables:

N_n = I₁ + I₂ + ··· + I_n
where I_j = 1 if X_j = j and I_j = 0 otherwise.

The exchangeable property is an important tool in this section.

The Mean

$Mathematical Exercise$ 1. Show that for any j,

$Mathematical Exercise$ 2. Use the result of Exercise 1 and basic properties of expected value to show

E(N_n) = 1

Thus, the expected number of matches is 1, regardless of the size of the permutation n.

3. In the matching experiment, start with n = 2 and click repeatedly on the scrollbar to increase n. Note that the mean does not change. Now with n = 10, run the simulation 1000 times, updating every 10 runs. Note the apparent convergence of sample mean to the distribution mean.

The Variance

$Mathematical Exercise$ 4. Show that

A match in one position would seem to make it more likely that there would be a match in another position. Thus, we might guess that the indicator variables are positively correlated.

$Mathematical Exercise$ 5. Show that if j and k are distinct then

From Exercise 5, when n = 2, the event that there is a match in position 1 is perfectly correlated with the event that there is a match in position 2. Does this result seem reasonable?

$Mathematical Exercise$ 6. Use Exercises 4 and 5 and basic properties of covariance to show that for any n,

var(N_n) = 1.

Thus, the variance of the number of matches is 1, regardless of the size of the permutation n.

7. In the matching experiment, start with n = 2 and click repeatedly on the scrollbar to increase n. Note that the standard deviation does not change. Now with n = 10, run the simulation 1000 times, updating every 10 runs. Note the apparent convergence of sample standard deviation to the distribution standard deviation.

$Mathematical Exercise$ 7. Show that for distinct j and k,

Thus, the event that a match occurs in position j is nearly independent of the event that a match occurs in position k if n is large. For large n, the indicator variables behave nearly like n Bernoulli trials with probability 1 / n of success. This gives additional insight into the convergence of the distribution of the number of matches to the Poisson distribution as n increases. Note also that the limiting Poisson distribution has mean 1 and variance 1.