Monday Math 39

Suppose we have a group of n people (n≥2). The name of each person is written on a separate slip of paper. These n slips are put in a box, and each person then draws a slip from the box. What, then, is the probability that nobody draws their own name? What happens to this probability when n becomes large?

We can treat a drawing outcome as a permutation on n items (the names). There are n! such permutations. What we need to find the probability we desire is the number of these permutations which leave no elements unshifted; that is, which contain no fixed points.

For the case n=2, there’s one such permutation (the swap), and so the probability is . Similarly, for n=3, there are the two cyclic permutations, and so the probability is . Trying to count the permutations becomes more lengthy with each increase in n. Thus, we seek a simpler way to do this.

Let us consider the probability of having k of the n people draw names other than their own, and write this . Then we seek . Now, , the probability that everyone draws their own name, is . We also have, from the basics of probability, that .

Thus, we see

n 0 1 2 3
1 1 0
2 1/2 0 1/2
3 1/6 0 1/2 1/3

Now, is the probability of k people drawing the names of others, and thus nk drawing their own. As these are independent events, we see
(to make this product accurate for k=0, we need ).
Combining this with the basic probability rule, we get

for any n. This gives us the recursive formula

for in terms of all previous ones.
Thus, we can determine the values:
Similarly, .

Now, let us examine :

Examining these, we thus find our desired result:
(A proof by induction can confirm this.)

And for large n, we use . This tells us , and thus, we see that approaches as n goes to infinity, and the approximation becomes very close very rapidly: .


Tags: , , ,

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: