The Distribution of the Number of Matches

Java Applet Simulation of the matching experiment

To find the discrete density function of the number of matches, we need to count the number of permutations with a specified number of matches. This will turn out to be easy once we have counted the number of permutations with no matches; these are called derangements of {1, 2, ..., n}.

We will denote the number of permutations with exactly k matches by

b_n(k) = #{N_n = k} for k in {0, 1, ..., n}

Derangements

1. Use basic properties of counting measure to show that

b_n(0) = n! - #{X_i = i for some i}

2. Use the inclusion-exclusion formula of combinatorics to show that

3. Show that if #(J) = j then

#{X_i = i for i in J} = (n - j)!

4. Use the results of Exercises 2 and 3 to show that

Permutations with k Matches

5. Show that the following two-step procedure generates all permutations with exactly k matches.

1. Select the k integers that will match.
2. Select a permutation of the remaining n - k integers with no matches.

6. Show that the number of ways of performing the steps in Exercise 5 are, respectively,

1. C(n, k)
2. b_{n - k}(0)

7. Use the multiplication principle of combinatorics to show that

The Density Function

8. Use the result of Exercise 7 to show that the density function of the number of matches is

9. In the matching experiment, start with n = 2 and click repeatedly on the scrollbar to increase n. Note how the graph of the density function changes. Now with n = 10, run the simulation 1000 times, updating every 10 runs. Note the apparent convergence of empirical density to the true density.

10. Show that P(N_n = n - 1) = 0. Give a probabilistic proof by arguing that the event is impossible and an algebraic proof using the density function in Exercise 8.

The Poisson Approximation

11. Show that

As a function of k, the right-hand side of the expression in Exercise 1 is the Poisson density function with parameter 1. Thus, the distribution of the number of matches converges to the Poisson distribution with parameter 1 as the n increases. The convergence is very rapid. Indeed, the distribution of the number of matches with n = 10 is essentially the same as the distribution of the number of matches with n = 1000000!

12. In the matching experiment, set n = 10. Run the experiment 1000 times with an update frequency of 10. Compare the relative frequencies, the true probabilities, and the limiting Poisson probabilities for the number of matches.

The Matching Experiment