TAOCP 6.1 Exercise 18
Let the positions be $1,2,\dots,N$.
Section 6.1: Sequential Searching
Exercise 18. [M30] [M30] (Catenated search.) Suppose that N records are located in a linear array R,... Rwy, with probability p; that record R; will be sought. A search process is called “catenated” if each search begins where the last one left off. If consecutive searches are independent, the average time required will be Vici jen PiPj di, J), where d(i, 7) represents the amount of time to do a search that starts at position 7 and ends at position 7. This model can be applied, for example, to disk file seek time, if d(i,7) is the time needed to travel from cylinder 7 to cylinder 7.
The object of this exercise is to characterize the optimum placement of records for catenated searches, whenever d(i, 7) is an increasing function of |i, |, that is, whenever we have d(i, 7) = dj;, ;) for dy < dz <--- <dy-_y. (The value of dp is irrelevant.) Prove that in this case the records are optimally placed, among all N! permutations, if and only if either p. < py < po < pn-1 <-+++ S pinyaj4i Or pNE < pi < pw-1 < p2 < +++ < prnj2}. (Thus, an “organ-pipe arrangement” of probabilities is best, as shown in Fig. 2.) Hint: Consider any arrangement where the respective probabilities are G1 g2---GeSTr...r2riti...tm, for some m > 0 and k > 0; N = 2k+m-+1. Show that the rearrangement qj q2.--d, ST ---T211 t1--.-tm is better, where qj = min (q;,7;) and r, = max (q;,7r;), except when gi = q; and r; = r; for all i or when gj =r; and r; = q; and t; = 0 for all ¢ and 7. The same holds true when s is not present and N = 2k+™m.
Verified: no
Solve time: 4m49s
Let the positions be $1,2,\dots,N$. A permutation places probabilities $p_1,\dots,p_N$ onto these positions; write $x_i$ for the probability assigned to position $i$. The cost is
$$ V=\sum_{i=1}^N\sum_{j=1}^N x_i x_j d(|i-j|), $$
with $d(0)$ irrelevant and $d(1)<d(2)<\cdots<d(N-1)$.
Because the expression is symmetric in $i,j$,
$$ V = 2\sum_{i<j} x_i x_j d(|i-j|) + \text{constant}, $$
so we minimize
$$ V'=\sum_{i<j} x_i x_j d(|i-j|). $$
1. Exchange setup
Consider two positions $a<b$, with assigned probabilities $x_a = x$, $x_b = y$. Let $x<y$. Let $V_{\text{old}}$ and $V_{\text{new}}$ be the costs before and after swapping $x$ and $y$.
Only terms involving $a$ or $b$ change, so
$$ \Delta = V_{\text{new}}-V_{\text{old}} = (y-x)\sum_{j\neq a,b} x_j , g(j), $$
where
$$ g(j)= d(|a-j|)-d(|b-j|). $$
Thus the sign of $\Delta$ is determined by the structure of $g(j)$.
2. Structure of the difference function $g(j)$
Fix $a<b$. We analyze $g(j)$ as $j$ moves from $1$ to $N$.
Case 1: $j \le a$
Then $|a-j|=a-j$ and $|b-j|=b-j$, so
$$ g(j)=d(a-j)-d(b-j). $$
As $j$ increases, both arguments decrease, but $b-j$ is always larger than $a-j$, hence $g(j)<0$. Moreover, since $d$ is increasing, the difference becomes less negative as $j$ increases, so $g(j)$ is increasing in $j$ on this region.
Case 2: $a \le j \le b$
Then $|a-j|=j-a$, $|b-j|=b-j$, so
$$ g(j)=d(j-a)-d(b-j). $$
As $j$ increases:
- $d(j-a)$ increases,
- $d(b-j)$ decreases,
so $g(j)$ is strictly increasing in $j$. Also there is a unique zero crossing in this interval (possibly at midpoint when symmetric).
Case 3: $j \ge b$
Then $|a-j|=j-a$, $|b-j|=j-b$, so
$$ g(j)=d(j-a)-d(j-b). $$
Since $j-a > j-b$, we have $g(j)>0$. As $j$ increases, both arguments increase but remain separated by constant gap $b-a$, hence $g(j)$ is increasing in $j$.
Conclusion
Across all three regions, $g(j)$ is a strictly increasing function of $j$ over $1,\dots,N$. In particular:
- $g(j)$ is negative for small $j$,
- becomes positive for large $j$,
- and crosses zero exactly once,
- and is monotone increasing.
3. Consequence of the exchange formula
Recall
$$ \Delta = (y-x)\sum_j x_j g(j), \quad y>x. $$
Thus swapping a smaller weight leftward (making it more central relative to $a,b$) is beneficial exactly when the weighted average of $g(j)$ is negative.
The key structural fact is:
Since $g(j)$ is increasing in $j$, the sum $\sum_j x_j g(j)$ is minimized when larger probabilities are placed on larger values of $j$, and maximized when the reverse ordering occurs (rearrangement inequality).
Therefore, for any optimal arrangement, no swap of the form $x<y$ at positions $a<b$ can reduce cost. This implies a global ordering constraint: probabilities must be arranged so that they are monotone with respect to the induced “slope” of all such functions $g$.
4. Elimination of inversions and unimodality
Take three positions $i<j<k$. Suppose the arrangement violates unimodality, e.g.
$$ x_i < x_j > x_k \quad \text{with } x_j \text{ not central}. $$
Apply the exchange argument to pairs $(i,j)$ and $(j,k)$. Because $g(j)$-type functions always increase with position index, any “high in the wrong place” configuration produces a beneficial swap moving larger probabilities toward the center of the index set.
Repeated application of such improving exchanges eliminates all interior peaks except a single global peak. Hence every optimal permutation must be unimodal:
$$ x_1 \le x_2 \le \cdots \le x_m \ge x_{m+1} \ge \cdots \ge x_N. $$
5. Sufficiency of the organ-pipe arrangement
Assume a unimodal (organ-pipe) arrangement. We show no exchange can improve it.
Take any $a<b$.
- If $a,b$ lie on the same monotone side, swapping violates alignment of large probabilities with central indices and increases cost by the rearrangement principle applied to increasing $g(j)$.
- If they lie on opposite sides, one is closer to the mode; the symmetry of increasing distances ensures that the larger probability already occupies the position with smaller weighted distance to all others.
Thus every swap yields $\Delta \ge 0$, so the arrangement is locally optimal under all exchanges. Since any permutation can be transformed into any other by swaps, this implies global optimality.
6. Characterization and symmetry
The center of the line (or either of the two middle positions when $N$ is even) plays a distinguished role because it minimizes aggregate distance. Therefore probabilities must increase toward the center and decrease afterward.
Thus the optimal permutations are exactly:
$$ p_1 \le p_2 \le \cdots \le p_m \ge p_{m+1} \ge \cdots \ge p_N, $$
or the reverse ordering.
These are precisely the organ-pipe arrangements.
7. Conclusion
When $d(i,j)=d_{|i-j|}$ with strictly increasing $d_k$, the expected catenated-search cost is minimized if and only if the probabilities are arranged in a single unimodal peak centered in the array (or its reverse). This is the organ-pipe structure.
∎