Software Journal

Problem: 10 people walk into a party and give their hats to the coat and hat check guy. When the party finishes, their hats are returned in no specific order and with no specific intent. What is the probability that no one gets their own hat back? (This is an old problem, and a standard one in combinatorics and probability.)

First, an approximate solution: probability that a person gets his hat back is 1/10, so the probability that the person does not get his hat back is 9/10. So the probability that no one gets their hat back is 0.9^10 = 0.34868. Why is this solution imperfect? Well, because the events aren’t really independent. If one person gets their hat back, it increases the chance that the remaining people will get their hats back (easy to see that with two people ).  We can’t really multiple the event probabilities, if the events are not independent.

The solution: The correct solution comes from combinatorics. Total number of ways in which hats can be returned is 10! (10 factorial = 10 x 9 x 8 x … 1). If we can count the number of ways in which no guest receives their hat back, then we can deduce the probability by dividing that number by 10!. To count that, we can use the principle of inclusion and exclusion. Say A1 is the set of cases in which the first guest receives his own hat back. Then, we can enumerate:

The cases in which some guest(s) receive their own hats back are: A1 U A2 U … U A10

The number of ways in which that happens can then be written as:
|A1 U A2 U A3 …. A10| = |A1| + |A2| .. + |A10| – (|A1 intersection A2| + |A1 intersection A3| …. + |A9 intersection A10|) + (|A1 intersection A2 intersection A3| + …. |A8 intersection A9 intersection A10|) – (|A1 intersection A2 intersection A3 intersection A4| + … |A7 intersection A8 intersection A9 intersection A10|) + …. – (A1 intersection A2 intersection … intersection A10)

Due to symmetry, we can say that:

|A1 U A2 .. A10| = 10 |A1| – C(10,2) |A1 intersection A2| + C(10,3) |A1 intersection A2 intersection A3| – C(10,4) |A1 intersection A2 intersection A3 intersection A4| + … – C(10,10) |A1 intersection A2 intersection A3 intersection … intersection A10|
[where C(10,2) is the number of ways to select two people out of 10 = 10! / (8! * 2!) ]

Now if we can calculate |A1 intersection A2 … intersection Ai|, we can get our answer. To see that part, the number of ways in which the guests 1..i receive their hats back is simply (10 – i)! because that is the number of ways in which the remaining guests can get their hats back (whether or not those other guests get their own hats back).

So, here we go:
|A1 U A2 .. A10| = 10 * 9! – C(10,2) 8! + C(10,3) 7! – C(10,4) 6! + …. – C(10,10) 0!
= 10 * 362880 – 45 * 40320 + 120 * 5040 – 210 * 720 + 252 * 120 – 210 * 24 + 120 * 6 – 45 * 2 + 10 * 1 – 1 * 1
= 2293839

Therefore, the probability that no guest receives their hat back is 1 – 2293839/10! = 0.367879464.

Monte Carlo Simulation: As Dijksra said (he said it once, I quote it often): Don’t rely on it – I have only proven my solution correct, I haven’t actually tested it. So, I wrote a small program to try this experiment randomly a bahzillion times and check how many times the 10 people get their hats back.  Here are the simulation results:

Strings: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Going to run 100,000,000 tests.
Finished test number: 10000000
Finished test number: 20000000
Finished test number: 30000000
Finished test number: 40000000
Finished test number: 50000000
Finished test number: 60000000
Finished test number: 70000000
Finished test number: 80000000
Finished test number: 90000000
Finished test number: 100000000
Results:
Total Cases tested: 100000000
Cases in which no guest got their hat back: 36782656.

Seems to me that that matches the analytical result above pretty well.

Entire source code is available here. Feel free to use it whichever way you want, but don’t hold me responsible if your space ship crashes against an asteroid because of it. It is unoptimized, unclean, smelly code – so hold your criticism.