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 \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 ₁, ..., \alpha _m and costs c₁, ..., c_m are known and the initial state (p, \pi ) is given where \pi = (\pi ₁, ..., \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!(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.