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.