
\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 host 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 partners are sitting next
to each other?

\hint Use indicator random variables and linearity of expectation. 
What's the probability that Jorge is sitting next to his date? 

\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 diner is equally likely to
occupy each of the $2n-1$ positions relative to her partner and there
are 2 positions right next to the partner.  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}
