Exercise 11. [M30] [M30] The purpose of this exercise is to analyze the limiting behavior of a selforganizing file with the move-to-front heuristic. First we need to define some notation:

Let fm(@1, U2,-..,%m) be the infinite sum of all distinct ordered products 2j, Gig... Li, such that 1 < #41,...,%% < m, where each of 41, %2,...,%m appears in every term. For example,

j j xy 1 1 fo(a,y) = wv y(a+y)+yVa(a+y)) = ( + ). (x,y) 2 ( ) ( )”) lo-c-y\i-2iny

406 SEARCHING 6.1

Given a set X of n variables {11,...,2n}, let 1 Pom = DY fin(@514-++35m): m= Ye 1Sj1 0 and y < 2’, and it is not immediately clear which condition should be tested first.) Suppose that the testing of condition j costs T; units of time, and that the condition will be true with probability p;, independent of the outcomes of all the other conditions. In what order should we make the tests?

6.1 SEQUENTIAL SEARCHING AOT

coll te.

Pl p2 Py

Fig. 2. An “organ-pipe arrangement” of probabilities minimizes the average seek time in a catenated search.

Verified: yes
Solve time: 2m27s

The reviewer is correct: the proposed solution does not address the problem at all. The correct solution must start from the sequential decision model and derive the optimal ordering rule from the expected cost.

Correct formulation

We have conditions $1,\dots,n$. Each test $i$ costs $T_i$ time units. It is independently true with probability $p_i$.

We test conditions sequentially in some order $\sigma(1),\sigma(2),\dots,\sigma(n)$, stopping at the first condition that is true.

The goal is to minimize the expected total testing time.

Expected cost of a fixed order

For an order $\sigma$, we pay $T_{\sigma(k)}$ only if we reach step $k$, meaning all previous tests were false.

Thus the probability we reach step $k$ is

$$ \prod_{j<k} (1 - p_{\sigma(j)}). $$

So the expected cost is

$$ E(\sigma)

\sum_{k=1}^n T_{\sigma(k)} \prod_{j<k} (1 - p_{\sigma(j)}). $$

Pairwise exchange argument

To determine the optimal order, it suffices to compare two adjacent tests.

Consider two conditions $i$ and $j$, and assume all other tests are fixed before them. Only their relative order matters.

Case 1: $i$ before $j$

Expected cost contribution (ignoring earlier factors) is:

$$ T_i + (1 - p_i)T_j. $$

Case 2: $j$ before $i$

Expected cost contribution is:

$$ T_j + (1 - p_j)T_i. $$

Compare the two orders

We prefer $i$ before $j$ when:

$$ T_i + (1 - p_i)T_j \le T_j + (1 - p_j)T_i. $$

Expand:

$$ T_i + T_j - p_i T_j \le T_j + T_i - p_j T_i. $$

Cancel $T_i + T_j$:

p_i T_j \le - p_j T_i. $$

Multiply by $-1$ (reversing inequality):

$$ p_i T_j \ge p_j T_i. $$

Rearrange:

$$ \frac{p_i}{T_i} \ge \frac{p_j}{T_j}. $$

Optimal ordering rule

Thus, any adjacent inversion where

$$ \frac{p_i}{T_i} < \frac{p_j}{T_j} $$

can be improved by swapping $i$ and $j$.

Therefore, the optimal strategy is:

$$ \boxed{\text{Test conditions in decreasing order of } \frac{p_i}{T_i}.} $$

Conclusion

The expected time is minimized by sorting tests by the ratio of probability of success per unit cost. This follows directly from a pairwise exchange argument and yields a globally optimal ordering.

TAOCP 6.1 Exercise 11