The Discrete Sequential Search Problem with Nonrandom Cost and Overlook Probabilities

Suppose one object is hidden in the kth of n boxes with probability p(k). The boxes are to be searched sequentially. Associated with the jth search of box k is a cost c(j, k) and a conditional probability q(j, k) that the first j − 1 searches of box k are unsuccessful while the jth search is successful given that the object is hidden in box k.

The problem is to minimize the expected cost of a strategy which at last surely finds the object. Without further assumptions we give necessary and sufficient conditions for the existence of admissible strategies with finite expected cost and the existence of optimal strategies. We give a procedure for the computation of an optimal strategy.