3
$\begingroup$

I am struggling with this probability/combinatorics problem.

the problem states: "11 people are seated around a round table. At some point, everyone stands up and sits again at a randomly chosen seat. Show that the expected value of the number of pairs which swapped places (A sat at B's place and B sat at A's place) is 1/2."

I struggle with calculating the number of orderings in which pairs switch places. I know we have 10! possible permutations for 11 people sitting in a circle, and there are $11\choose2$ possible pairs that could switch places. But I'm not sure how to count for example the number of permutation in which only one couple switches places.

$\endgroup$
3
$\begingroup$

Number the people from 1 to 11 and define $$X_{A,B} = \begin{cases} 1 \quad \text{if A and B switch places} \\ 0 \quad \text{otherwise} \end{cases}$$ for $1 \le A < B \le 11$.

The probability that $A$ ends up in $B$'s former position is $1/11$, and then the probability that $B$ also ends up in $A$'s former position is $1/10$; so $$P(X_{A,B} = 1) = \frac {1} {11 \cdot 10}$$

The expected number of pairs who switch places is $$\begin{align} E \left( \sum_{1 \le A < B \le 11} X_{A,B} \right) &= \sum_{1 \le A < B \le 11} E(X_{A,B} ) \tag{1}\\ &= \binom{11}{2} \frac {1} {11 \cdot 10} \tag{2}\\ &= \frac{1}{2} \end{align}$$ At $(1)$ we have used linearity of expectation, and at $(2)$ we have used the fact that the number of pairs $(A,B)$ satisfying $1 \le A < B \le 11$ is $\binom{11}{2}$, the number of subsets of $\{1,2,3,\dots,11\}$ of size $2$.

$\endgroup$
2
$\begingroup$

There's a total of $11!$ possible permutations. A given pair $(a,b)$ gets switched in exactly $(11-2)! = 9!$ of these: the elements $a$ and $b$ get swapped while the rest (the other 9 elements) are free to do whatever (to permute among themselves). There is a total of $\frac{11*10}{2}$ pairs $(a,b)$, giving a total of $9!\frac{11*10}{2}$ switchings for all pairs in all permutations. Dividing by the number of permutations gives an average of $\frac{1}{2}$ switchings per permutation.

$\endgroup$

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.