TAOCP 6.1 Exercise 12

Equation (17) 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}.

taocpmathematicsalgorithmsvolume-3math-medium

Section 6.1: Sequential Searching

Exercise 12. [M23] Use (17) to evaluate the average number of comparisons needed to search the self-organizing file when the search keys have the binary probability distribution (5).

Verified: no
Solve time: 2m37s

Solution

Equation (17) 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}. \tag{17} ]

The binary probability distribution (5) is

[ p_i = \frac{1}{2^i}\quad (1\le i\le N-1),\qquad p_N = \frac{1}{2^{N-1}}. ]

Substitute these probabilities into (17). Let

[ S = \sum_{i<j} \frac{2p_i p_j}{p_i+p_j}. ]

We split the sum according to whether (j=N) or (j<N).

Case 1: (1\le i<j\le N-1).
Here (p_i=2^{-i}), (p_j=2^{-j}). The term becomes

[ \frac{2\cdot 2^{-i}2^{-j}}{2^{-i}+2^{-j}} = \frac{2^{1-i}}{2^{j-i}+1}. ]

Setting (k=j-i;(k\ge1)), for a fixed (i) the index (k) runs from (1) to (N-1-i). Summing over (i) gives

[ \sum_{i=1}^{N-2}\sum_{k=1}^{N-1-i} \frac{2^{1-i}}{2^k+1}. ]

Case 2: (1\le i\le N-1), (j=N).
Here (p_i=2^{-i}), (p_N=2^{-(N-1)}). The term is

[ \frac{2\cdot 2^{-i}2^{-(N-1)}}{2^{-i}+2^{-(N-1)}} = \frac{2^{1-i}}{2^{N-1-i}+1}. ]

Let (m=N-1-i); then (i=N-1-m) and (m) runs from (0) to (N-2). The term becomes

[ \frac{2^{m-N+2}}{2^m+1}, ]

so the contribution of this case is

[ \sum_{m=0}^{N-2} \frac{2^{m+2-N}}{2^m+1}. ]

Now combine the two cases. Set (M=N-1). Reorder the double sum of Case 1:

[ \sum_{i=1}^{M-1} 2^{1-i} \sum_{k=1}^{M-i} \frac{1}{2^k+1} = \sum_{k=1}^{M-1} \frac{1}{2^k+1} \sum_{i=1}^{M-k} 2^{1-i}. ]

The inner sum is (\sum_{i=1}^{M-k} 2^{1-i} = 2(1-2^{-(M-k)}) = 2 - 2^{1-M+k}). Hence the double sum equals

[ \sum_{k=1}^{M-1} \frac{2}{2^k+1} ;-; \sum_{k=1}^{M-1} \frac{2^{1-M+k}}{2^k+1}. ]

The second sum here is exactly the negative of the part of Case 2 with (m\ge 1), because Case 2 gives

[ \sum_{m=0}^{M-1} \frac{2^{m+1-M}}{2^m+1} = 2^{-M} + \sum_{m=1}^{M-1} \frac{2^{m+1-M}}{2^m+1}. ]

Adding the two cases, the terms with indices (\ge1) cancel, leaving

[ S = \sum_{k=1}^{M-1} \frac{2}{2^k+1} + 2^{-M}. ]

Returning to (N) ((M=N-1)),

[ S = \sum_{k=1}^{N-2} \frac{2}{2^k+1} + 2^{1-N}. ]

Therefore the average number of comparisons is

[ \widetilde C_N = 1 + S = 1 + 2^{1-N} + \sum_{k=1}^{N-2} \frac{2}{2^k+1}. ]

(For (N=2) the sum is empty and (\widetilde C_2 = 3/2); for (N=3), (\widetilde C_3 = 23/12); both agree with direct evaluation of (17).)

[ \boxed{\widetilde C_N = 1 + 2^{1-N} + \sum_{k=1}^{N-2} \frac{2}{2^k+1}} ]

This completes the proof. ∎