medium   Probability

Transpositions

A release-checked medium problem for training Counting With Indicators, Linearity of Expectation.

Question

Let $P = (p_1,\dots, p_n)$ be a uniformly random permutation of $[n] = \{1,2,\dots,n\}$. We say $(i,j)$ is a $\textit{transposition}$ if $p_i = j$ and $p_j = i$ for $i < j$. For example, if $n = 4$, then in $(1,2,4,3)$, $(3,4)$ is a transposition, as the fourth element is $3$ and the third element is $4$. Find the expected number of transpositions in $P$ when $n = 10$.

Practice focus

This Probability problem is tagged Counting With Indicators, Linearity of Expectation. State the random variables and conditioning information explicitly, then check the result against boundary cases before opening hints or a solution.

Explore related collections

Reviewed questions in this area

easyBaby BoyReviewed

Probability · SIG, DE Shaw

easyBad BagelReviewed

Probability · SIG, Jane Street