A total of $2n$ people, consisting of $n$ married couples, are randomly seated (all possible orderings being equally likely) at a round table. Let $C_i$ denote the event that the members of couple $i$ are seated next to each other, $i = 1,...,n$

a) Find $P(C_i)$

Attempt: So this is the prob that one particular couple sit next to each other. There are $2n$ seats for the first person. Given that the table is round, there are 2 seats for the wife/husband, (either to the left or right) and $(2n-2)!$ rearrangements of the remaining people. Since each of the orderings are equally likely, $|s| = (2n)!$ and the prob we want is $(2n) \cdot 2 \cdot (2n-2)! / (2n)! = 2/(2n-1) $ Is it a good argument?

b) For $j \neq i,\, \text{find} \, P(C_i|C_j)$

Attempt: This is the prob that given some couple $j$ already sitting next to one another, what is the probability that some other couple $i$ are sitting next to each other. By definition, this is equal to $P(C_i, C_j)/P(C_j)$. I already computed the denominator in a), so I need only worry about the numerator. For the numerator: If couple $i$ and $j$ are to sit next to each other, there are $(2n)$ places for the first person and $2$ choices for the next person. For the other couple, I am not really sure what to say since if one member of couple $j$ sits next to a member of couple $i$, then there is only one place for the other member of couple $j$. But, if the couple $j$ do not sit any where near couple $i$ then there is more than one place for the other member. It seems reasonable to compute therefore, $$P(C_i,C_j) = P(C_i,C_j| \text{one member of j next to i})P(\text{one member of j next to i}) + P(C_i,C_j|\text{member of j not next to i})P(\text{member of j not next to i})$$ Does this make sense and is my approach good or not?

c) Approximate the probability, for $n$ large, that there are no married couples who are seated next to each other.

Attempt: $P(\text{no married couples next to each other}) = 1-P(\text{at least one couple sit next to each other})$I know the approximation will be Poisson since n is large, but I am not sure where to go from here. Thanks!

  • $\begingroup$ (a) is correct but too complicated. Pretend that wife #$i$ chose her seat first among all $2n$ people and husband #$i$ chose next. It doesn't matter where she sits; hubby has $2n-1$ places to choose from at random, and only two of them put him next to his wife. $\endgroup$ – Dilip Sarwate Dec 8 '12 at 15:55
  • $\begingroup$ That's nice. Can you help me at all with parts b), c)? $\endgroup$ – CAF Dec 8 '12 at 16:29
  • $\begingroup$ Try developing it in your own. Couple #$j$ is already seated next to each other. Now let wife #$i$ choose next, and break up the problem into two parts: she sits next to the already seated couple, and she sits apart from the already seated couple. $\endgroup$ – Dilip Sarwate Dec 8 '12 at 17:07
  • $\begingroup$ So what I wrote was good for b)? I wanted to verify that the equation I wrote was right before I started computing the terms. Thanks. $\endgroup$ – CAF Dec 8 '12 at 17:19
  • $\begingroup$ For (b), if couple $j$ are neighbours, the rest of the table is essentially a line. There are $\binom{n-2}{2}$ equally likely ways to choose the (unordered) pair of chairs occupied by couple $i$, and $n-2-1$ of these choices are "good." $\endgroup$ – André Nicolas Dec 8 '12 at 18:06

a) The probability that a particular wife has her husband sitting next to her is $\dfrac{2}{2n-1}$ since she has two neighbours.

b) You can regard couple $i$ together as breaking the circle so that the question now involves a row of $2n-2$ people. These can be arranged in $(2n-2)!$ ways. But the number of ways they can be arranged if couple $j$ sit together is $2(2n-3)!$ since we could treat couple $j$ as a single person, but doubling the number as they can sit either way round. So the probability is $\dfrac{2}{2n-2}$.

c) Going back to (a), the expected number of couples sitting together is $\tfrac{2n}{2n-1}$ which for large $n$ approaches $1$. Using your Poisson approximation [which also uses the almost independence between couples illustrated by the answer to (b) being close to the answer for (a)] with an expectation of $1$, the limit of the probability of no couples together is $e^{-1}\approx 0.3678794$. For a similar question (couples in a row rather than a circle) see Showing probability no husband next to wife converges to $e^{-1}$

| cite | improve this answer | |
  • $\begingroup$ I'm a bit confused on how you get the expected value for part c). $\endgroup$ – Vedaad Shakib Sep 7 '16 at 7:26
  • 1
    $\begingroup$ @VedaadShakib If from (a) you have the probability that a particular wife has her husband sitting next to her is $\dfrac{2}{2n−1}$ and there are $n$ couples, then by linearity of expectation the expected number of couples sitting together is $n \times \dfrac{2}{2n−1}$ $\endgroup$ – Henry Sep 7 '16 at 7:31
  • $\begingroup$ Thanks for the speedy response. So do you assume that the values of $P(C_i)$ are independent? $\endgroup$ – Vedaad Shakib Sep 7 '16 at 7:37
  • 1
    $\begingroup$ @VedaadShakib You do not need independence for that expectation. You do need to assume it for CAF's Poisson approximation $\endgroup$ – Henry Sep 7 '16 at 7:43

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.