0
$\begingroup$

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 ?

$\endgroup$
  • 2
    $\begingroup$ How many of these $n!$ permutations have $i$ as a fixed point? $\endgroup$ – Daniel Fischer Aug 14 '18 at 18:03
  • $\begingroup$ @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 ? $\endgroup$ – zython Aug 14 '18 at 18:06
  • 2
    $\begingroup$ 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. $\endgroup$ – Daniel Fischer Aug 14 '18 at 18:10
  • $\begingroup$ @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. $\endgroup$ – zython Aug 14 '18 at 18:13
  • 1
    $\begingroup$ What happens early in the morning though? $\endgroup$ – Maxim Aug 14 '18 at 19:26
2
$\begingroup$

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$

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.