# Drunken Seaman problem

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 ?

• How many of these $n!$ permutations have $i$ as a fixed point? – Daniel Fischer Aug 14 '18 at 18:03
• @DanielFischer I'm sorry but I'm not getting it. I know what a fixed point is. Could you maybe explain your answer a little bit more ? – zython Aug 14 '18 at 18:06
• The event that seaman $i$ correctly finds his bed is the event that the permutation (seaman $k$ goes to bed $m$) has $i$ as a fixed point. The probability that that happens - under the assumption that all permutations occur with equal probability - is the number of permutations with fixed point $i$ divided by the number of all permutations. – Daniel Fischer Aug 14 '18 at 18:10
• @DanielFischer I think I'm getting it. Heres my own explanation please correct me if I'm wrong. wlog $i=0$ now when we try to build all permutations we have one less spot to "choose" from and the amounf ot permutations is $(n-1)!$. Along with your comment I think I undersand: Thanks for taking the time. I appreciate your effort very much. – zython Aug 14 '18 at 18:13
• What happens early in the morning though? – Maxim Aug 14 '18 at 19:26

• 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$