There's a round table with N chairs. $N$ people are seated randomly. What is the probability that a given pair of people will sit next to each other.

If you fix the first person to sit at the i-th chair, then it seems the problem reduces down to the probability of the second person sitting in the i+1 or i-1 chair locations, which is simply just $\frac{2}{N-1}$. Is this correct?

When I try to prob this with monte carlo, I seem to be getting a consistently smaller probability. The way my monte carlo algorithm works is I sample 2 numbers without replacement from $\sim U(1, N)$. Then I check that the absolute difference between the numbers is 1. If it is, then they're deemed to be sitting next to each other. Then I divide this amount by the number of trials.

  • 2
    $\begingroup$ You probably discard the pair $(1,N) $ in the simulation. $\endgroup$
    – user
    Feb 28 '21 at 21:54
  • $\begingroup$ @user Ah you're right! $\endgroup$ Mar 1 '21 at 0:31

The first part is right.

For the simulation, are you also counting the case where the chosen numbers are $1$ and $N$?

  • $\begingroup$ No, this is where I went wrong. I disregarded the fact that the table was circular in my simulation. $\endgroup$ Mar 1 '21 at 1:15

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.