Binomial Searching for a Random Number of Multinomially Hidden Objects
George Kimeldorf, Furman H. Smith · Management Science · 1979
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 π 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 α j . The numbers α 1 , …, α m and costs c 1 , …, c m are known and the initial state (p, π) is given where π = (π 1 , …, π 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, π) where p is positive-Poisson with parameter λ > 0 (P n = e −λ λ n /(n!(1 − e −λ ) for n = 1, 2, …), it is optimal to search a box with maximal value of [exp(λ j π j λ) − 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.