TAOCP 6.1 Exercise 13

Exercise 13. [M27] Use (17) to evaluate $\widetilde C_N$ for the wedge-shaped probability distribution (6).

Verified: no
Solve time: 8m14s

Setup

The wedge-shaped probability distribution (6) is [ p_1 = Nc,; p_2 = (N-1)c,; \dots,; p_N = c,\qquad c = \frac{2}{N(N+1)}. ]

Equation (17) (derived in Exercise 11(c)) gives the limiting average number of comparisons for the move‑to‑front self‑organizing file: [ \widetilde C_N = 1 + \sum_{1\le i<j\le N} \frac{2p_i p_j}{p_i+p_j}. ]

Solution

Substitute (p_i = (N+1-i)c). Let (a = N+1-i) and (b = N+1-j); then (1\le b < a \le N) and [ \frac{p_i p_j}{p_i+p_j} = \frac{ab,c^2}{(a+b)c} = c,\frac{ab}{a+b}. ] Hence [ \widetilde C_N = 1 + 2c \sum_{1\le b<a\le N} \frac{ab}{a+b}. ] Define (S_N = \sum_{1\le b<a\le N} \frac{ab}{a+b}). We evaluate (S_N) by a recurrence. For (N\ge 2), [ S_N = S_{N-1} + \sum_{b=1}^{N-1} \frac{N b}{N+b}. ] Writing (\frac{b}{N+b} = 1 - \frac{N}{N+b}) gives [ \sum_{b=1}^{N-1} \frac{N b}{N+b} = N(N-1) - N^2 \sum_{b=1}^{N-1} \frac{1}{N+b} = N(N-1) - N^2\bigl(H_{2N-1} - H_N\bigr). ] With (S_1 = 0), summing from (k=2) to (N) yields [ S_N = \sum_{k=2}^N k(k-1) - \sum_{k=2}^N k^2\bigl(H_{2k-1} - H_k\bigr). ] The first sum is [ \sum_{k=1}^N k(k-1) = \frac{N(N^2-1)}{3}. ] For the second sum we use the known identities [ \sum_{k=1}^N k^2 H_k = \frac{N(N+1)(2N+1)}{6} H_N - \frac{N(N-1)(4N+1)}{36}, ] [ \sum_{k=1}^N k^2 H_{2k-1} = \frac{N(N+1)(2N+1)}{6} H_{2N} - \frac{N(8N^2+15N+13)}{72}. ] Subtracting, [ \sum_{k=1}^N k^2(H_{2k-1} - H_k) = \frac{N(N+1)(2N+1)}{6} (H_{2N} - H_N) - \frac{N(7N+5)}{24}. ] Therefore [ S_N = \frac{N(N^2-1)}{3} - \frac{N(N+1)(2N+1)}{6} (H_{2N} - H_N) + \frac{N(7N+5)}{24} = \frac{N(8N^2+7N-3)}{24} - \frac{N(N+1)(2N+1)}{6} (H_{2N} - H_N). ]

Now (2c = \frac{4}{N(N+1)}), so [ \widetilde C_N = 1 + \frac{4}{N(N+1)} S_N = 1 + \frac{4}{N(N+1)}\left[ \frac{N(8N^2+7N-3)}{24}

\frac{N(N+1)(2N+1)}{6} (H_{2N} - H_N) \right]. ] Simplifying, [ \widetilde C_N = 1 + \frac{8N^2+7N-3}{6(N+1)} - \frac{2(2N+1)}{3} (H_{2N} - H_N) = \frac{8N^2+13N+3}{6(N+1)} - \frac{2(2N+1)}{3} (H_{2N} - H_N). ] An equivalent form is [ \widetilde C_N = \frac{8N+5}{6} - \frac{1}{3(N+1)} - \frac{2(2N+1)}{3} (H_{2N} - H_N). ]

\boxed{\widetilde C_N = \dfrac{8N^2+13N+3}{6(N+1)} - \dfrac{2(2N+1)}{3} \bigl(H_{2N} - H_N\bigr)}

Verification

Direct computation for small (N) matches the formula:

(N=1): (\frac{24}{12} - 2(H_2-H_1) = 2 - 2(0.5) = 1).
(N=2): (\frac{61}{18} - \frac{10}{3}(H_4-H_2) = \frac{61}{18} - \frac{35}{18} = \frac{13}{9}).
(N=3): (\frac{114}{24} - \frac{14}{3}(H_6-H_3) = \frac{57}{12} - \frac{518}{180} = \frac{337}{180}).
(N=4): (\frac{183}{30} - 6(H_8-H_4) = \frac{61}{10} - \frac{533}{140} = \frac{321}{140}).

All agree with the values obtained by summing the definition of (\widetilde C_N) directly. ∎