TAOCP 5.2.1 Exercise 20

Exercise 20. [M22] Show that Theorem K follows from Lemma L.

Verified: no
Solve time: 41m49s

Solution

We first recall the statements of Lemma L and Theorem K from the text.

Lemma L. If a permutation of ({1,2,\ldots,N}) is (h)-ordered (i.e., (K_i \le K_{i+h}) for all (1 \le i \le N-h)), then the number of inversions it contains has the same probability distribution as the sum of (h) independent random variables, each having the distribution of the number of inversions in a random permutation of (N/h) elements.

Theorem K. Suppose the increments (h_{t-1}, h_{t-2}, \ldots, h_0) used by Algorithm D satisfy the divisibility condition
[ h_{t-1} = c_{t-1}h_{t-2},; h_{t-2} = c_{t-2}h_{t-3},; \ldots,; h_1 = c_1h_0,\qquad h_0 = 1. ] Then the average number of moves (B) performed by Algorithm D is [ \frac{1}{4}\sum_{s=0}^{t-1}\Bigl(\frac{N^2}{h_s} - N\Bigr)

\frac{1}{4}\sum_{s=1}^{t-1}\Bigl(\frac{N^2}{h_s} - N,\frac{h_{s-1}}{h_s}\Bigr). ]

Proof that Theorem K follows from Lemma L

The algorithm makes (t) passes, using the increments in decreasing order: first (h_{t-1}), then (h_{t-2}), …, finally (h_0 = 1).
Let (B_s) be the number of moves in the pass that uses increment (h_s) ((0 \le s \le t-1)).
Then (B = \sum_{s=0}^{t-1} B_s). We evaluate (\mathbb{E}[B_s]) for each pass.

Pass (s = t-1) (the first pass, increment (h_{t-1})).
The input permutation is uniformly random. The pass sorts each of the (h_{t-1}) subsequences (subfiles) of step (h_{t-1}); the number of moves is exactly the total number of inversions inside those subfiles.
Because the whole permutation is random, the (h_{t-1}) subfiles are independent random permutations of (N/h_{t-1}) elements. By Lemma L (with (h = h_{t-1})), the total number of moves (B_{t-1}) is distributed as the sum of (h_{t-1}) independent copies of the inversion number of a random permutation of (N/h_{t-1}) elements. Hence [ \mathbb{E}[B_{t-1}] = h_{t-1}\cdot\frac{(N/h_{t-1})^2 - (N/h_{t-1})}{4} = \frac{1}{4}\Bigl(\frac{N^2}{h_{t-1}} - N\Bigr). ]

Pass (s < t-1) (increment (h_s)).
Before this pass the permutation is (h_{s+1})-ordered (this is an easy induction using the divisibility condition and the fact that the first pass leaves the permutation (h_{t-1})-ordered).
We have (h_{s+1} = c,h_s) with (c = c_{s+1} > 1). The pass sorts each of the (h_s) subfiles of length (m = N/h_s). The moves (B_s) equal the total number of inversions inside those (h_s) subfiles.

Consider one particular (h_s)-subfile. Because the whole permutation is (h_{s+1})-ordered, this subfile consists of (c) sorted lists, each of length (L = N/h_{s+1} = m/c). These (c) lists are exactly the (h_{s+1})-subfiles that fall inside the chosen (h_s)-subfile; they are independent and their elements form a uniformly random partition of a uniformly random (m)-subset of ({1,\ldots,N}) into (c) ordered subsets of size (L). After sorting each of the (c) lists (which is already true by (h_{s+1})-ordering), the (h_s)-subfile is the fixed interleaving [ A^{(1)}_1,; A^{(2)}_1,; \ldots,; A^{(c)}_1,; A^{(1)}_2,; \ldots,; A^{(c)}_2,; \ldots,; A^{(1)}_L,; \ldots,; A^{(c)}_L, ] where (A^{(j)}_1 < A^{(j)}_2 < \cdots < A^{(j)}_L) is the (j)-th sorted list.

The number of inversions in this interleaving is exactly the number of inversions in a random (c)-ordered permutation of (m) elements. To see this, take a random permutation of (m) elements and sort its (c) subfiles of step (c); the resulting permutation is uniformly distributed over all (c)-ordered permutations of (m) elements, and its number of inversions equals the number of inversions between the (c) sorted lists. By Lemma L (applied with (h = c) and (N = m)), this inversion number is distributed as the sum of (c) independent copies of the inversion number of a random permutation of (m/c = L) elements. Therefore its expected value is [ c \cdot \frac{L^2 - L}{4} = \frac{m^2/c - m}{4}. ]

Alternatively, we can compute the expected inversions in one (h_s)-subfile directly: it is the total expected inversions in a random permutation of (m) elements minus the expected inversions within the (c) sorted lists. The total expected inversions in a random permutation of (m) is ((m^2-m)/4); the expected inversions within the (c) lists (if they were randomly ordered) would be (c\cdot(L^2-L)/4). Since the lists are actually sorted, those inversions are absent, leaving [ \frac{m^2-m}{4} - \frac{c(L^2-L)}{4} = \frac{m^2-m}{4}\Bigl(1-\frac{1}{c}\Bigr) = \frac{m^2-m}{4}\cdot\frac{c-1}{c}. ] Both methods give the same expectation.

Since there are (h_s) such subfiles, all identically distributed, the expected moves for pass (s) are [ \mathbb{E}[B_s] = h_s \cdot \frac{1}{4}\Bigl(\frac{N^2}{h_s^2} - \frac{N}{h_s}\Bigr)\cdot\frac{c-1}{c} = \frac{1}{4}\Bigl(\frac{N^2}{h_s} - N\Bigr)\Bigl(1 - \frac{h_s}{h_{s+1}}\Bigr), ] where we used (c = h_{s+1}/h_s).

Summing the passes.
For uniformity we define (h_t = \infty) (so that (h_{t-1}/h_t = 0)). Then the formula above also covers the first pass (s = t-1). Hence [ \mathbb{E}[B] = \frac{1}{4}\sum_{s=0}^{t-1} \Bigl(\frac{N^2}{h_s} - N\Bigr)\Bigl(1 - \frac{h_s}{h_{s+1}}\Bigr). ]

Expanding the product, [ \mathbb{E}[B] = \frac{1}{4}\sum_{s=0}^{t-1}\Bigl(\frac{N^2}{h_s} - N\Bigr)

\frac{1}{4}\sum_{s=0}^{t-1}\Bigl(\frac{N^2}{h_s} - N\Bigr)\frac{h_s}{h_{s+1}}. ] For (s = t-1) the second term is zero because (h_{t-1}/h_t = 0). In the remaining terms (s = 0,\ldots,t-2) we have [ \Bigl(\frac{N^2}{h_s} - N\Bigr)\frac{h_s}{h_{s+1}} = \frac{N^2}{h_{s+1}} - N,\frac{h_s}{h_{s+1}}. ] Shifting the index (k = s+1) (so (k = 1,\ldots,t-1)) gives [ \mathbb{E}[B] = \frac{1}{4}\sum_{s=0}^{t-1}\Bigl(\frac{N^2}{h_s} - N\Bigr)
\frac{1}{4}\sum_{k=1}^{t-1}\Bigl(\frac{N^2}{h_k} - N,\frac{h_{k-1}}{h_k}\Bigr), ] which is exactly the statement of Theorem K. ∎