Consider the following problem:
There are $n$ seamen who drunkenly stumble into their quarters at night.
There exist $n$ beds for the $n$ seamen.
Being drunk they choose a random bed to fall asleep in.
How many sailor do we expect to find their correct bed (every sailor has only one assigned bed) ?
So far so clear, according to my lecture notes we calculate the expected value of the event "seaman $i$ correctly finds his bed" to be:
$$ E(1_{A_i}) = \frac{|A_i|}{\Omega} = \frac{(n-1)!}{n!} = \frac{1}{n} $$
Which surprised me a little bit because I cannot fathom how this formula ($\frac{(n-1)!}{n!}$) was derived. I recognize the $n!$ part which could stand for all permutations, but other than that I'm lost.
I can calculate the expected otherwise but this identity is a mystery to me.
Can somebody explain this formula to me ?
Best Answer
As a count of equally probable events
numerator: Sailor $i$ in the correct bed, and the other $n-1$ sailors in the other $n-1$ beds, one per bed, $(n-1)!$ ways
denominator: $n$ sailors in the $n$ beds, one per bed, $n!$ ways
so a probability of $\frac{(n-1)!}{n!}=\frac1n$
You can find the expected total number of sailors in the correct beds using linearity of expectation and adding up the expected correct number in bed $i$ over $i$ from $1$ to $n$