Sunday, July 30, 2023

"10 people and 10 hats (an old problem)"

When drawing inferences using probability theory it is crucial to understand whether events are dependent or independent. In gambling games this is the difference between a slot machine where the last spin does not influence the outcome of the next spin and blackjack where each card that is dealt changes the composition of the deck of remaining cards.

In investing, misunderstanding this concept can lead to disaster as when the beautiful, well-trimmed hedge you have constructed from seemingly uncorrelated assets turns into a garden of weeds as the correlation you either didn't see or didn't understand makes itself apparent.

From Standard Wisdom:

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...