Urn sampling distributions giving alternate correspondences between two optimal stopping problems. (September 2016) - Tamaki, Mitsushi
Abstract: The best-choice problem and the duration problem, known as versions of the secretary problem, are concerned with choosing an object from those that appear sequentially. Let ( B, p) denote the best-choice problem and ( D, p) the duration problem when the total number N of objects is a bounded random variable with prior p=( p 1, p 2, ..., p n ) for a known upper bound n . Gnedin (2005) discovered the correspondence relation between these two quite different optimal stopping problems. That is, for any given prior p, there exists another prior q such that ( D, p) is equivalent to ( B, q). In this paper, motivated by his discovery, we attempt to find the alternate correspondence {p ( m ), m ≥0}, i.e. an infinite sequence of priors such that ( D, p ( m -1) ) is equivalent to ( B, p ( m ) ) for all m ≥1, starting with p (0) =(0, ..., 0, 1). To be more precise, the duration problem is distinguished into ( D 1, p) or ( D 2, p), referred to as model 1 or model 2, depending on whether the planning horizon is N or n . The aforementioned problem is model 1. For model 2 as well, we can find the similar alternate correspondence {p [ m ], m ≥ 0}. We treat both the no-information model and the full-information model and examine the limiting behaviors of their optimal rules and optimal values related to the alternate correspondences as n →∞. A generalization of the no-information model is given. It is worth mentioning that the alternate correspondences for model 1 and model 2 are respectively related to the urn sampling models without replacement and with replacement.