
\problemdata     
{S01-PS10-4}           
{IRV's, probability-expectation}              
{} 		
{S01-PS10}
{S01 Karger}





\begin{problem}


 There is a dinner party for $n \geq 2$
couples.  The hostess chooses a seating arrangement for the $2n$
people around a circular table uniformly at random.  What is the
expected number of couples such that the husband and wife are sitting
next to each other?

\hint Use indicator random variables and linearity of expectation. What's the probability that Mr. Jones is sitting next to Mrs. Jones? 

\solution{
\textbf{Solution:}\\
Let $I_k$ be an indicator variable for the event that couple
$k$ is sitting together.  Then the number of couples sitting together
is $I_1 + I_2 + \ldots + I_n$.  The probability that a couple is
seated together is $2 / (2n-1)$, since a wife is equally likely to
occupy each of the $2n-1$ positions relative to her husband and there
are 2 positions right next to him.  Consequently, $\Pr(I_k = 1) = 2 /
(2n-1)$, and we can reason as follows:

\begin{eqnarray*}
\Ex(\text{couples sitting together})
    & = &   \Ex\left(\sum_{k=1}^n I_k\right) \\
    & = &   \sum_{k=1}^n \Ex(I_k) \\
    & = &   \sum_{k=1}^n \Pr(I_k = 1) \\
    & = &   \sum_{k=1}^n \frac{2}{2n-1} \\
    & = &   \frac{2n}{2n-1}
\end{eqnarray*}

Thus, regardless of the size of the party, the expected number of
couples seated together is always close to 1.}

\end{problem}
