Hostname: page-component-586b7cd67f-2brh9 Total loading time: 0 Render date: 2024-11-27T20:04:15.396Z Has data issue: false hasContentIssue false
  • English
  • Français

Optimal Stopping Rule for the No-Information Duration Problem with Random Horizon

Part of: Stochastic processes Sequential methods

Published online by Cambridge University Press:  04 January 2016

Mitsushi Tamaki
Mitsushi Tamaki*
Affiliation:
Aichi University
*
∗ Postal address: Department of Business Administration, Aichi University, Nagoya Campus, Hiraike 4-60-6, Nakamura, Nagoya, Aichi 453-8777, Japan. Email address: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

As a version of the secretary problem, Ferguson, Hardwick and Tamaki (1992) considered an optimal stopping problem called the duration problem. The basic duration problem is the classical duration problem, in which the objective is to maximize the time of possession of a relatively best object when a known number of rankable objects appear in random order. In this paper we generalize this classical problem in two directions by allowing the number N (of available objects) to be a random variable with a known upper bound n and also allowing the objects to appear in accordance with Bernoulli trials. Two models can be considered for our random horizon duration problem according to whether the planning horizon is N or n. Since the form of the optimal rule is in general complicated, our main concern is to give to each model a sufficient condition for the optimal rule to be simple. For N having a uniform, generalized uniform, or curtailed geometric distribution, the optimal rule is shown to be simple in the so-called secretary case. The asymptotic results, as n → ∞, will also be given for these priors.

Keywords

Secretary problembest-choice problemBruss' odds theoremsimple rulecandidaterelative rankBernoulli trial

MSC classification

Primary: 60G40: Stopping times; optimal stopping problems; gambling theory 62L15: Optimal stopping
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 45 , Issue 4 , December 2013 , pp. 1028 - 1048
Copyright
© Applied Probability Trust 

References

Bruss, F. T. (2000). Sum the odds to one and stop. Ann. Prob. 28, 1384–1391.Google Scholar
Dynkin, E. B. and Yushkevich, A. A. (1969). Markov Processes: Theorems and Problems. Plenum Press, New York.Google Scholar
Ferguson, T. S. (2008). The sum-the-odds theorem with application to a stopping game of Sakaguchi. Preprint.Google Scholar
Ferguson, T. S., Hardwick, J. P. and Tamaki, M. (1992). Maximizing the duration of owning a relatively best object. In Strategies for Sequential Search and Selection in Real Time (Contemp. Math. 125), American Mathematical Society, Providence, RI, pp. 37–57.Google Scholar
Gilbert, J. P. and Mosteller, F. (1966). Recognizing the maximum of a sequence. J. Amer. Statist. Assoc. 61, 35–73.CrossRefGoogle Scholar
Gnedin, A. V. (2004). Best choice from the planar Poisson process. Stoch. Process. Appl. 111, 317–354.CrossRefGoogle Scholar
Gnedin, A. V. (2005). Objectives in the best-choice problems. Sequent. Anal. 24, 177–188.Google Scholar
Mazalov, V. V. and Tamaki, M. (2006). An explicit formula for the optimal gain in the full-information problem of owning a relatively best object. J. Appl. Prob. 43, 87–101.Google Scholar
Mucci, A. G. (1973a). Differential equations and optimal choice problem. Ann. Statist. 1, 104–113.Google Scholar
Mucci, A. G. (1973b). On a class of secretary problems. Ann. Prob. 1, 417–427.CrossRefGoogle Scholar
Pearce, C. E. M., Szajowski, K. and Tamaki, M. (2012). Duration problem with multiple exchanges. Numer. Algebra Control Optimization 2, 333–355.Google Scholar
Petruccelli, J. D. (1983). On the best-choice problem when the number of observations is random. J. Appl. Prob. 20, 165–171.Google Scholar
Presman, E. L. and Sonin, I. M. (1972). The best choice problem for a random number of objects. Theory. Prob. Appl. 17, 657–668.Google Scholar
Samuels, S. M. (2004). Why do these quite different best-choice problems have the same solutions? Adv. Appl. Prob. 36, 398–416.Google Scholar
Suchwalko, A. and Szajowski, K. (2002). Non standard, no information secretary problems. Sci. Math. Japonicae 56, 443–456.Google Scholar
Tamaki, M. (2010). Sum the multiplicative odds to one and stop. J. Appl. Prob. 47, 761–777.CrossRefGoogle Scholar
Tamaki, M. (2011). Maximizing the probability of stopping on any of the last m successes in independent Bernoulli trials with random horizon. Adv. Appl. Prob. 43, 760–781.Google Scholar