TAOCP 5.2.1 Exercise 7

Let $a_1 a_2 \dots a_n$ be a random permutation of ${1,2,\dots,n}$.

taocpmathematicsalgorithmsvolume-3math-medium

Section 5.2.1: Sorting by Insertion

Exercise 7. [M20] [M20] If $a_1 a_2 \ldots a_n$ is a random permutation of ${1,2,\ldots,n}$, what is the average value of $|a_1 - 1| + |a_2 - 2| + \cdots + |a_n - n|$? (This is $n$ times the average net distance traveled by a record during a sorting process.)

Verified: yes
Solve time: 14m42s

Solution

Let $a_1 a_2 \dots a_n$ be a random permutation of ${1,2,\dots,n}$. Define

$$ X = |a_1 - 1| + |a_2 - 2| + \cdots + |a_n - n|. $$

By linearity of expectation,

$$ \mathbb{E}[X] = \mathbb{E}[|a_1 - 1|] + \mathbb{E}[|a_2 - 2|] + \cdots + \mathbb{E}[|a_n - n|]. $$

Consider a single term $\mathbb{E}[|a_j - j|]$. Since $a_j$ is uniformly distributed over ${1,2,\dots,n}$,

$$ \mathbb{E}[|a_j - j|] = \frac{1}{n} \sum_{k=1}^{n} |k - j|. $$

Split the sum into two parts: $k < j$ and $k \ge j$. Then

$$ \sum_{k=1}^{n} |k - j| = \sum_{k=1}^{j-1} (j - k) + \sum_{k=j+1}^{n} (k - j). $$

The first sum is an arithmetic series:

$$ \sum_{k=1}^{j-1} (j - k) = 1 + 2 + \cdots + (j-1) = \frac{(j-1) j}{2}. $$

The second sum is

$$ \sum_{k=j+1}^{n} (k - j) = 1 + 2 + \cdots + (n-j) = \frac{(n-j)(n-j+1)}{2}. $$

Hence

$$ \mathbb{E}[|a_j - j|] = \frac{(j-1)j/2 + (n-j)(n-j+1)/2}{n} = \frac{j(j-1) + (n-j)(n-j+1)}{2n}. $$

The total expectation is

$$ \mathbb{E}[X] = \sum_{j=1}^{n} \frac{j(j-1) + (n-j)(n-j+1)}{2n} = \frac{1}{2n} \sum_{j=1}^{n} \bigl(j(j-1) + (n-j)(n-j+1)\bigr). $$

Compute the sum of the first term:

$$ \sum_{j=1}^{n} j(j-1) = \sum_{j=1}^{n} (j^2 - j) = \frac{n(n+1)(2n+1)}{6} - \frac{n(n+1)}{2} = \frac{n(n+1)(2n+1 - 3)}{6} = \frac{n(n+1)(2n-2)}{6} = \frac{n(n+1)(n-1)}{3}. $$

Compute the sum of the second term:

$$ \sum_{j=1}^{n} (n-j)(n-j+1) = \sum_{k=0}^{n-1} k(k+1), \quad \text{where } k = n-j. $$

Then

$$ \sum_{k=0}^{n-1} k(k+1) = \sum_{k=0}^{n-1} (k^2 + k) = \frac{(n-1)n(2n-1)}{6} + \frac{(n-1)n}{2} = \frac{(n-1)n(2n-1 + 3)}{6} = \frac{(n-1)n(2n+2)}{6} = \frac{(n-1)n(n+1)}{3}. $$

Adding the two sums gives

$$ \sum_{j=1}^{n} \bigl(j(j-1) + (n-j)(n-j+1)\bigr) = \frac{n(n+1)(n-1)}{3} + \frac{n(n+1)(n-1)}{3} = \frac{2 n(n+1)(n-1)}{3}. $$

Therefore

$$ \mathbb{E}[X] = \frac{1}{2n} \cdot \frac{2 n(n+1)(n-1)}{3} = \frac{(n+1)(n-1)}{3} = \frac{n^2 - 1}{3}. $$

Hence the average value of $|a_1 - 1| + \cdots + |a_n - n|$ is

$$ \boxed{\frac{n^2 - 1}{3}}. $$

This completes the proof.

∎