Probability a couple sits at the same table.

Question

There is a chess tournament for married couples.   There are a total of $2n$ participants in this tournament; implying there are $n$ married couples.   All of the participants meet in a ballroom which has $n$ tables in it with $2$ chairs per table.   This implies there are $2n$ chairs.   The host/hostess of the chess tournament enters the names of every participant into a computer and the computer uniformly and randomly pairs the participants up.   We define a random variable $X$ and let this equal the number of participants paired up with their original partners.   Find $E[X]$.

---

Okay, that's the question.   Now, let me type up my current thought process.   I want to define $X$ as a sum of Bernoulli random variables i.e. $X = X_1+X_2+ \cdots + X_n$.

$X_i$ ranges from $1 \to n$ because there are $n$ partners. Each $X_i$ is distributed as:

$X_i = \begin{cases} 1 & \text{if partners "i' are sitting together} \\ 0 & \text{if partners "i" are not sitting together} \end{cases}$

Then, I can just use the linearity of expectation to calculate $E[X]$:

$E[X] = E[X_1] + E[X_2] + \cdots + E[X_n]$

However, I'm having a hard time deriving the expectation of each $X_i$. I know $E[X_1] = E[X_2] = \cdots = E[X_n]$ and in a simpler Bernoulli problem the expectation is just $p = \text{probability of success} = \frac{1}{n}$ when there are $n$ choices but I am having a hard time translating that to this example.

In this problem, there are $2n$ choices for seats. So, does this imply: $P(X_i = 1) = \text{probability partners are sitting together} = \frac{1}{2n-1}$?

I say $\frac{1}{2n-1}$ because, if I am standing in one of the participant's shoes, there are $2n-1$ people other than myself and only one of them is my partner.

Or, would it be $\frac{2}{2n-1}$ because there are two ways for the couple to be paired up together i.e. let $A$ and $B$ represent the two members of a couple. Either $A$ can be paired with $B$ or $B$ can be paired with $A$.

Answer 1

You are right, It is $\frac{1}{2n-1}$. It is convenient to assume that in every couple, one of the members of the couple is wearing blue, and the other is wearing red.

Let the people wearing blue be labelled $1$ to $n$, and let $X_i=1$ if blue-wearer $i$ is partnered with the person he/she couples with, and $0$ otherwise. We have $\Pr(X_i=1)=\frac{1}{2n-1}$, because only one of the remaining $2n-1$ people is the partner of blue-wearer $i$.

Thus the required expectation is $\frac{n}{2n-1}$.

Answer 2

Let's say $M_n$ is the number of ways to pair $2n$ people together ($n$ couples). Now let's count these pairings by singling out one person. There are $2n-1$ ways to pair this person off. Once paired there are $M_{n-1}$ ways to pair the remaining $2n-2$ people. This leads to the recurrence relation

$$ M_n = (2n-1)M_{n-1}, \;\; M_1=1. $$

Now assume that the $i^{th}$ couple is paired together. There are $M_{n-1}$ ways to pair off the remaining people. So the probability that the $i^{th}$ couple is together is

$$ \begin{align} P(X_i = 1) &= \frac{\mbox{# of configurations with couple }i\mbox{ paired}}{\mbox{total # of configurations}} \\ &= \frac{M_{n-1}}{M_n} \\ &= \frac{M_{n-1}}{(2n-1)M_{n-1}} \\ &= \frac{1}{2n-1}. \end{align} $$

Summing the expectation values as you did gives the desired result. Incidentally $M_n$ is the product of odd numbers and is given by

$$ M_n = \frac{(2n)!}{2^nn!}. $$