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₁, p₂, …) 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 α₁, …, α_m and costs c₁, …, c_m are known and the initial state (p, π) is given where π = (π₁, …, π_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!(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.