Modeling the Matching Experiment

Java Applet Simulation of the matching experiment

The Experiment

The matching experiment can the formulated in a number of colorful ways:

• Suppose that n married couples are at a party and that the mean and women are randomly paired for a dance. A match occurs if a married couple happens to be paired together.
• An absent-minded secretary prepares n letters and envelopes to send to n different people, but then randomly stuffs the letters into the envelopes. A match occurs if a letter is inserted in the proper envelope.
• n people with hats have had a bit too much to drink at a party. As they leave the party, each person randomly grabs a hat. A match occurs if a person gets his or her own hat.

These experiments are clearly equivalent from a mathematical point of view. In each case, the outcome of the experiment is a random permutation of {1, 2, ..., n} which we will denote by the random vector

X = (X₁, X₂, ..., X_n)

Thus, the sample space S consists of all such permutations. Recall that #(S) = n! Since we are choosing the permutation at random, our basic modeling assumption is that X is uniformly distributed on S. By definition, this means that

The number of objects being permuted (n) is the basic parameter of the experiment.

Matches

We will say that a match occurs at position i if

X_i = i.

Thus, number of matches is the random variable N_n defined mathematically by

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

The Simulation

In the simulation of the matching experiment, the parameter n can be varied from 2 to 20 with a scroll bar. The density and relative frequency functions of the number of matches are shown numerically in the distribution table and graphically in the distribution graph.

1. Start with n = 2 and repeatedly click on the scroll bar to increase n by 1. Note the graph of the density function of the number of matches. What seems to be happening? Now with n = 10, run the simulation 500 times and observe the random permutations and the number of matches.

The Exchangeable Property

2. Using the multiplication principle of combinatorics, show that any subsequence of k of the basic random variables

X₁, X₂, ..., X_n

is uniformly distributed on the set of permutations of size k chosen from {1, 2, ..., n}

In particular, it follows that the basic random variables are exchangeable. The result in Exercise 2 also holds for the outcome variables in the ball and urn experiment. In both cases, the experiment is equivalent to drawing a random sample, without replacement, from a finite population.

3. With n = 5, run the matching experiment 500 times. Compute the joint relative frequency function of the first and second coordinates of the random permutation. Compute the (marginal) relative frequency functions as well. Compare your results to the theoretical results in Exercise 2.

The Matching Experiment