For a permutation $\pi$, let $S(\pi$) be the minimum number of transpositions required to sort the elements in increasing order. Show that for a random permutation $\pi \in S_{10001}$ $E[S(\pi)] ≥ 5000$, and deduce that $P(S(\pi) ≤ 4500) < 1/20$.
By using the probability space suggested in the answer to this question: https://mathoverflow.net/questions/120163/concentration-bounds-for-sums-of-random-variables-of-permutations it can be easily seen that the random variable S is 2-Lipschitz. If $E[S(\pi)] ≥ 5000$ then $P(S(\pi) ≤ 4500) < 1/20$ follows immediately by using the Azuma-Hoeffding inequality.
My question is: How can I show that $E[S(\pi)] ≥ 5000$?
You can partition a permutation into cycles. For example, the permutation $\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 5 & 1 & 3 & 4 & 2\end{pmatrix}$ has cycles $(5, 2, 1)$, $(3)$ and $(4)$.
Now let's do a transposition. When swapping two elements that belong to the same cycle, the cycle is split into two smaller cycles. When swapping two elements that belong to different cycles, the two cycles merge into one cycle.
Let $n$ be the number of elements and $c$ be the number of cycles in the permutation. As soon as we have $n$ cycles, the permutation is sorted. So we need $n$ - $c$ transpositions.
The expected number of cycles in a permutation is $H_n$, the $n$-th harmonic number. This makes the expected minimum number of transpositions to sort a permutation equal to $n - H_n$.