Think of N people sitting in N chairs. Now we have them all get up and randomly select them as we refill the seats in order. What is the probability that nobody gets their original seat back?
1st person:
Prob that seat is not occupied yet = 1
Prob of missing original seat = (N-1)/N
2nd person:
Prob that seat is not occupied yet = (N-1)/N
Prob of missing original seat = (N-2)/(N-1)
nth person:
Prob that seat is not occupied yet = (N-n)/N
Prob of missing original seat = (N-n)/(N-n+1)
To get the probability that nobody through the nth person has yet been seated in their original seat we require that the 1st person was not and the 2nd and ...
The probability that the nth person was not seated in his original seat is the probability that it was unoccupied and he was not seated in it or that it was already occupied:
(N-n)/N + (n-1)/N
So to get the probability that all persons were seated in a different seat from their original:
Product for n=1 to N of [ (N-n)/N + (n-1)/N ]
= Product for n=1 to N of [ (N-1)/N ]
= ( (N-1)/N )^N
Subtract this from 1 to get the probability that at least one person was seated in their original seat:
1 - ( (N-1)/N )^N
For N = 2^m
m 1 - ( (N-1)/N )^N
8 63.28%
12 63.22%
16 63.21%
20 63.21%
24 63.21%
28 63.21%
Main Topics
Browse All Topics
by: grg99Posted on 2004-09-28 at 09:09:31ID: 12171048
This sounds a lot like the old chestnut, the "same birthday" problem, only without the attractive waitress.
You basically have to add the probablity that m will not map to m, for all m in the range 2^n.
So it's something like (1/(2^n - 1) ) ^ (2^n) ?