Urn sampling distributions giving alternate correspondences between two optimal stopping problems. (September 2016)

• Record Type: Journal Article
• Authors: Tamaki, Mitsushi
• Is Part Of: Advances in applied probability. Volume 48:Number 3(2016)
• Page Start: 726
• Page End: 743
• Publication Date: 2016-09
• Subjects: Secretary problem, -- best-choice problem, -- alternate correspondence, -- duration problem, -- Bruss extension; Primary 60G40, -- Secondary 62L15; Probabilities -- Periodicals; Stochastic models -- Periodicals; Electronic journals; Periodicals; 519.2
• DOI: 10.1017/apr.2016.25
• Languages: English
• ISSNs: 0001-8678

Abstract

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.