TAOCP 6.1 Exercise 16
We want to test conditions \(1,\ldots,n\) in some order \(\sigma\) (a permutation of \(\{1,\ldots,n\}\)).
Section 6.1: Sequential Searching
Exercise 16. [M22] (H. Riesel.) We often need to test whether or not $n$ given conditions are all simultaneously true. (For example, we may want to test whether both $x>0$ and $y<z^2$, and it is not immediately clear which condition should be tested first.) Suppose that the testing of condition $j$ costs $T_j$ units of time, and that the condition will be true with probability $p_j$, independent of the outcomes of all the other conditions. In what order should we make the tests?
6.1 SEQUENTIAL SEARCHING 407
p1 p2 pN
Fig. 2. An “organ-pipe arrangement” of probabilities minimizes the average seek time in a catenated search.
Verified: no
Solve time: 1m12s
Solution
We want to test conditions (1,\ldots,n) in some order (\sigma) (a permutation of ({1,\ldots,n})). We stop when a condition is found false, or after all are found true. Testing condition (j) takes (T_j) time units, and it is true with probability (p_j), independently of the other conditions.
Let the order be (\sigma(1),\sigma(2),\ldots,\sigma(n)). The probability that we reach test (k) is the product of the probabilities that the first (k-1) conditions are true: (\prod_{i=1}^{k-1} p_{\sigma(i)}) (with the empty product equal to (1)). The expected time is therefore
[ E(\sigma) = \sum_{k=1}^n T_{\sigma(k)} \prod_{i=1}^{k-1} p_{\sigma(i)}. ]
To find the optimal permutation, consider any two adjacent conditions in the sequence, say (i) immediately followed by (j), with the product of the (p)'s of all preceding conditions equal to (P). The contribution of this pair to (E) is
[ P T_i + P p_i T_j. ]
If we swap them, the contribution becomes
[ P T_j + P p_j T_i. ]
The difference (original minus swapped) is
[ P\bigl(T_i + p_i T_j - T_j - p_j T_i\bigr) = P\bigl(T_i(1-p_j) - T_j(1-p_i)\bigr). ]
Hence, placing (i) before (j) is better (or equal) exactly when
[ T_i(1-p_j) \le T_j(1-p_i). ]
If (1-p_i>0) and (1-p_j>0), this is equivalent to
[ \frac{T_i}{1-p_i} \le \frac{T_j}{1-p_j}. ]
If (1-p_i = 0) (i.e., (p_i=1)) and (1-p_j>0), the left‑hand side (T_i(1-p_j)) is positive while the right‑hand side (T_j(1-p_i)=0), so the inequality fails; thus (j) should precede (i). This is consistent with interpreting the ratio (T/(1-p)) as (+\infty) when (p=1). If both (p_i=p_j=1), the difference is (0) and the order does not matter.
Therefore, any permutation that contains an adjacent pair violating the nondecreasing order of (T_j/(1-p_j)) (with the convention that a zero denominator gives (+\infty)) can be improved by swapping that pair. Since the expected cost is a sum of such adjacent contributions, a globally optimal permutation is obtained by sorting the conditions according to the key
[ \frac{T_j}{1-p_j}, ]
with the understanding that (T_j/(1-p_j) = +\infty) when (p_j = 1).
Answer: Test the conditions in nondecreasing order of (T_j/(1-p_j)) (with conditions that are certainly true, (p_j=1), placed last).
\boxed{\text{Sort by nondecreasing } \dfrac{T_j}{1-p_j} \text{ (treat } 1-p_j=0 \text{ as } +\infty\text{).}}
This completes the proof.
∎