Discrete Sequential Search with Positive Switch Cost

Suppose one object is hidden in one of n boxes according to a known probability distribution p(1), …, p(n). The boxes are to be searched sequentially. The probability of overlooking the object if we search box k and if the object is in box k is denoted by q(k). The cost of a search of box k amounts to c(k). If we decide to search box k directly after box k′ we have to pay some extra cost called switch cost: T(k′, k). The problem is—under some reasonable assumptions—to construct a strategy with minimal expected cost. If T ≡ 0 the problem has a well-known solution. Unfortunately there are many reasons which establish the conjecture that there does not exist an easy construction rule for optimal strategies in the general case. We give necessary and sufficient conditions for the existence of optimal strategies which are ultimately periodic (u.p.). Since we state bounds on the length not only of the transient phase but also of the period of optimal u.p. strategies we may construct these optimal strategies by comparing finitely many strategies (if optimal u.p. strategies exist). We prove some other results to reduce the number of strategies which we have to compare. At last we present a numerical example.