From the always-excellent Futility Closet, a problem by Paul J. Nahin:
Each of a million people puts his or her hat into a very large box. Each hat has its owner’s name on it. The box is given a good shaking, and then each person, one after another, randomly draws a hat out of the box. What is the probability that at least one person gets their own hat back?
Most people might think that the chance is very, very small, but it’s not. It’s actually more than 60%. How can this be true?
We can view this problem as having only two possible solutions (events): either nobody gets their hat back, or at least one person gets their hat back. The sum of the probabilities of these events must be equal to one and therefore if we can work out the probability that nobody gets their own hat back, then the probability that at least one person does is one minus that.
For each person, there is only a one-in-a-million chance that they have picked their own hat, and thus a 999999 in 1000000 chance that they have not got their own hat.
If the probability of all one million people picking the incorrect hat in 0.368, then via our previous reasoning, the probability of at least one person picking the correct hat is 1-0.368, or 63.2%.
This is a very counterintuitive result, but the wording of the question is key. If we changed the wording to exactly one person getting their hat back then our answer changes dramatically. Starting with our 63.2% chance, we would have to subtract the chance of two people getting their hats back, and of three people getting their hats back, and so on … until we reached the very small chance of one person, and one person only, getting their hat back.
Hi Mr Reid,
I have some trouble following your calculation.
In my opinion, the following should be the case:
For the first person drawing the hat:
P_0 = (N-1)/N
this is the same you calculated.
but for the next person, the situation is different:
there is one less hat in the box. and one remaining person has per definition no matching hat, because the previous person just took his hat. hence:
P_1 = 1*1/(N-1) + (N – 1 – 1)/(N – 1) * (1/(N-1) + (N – 1 – 1)/(N – 1) * (N-1-1-1)/(N-1-1) )
This sum contains two parts: the first part is the case, where the person is the one, whose hat has been taken in the previous round. In this case the probability is 1, but the chance to be this person is only 1/(N-1).
The second part is for the case when the person is one of the other persons, whose hats still are in the box.
There is a chance of (N – 1 – 1)/(N-1) to be one of this persons. In this case, we again have to distinguish two cases:
First, the person might chose the hat, which belongs to the person from the first draw. the chance for this is 1/(N-1) then the miss probability is 1. The other case is, the opposite: (N-1-1)/(N-1) in this case the probability for choosing the wrong hat is (N-1-1-1)/(N-1-1).
in general the following should hold for the k+1th taking of a hat:
P_k = 1*k/(N-k) + (N-k-k)/(N-k) * ( 1*k/(N-k) + (N-k-k-1)/(N-k-k) )
After half of the N persons have taken a hat and did not get their own, no one will get its own hat, as there are no possibilities left.
so we have to multiply P_k for k=0 … N/2
I think i still have an error somewhere in my calculation. But what I want to say is, that in my opinion, the calculation is not as easy as you are proposing.
I hope you can help me find the solution to this, because the problem really interests me :)
best regards…
The hats aren’t returned to the pile, so it doesn’t matter if they’re drawn sequentially or all at once.
Thanks for the fast reply :)
that is exactly where my problem with understanding your calculation lies.
It seems to me, that with your calculation, multiple persons can draw the same hat.
however if all hats are drawn at the same time or sequentially, this is not possible.
In my opinion, your solution assumes, that the hats ARE returned to the pile.
I have found a very simple counterexample for your formula:
assume we have not 1000000 hats, but 2 hats.
now we obviously have a 50% chance so that everybody does not get his own hat.
This is because if the first person chooses the wrong hat (with 50% chance) the game is over, because the second person then has only one hat to choose which is the wrong one.
however, your equation would calculate a 25% chance: ((2-1)/2)^2 = 0.25
If hats are not returned the answer should be 1 – (10^-6) = .999999
@Mr Reid:
You got (approximately) the right number by doing a wrong computation!
As appletree points out, if the hats are not returned, the probabilities of the draws are not independent. Therefore you cannot just multiply the probabilities of single draws to find out the joint probability, as you did.
What you want to do instead, is to look at the ratio of derangements to permutations.
!N/N!
If N goes to infinity, this converges to 1/e; just like ((N-1)/N)^N does. In limit you get the same probability!
(At N = 1000000, the first 6 digits after the decimal point agree.)
So the result is indeed (approximately) 1-1/e!
@appletree:
No.
Consider the case that N is even and N/2 people have drawn hats:
Specifically, each one the hat of the person preceding them; the first one drawing the hat of the N/2-th. No matches.
(This is a derangement – a permutation with no fixed point.)
Then each of the N/2 people left can still draw the correct hat!
Your counterexample was good!
@Kris:
No.
That’s the probability that one person draws an incorrect hat.
You want 1-(N-1/N)^N. As mentioned before this converges to 1-1/e as N goes to infinity.
…and I left out a pair of brackets:
The term in the last line should be 1-((N-1)/N)^N, of course.
(That’s why I dislike writing fractions in plaintext.)
That’s equal to 1-(1-1/N)^N, which is closer to the form you wrote, Kris.