5
$\begingroup$

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!

  • 0
    (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.2012-12-08
  • 0
    That's nice. Can you help me at all with parts b), c)?2012-12-08
  • 0
    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.2012-12-08
  • 0
    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.2012-12-08
  • 0
    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."2012-12-08
  • 0
    What do you mean by '$n-2-1 $ choices are 'good''. Is the eqn correct that I wrote down in my question?2012-12-08
  • 0
    I have the correct answer for b) now. Any hints on how I may get c)? Thanks!2012-12-09

1 Answers 1

4

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

  • 0
    I'm a bit confused on how you get the expected value for part c).2016-09-07
  • 1
    @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}$2016-09-07
  • 0
    Thanks for the speedy response. So do you assume that the values of $P(C_i)$ are independent?2016-09-07
  • 1
    @VedaadShakib You do not need independence for that expectation. You do need to assume it for CAF's Poisson approximation2016-09-07