Mathematical expectation of the number of transpositions in random permutation.

Question

Let $P=(p_1,p_2,\ldots,p_n)$ be a permutation chosen randomly and equiprobably from S(n). We say that $(i, j)$ is a transposition if $p_i=j$ and $p_j=i$. Calculate the mathematical expectation of the number of transpositions in the permutation $P$.

Let $\gamma$ be a random variable equal to the number of transpositions in the permutation.

Then $Pr(\gamma=k)$ is equal to

$Pr((\exists \; i_1,j_1,\ldots,i_k,j_k$ $(i_r,j_r)$ - transposition) and ($\forall l,s \in \bar{(1,n)} \setminus\{i_1,j_1,\ldots,i_k,j_k\}$ $(l,s)$ is not transposition)). I have problems with calculating this probability.

Answer 1

Let $X_{ij}$ be a random variable which is 1 if $(i, j)$ is a transposition and 0 otherwise - that is, an indicator random variable for the event that $(i, j)$ is a transposition. Then the expectation you want is just

$$ E \left( \sum_{i=1}^n \sum_{j=1}^{i-1} X_{ij} \right) $$

and by linearity of expectation, this is

$$ \sum_{i=1}^n \sum_{j=1}^{i-1} E(X_{ij}) $$

Now you need to find $E(X_{ij})$. This is the number of permutations $p$ of $\{ 1, 2, \ldots, n \}$ with $p_i = j, p_j = i$, divided by $n!$. Find that numerator and do the sum. (Hint: the sum is easy.)