Average distance moved by a permutation

Question

For each $\pi$ permutation of numbers 1 to n, $f(\pi) = \sum_{i=1}^n |\pi_i - i|$. What is the average of $f(\pi)$ on all of the $n=7$ permutations?

Answer 1

Let's do this for a general $n$, instead of $7$.

We have $$E(f(\pi)) = E \left( \sum_{i=1}^n |\pi_i - i| \right).$$ By linearity of expectation, we get

$$ E(f(\pi)) = \sum_{i=1}^n E(|\pi_i - i|). $$

Now $E(|\pi_i - i|)$ of course depends on $i$ and $n$. In particular, we have

$$ E(|\pi_i - i|) = {(i-1) + (i-2) + \cdots + 1 + 0 + 1 + \cdots + (n-i) \over n}. $$

Then we have $(i-1) + (i-2) + \cdots + 1 = i(i-1)/2$ and $1 + 2 + \cdots + (n-i) = (n-i)(n-i+1)/2$. This gives

$$ E(|\pi_i - i|) = {i(i-1)/2 + (n-i)(n-i+1)/2 \over n} $$

Therefore, going back to the initial sum, $$E(f(\pi)) = \sum_{i=1}^n {i(i-1) \over 2n} + \sum_{i=1}^n {(n-i)(n-i+1) \over 2n}.$$

These tw sums are the same since they have the same terms in reverse order, so we get

$$ E(f(\pi)) = 2 \sum_{i=1}^n {i(i-1) \over 2n} = {1 \over n} \sum_{i=1}^n i^2-i$$

Finally we can work out that sum:

$$ {1 \over n} \sum_{i=1}^n (i^2-i) = {1 \over n} (\sum_{i=1}^n i^2 - \sum_{i-1}^n i) = {1 \over n} \left( {n(n+1)(2n+1) \over 6} - {n(n+1) \over 2} \right) = (n+1) \left( {2n+1 \over 6} - {1 \over 2} \right) = {(n+1)(2n-2) \over 6} = {n^2 - 1 \over 3}.$$

The references at https://oeis.org/A062869 appear to be relevant; the statistic computed here is called the "total displacement" of a permutation or "Spearman's disarray".