Binomial Searching for a Random Number of Multinomially Hidden Objects

Suppose N objects are hidden in m boxes where m is known and N is unknown; for example, suppose that we are hunting for defects (objects) in a system having several components (boxes). Let p = (p 1 , p 2 , ...) denote the probability distribution of N where p n = P(N = n). The objects are independently placed in the boxes such that the probability that any particular object is placed in box j is \pi j . Each time box j is searched we pay cost c j > 0, and if x objects are in box j when it is about to be searched, the distribution of the number of objects removed is binomial with parameters x and \alpha j . The numbers \alpha 1 , ..., \alpha m and costs c 1 , ..., c m are known and the initial state (p, \pi ) is given where \pi = (\pi 1 , ..., \pi m ). Let T be the (random) total cost required to find all the objects. A major result is that to minimize the expectation E(T) when in state (p, \pi ) where p is positive-Poisson with parameter \lambda > 0 (P n = e -\lambda \lambda n /(n!(1 - e -\lambda ) for n = 1, 2, ...), it is optimal to search a box with maximal value of [exp(\lambda j \pi j \lambda) - 1]/c j . Results are obtained for problems such as minimizing E(1 - e -T ) when is positive-Poisson or minimizing a utility function of the total number of searches.