Binomial Searching for a Random Number of Multinomially Hidden Objects

George Kimeldorf and Furman H. Smith
Additional contact information
George Kimeldorf: University of Texas at Dallas
Furman H. Smith: University of Houston, Victoria Campus

Management Science, 1979, vol. 25, issue 11, 1115-1126

Abstract: 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.

Keywords: decision analysis: sequential; dynamic programming: Markov; infinite state (search for similar items in EconPapers)
Date: 1979
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.25.11.1115 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:25:y:1979:i:11:p:1115-1126

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().