 # Probability

 From: T J Noonie Date: 12 March 1999 Subject: The "drunken secretary" problem Can you show me how to go about solving the following problem: If five letters are put into five addressed envelopes at random, what is the probability that none of the envelopes contains the correct letter?

### Maths Help suggests:

This is a well known problem in probability. It is known as the "drunken secretary problem" - conjuring up images of a secretary who has had a few too many drinks not bothering about how the letters are put into the envelopes.

It is quite a tricky problem. There are several methods of approaching it, each needing maths of at least A-level standard. The one below is not necessarily the shortest, but we think it is the easiest to follow and try yourself.

We will start with the case of 2 letters and 2 envelopes, and then build it up to 3, 4, and 5 letters and envelopes. We could of course go further. In each case, we will work out the number of ways of getting 0 correct matches, 1 correct match, 2 correct matches etc, and we will need to do this in reverse order. When we have a table of the number of ways of getting all the different numbers of matches, we can easily find the probabilities.

Some essential background results before we start:

• Assuming the envelopes are in fixed positions, the total number of ways of ordering the n letters to go into the n envelopes is n! (n factorial).
• If r of the n letters are matched correctly, the number of ways of choosing which r of the n are matched correctly is nCr
• We will use the notation N(0/m) to stand for "the number of ways of getting no correct matches with m letters and m envelopes.
• There is only one way that all letters can be correctly matched.
• There is no way that all but one letter can be correctly matched (think about it...!)

CONSIDER THE CASE OF 2 LETTERS AND 2 ENVELOPES

There are 2! = 2 ways in total.

Number of ways of 2 correct matches = 1 (always)

Number of ways of getting 1 correct match = 0 (always)

Number of ways of getting 0 correct matches is 2 - (1 + 0) = 1
Note that this is given by "total number of ways" minus "all the other answers"

The results here can be presented in a table:
 Correct matches 2 1 0 Number of ways 1 0 1

CONSIDER THE CASE OF 3 LETTERS AND 3 ENVELOPES

There are 3! = 6 ways in total.

Number of ways of 3 correct matches = 1 (always)

Number of ways of getting 2 correct matches = 0 (always)

Number of ways of getting 1 correct match = 3C1 × N(0/2) = 3×1 = 3
Note this is "number of ways of choosing the one which matches" times "number of ways that none of the remaining ones match". N(0/2) is taken from the previous table.

Number of ways of getting 0 correct matches is 6 - (1 + 0 + 3) = 2
Note that this is given by "total number of ways" minus "all the other answers"

The results here can be presented in a table:
 Correct matches 3 2 1 0 Number of ways 1 0 3 2

CONSIDER THE CASE OF 4 LETTERS AND 4 ENVELOPES

There are 4! = 24 ways in total.

Number of ways of 4 correct matches = 1 (always)

Number of ways of getting 3 correct matches = 0 (always)

Number of ways of getting 2 correct matches = 4C2 × N(0/2) = 6×1 = 6
Note this is "number of ways of choosing the two which match" times "number of ways that none of the remaining ones match". N(0/2) is taken from the previous table.

Number of ways of getting 1 correct match = 4C1 × N(0/3) = 4×2 = 8
Note this is "number of ways of choosing the one which matches" times "number of ways that none of the remaining ones match". N(0/3) is taken from the previous table.

Number of ways of getting 0 correct matches is 24 - (1 + 0 + 6 + 8) = 9
Note that this is given by "total number of ways" minus "all the other answers"

The results here can be presented in a table:
 Correct matches 4 3 2 1 0 Number of ways 1 0 6 8 9

CONSIDER THE CASE OF 5 LETTERS AND 5 ENVELOPES

There are 5! = 120 ways in total.

Number of ways of 5 correct matches = 1 (always)

Number of ways of getting 4 correct matches = 0 (always)

Number of ways of getting 3 correct matches = 5C3 × N(0/2) = 10×1 = 10
Note this is "number of ways of choosing the three which match" times "number of ways that none of the remaining ones match". N(0/2) is taken from the previous table.

Number of ways of getting 2 correct matches = 5C2 × N(0/3) = 10×2 = 20
Note this is "number of ways of choosing the two which match" times "number of ways that none of the remaining ones match". N(0/3) is taken from the previous table.

Number of ways of getting 1 correct match = 5C1 × N(0/4) = 5×9 = 45
Note this is "number of ways of choosing the one which matches" times "number of ways that none of the remaining ones match". N(0/4) is taken from the previous table.

Number of ways of getting 0 correct matches is 120 - (1 + 0 + 10 + 20 + 45) = 44
Note that this is given by "total number of ways" minus "all the other answers"

The results here can be presented in a table:
 Correct matches 5 4 3 2 1 0 Number of ways 1 0 10 20 45 44

This procedure can be continued recursively for higher numbers of letters and envelopes.