What is the expected value of this formula?

Question

Let $Π = (π_1,π_2,...,π_n)$ be a random permutation of {1, 2,..., n}.
What is the expected value of $$ \frac{1}{n} \sum_{i=1}^n |\pi_i-i|? $$

Answer 1

Linearity of expectation is your friend: $$ \mathbb{E}\left[\frac{1}{n}\sum_{i=1}^{n}\lvert \pi_i-i\rvert\right]=\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}\lvert\pi_i-i\rvert. $$ So, you just have to figure out these intermediate expectations. To that end, note that $$ \mathbb{E}\lvert \pi_i-i\vert=\sum_{k=1}^{n}\lvert k-i\rvert P(\pi_i=k). $$ What is $P(\pi_i=k)$? This is a simple matter of counting the number of permutations which map $i\mapsto k$ for a fixed $i$ and $k$ (which won't depend on either $i$ or $k$, as it happens). Once you've done this, it is a matter of manipulating the sum.

Can you take it from here?