Hostname: page-component-586b7cd67f-r5fsc Total loading time: 0 Render date: 2024-11-22T04:38:32.513Z Has data issue: false hasContentIssue false
  • English
  • Français

Sum the Multiplicative Odds to One and Stop

Part of: Stochastic processes

Published online by Cambridge University Press:  14 July 2016

Mitsushi Tamaki
Mitsushi Tamaki*
Affiliation:
Aichi University
*
∗Postal address: Department of Business Administration, Aichi University, Nagoya Campus, 370 Shimizu, Kurozasa, Miyoshi, Aichi 470-0296, 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.

We consider the optimal stopping problem of maximizing the probability of stopping on any of the last m successes of a sequence of independent Bernoulli trials of length n, where m and n are predetermined integers such that 1 ≤ m < n. The optimal stopping rule of this problem has a nice interpretation, that is, it stops on the first success for which the sum of the m-fold multiplicative odds of success for the future trials is less than or equal to 1. This result can be viewed as a generalization of Bruss' (2000) odds theorem. Application will be made to the secretary problem. For more generality, we extend the problem in several directions in the same manner that Ferguson (2008) used to extend the odds theorem. We apply this extended result to the full-information analogue of the secretary problem, and derive the optimal stopping rule and the probability of win explicitly. The asymptotic results, as n tends to ∞, are also obtained via the planar Poisson process approach.

Keywords

Optimal stoppingsecretary problemplanar Poisson processodds theoremnonhomogeneous Poisson processmonotone problemone-stage look-ahead rule

MSC classification

Secondary: 60G40: Stopping times; optimal stopping problems; gambling theory
Type
Research Article
Information
Journal of Applied Probability , Volume 47 , Issue 3 , September 2010 , pp. 761 - 777
Copyright
Copyright © Applied Probability Trust 2010 

References

Arnold, B. C., Barlakrishnan, N. and Nagaraja, H. N. (1998). Records. John Wiley, New York.CrossRefGoogle Scholar
Blom, G., Holst, L. and Sandel, D. (1994). Problems and Snapshots from the World of Probability. Springer, New York.CrossRefGoogle Scholar
Bruss, F. T. (2000). Sum the odds to one and stop. Ann. Prob. 28, 1384–1391.CrossRefGoogle Scholar
Bruss, F. T. (2003). A note on bounds for the odds theorem of optimal stopping. Ann. Prob. 31, 1859–1861.CrossRefGoogle Scholar
Bruss, F. T. and Louchard, G. (2009). The odds algorithm based on sequential updating and its performance. Adv. Appl. Prob. 41, 131–153.CrossRefGoogle Scholar
Bruss, F. T. and Paindaveine, D. (2000). Selecting a sequence of last successes in independent trials. J. Appl. Prob. 37, 389–399.CrossRefGoogle Scholar
Bruss, F. T. and Swan, Y. C. (2009). A continuous-time approach to Robbins' problem of minimizing the expected rank. J. Appl. Prob. 46, 1–18.CrossRefGoogle Scholar
Chow, Y. S., Robbins, H. and Siegmund, D. (1971). Great Expectations: The Theory of Optimal Stopping. Houghton Mifflin, Boston, MA.Google Scholar
Chow, Y. S., Moriguti, S., Robbins, H. and Samuels, S. M. (1964). Optimal selection based on relative rank (the ‘secretary problem’). Israel J. Math. 2, 81–90.CrossRefGoogle Scholar
Dynkin, E. B. (1963). The optimal choice of the instant for stopping a Markov process. Soviet Math. Dokl. 4, 627–629.Google Scholar
Ferguson, T. S. (1989). Who solved the secretary problem? Statist. Sci. 4, 282–289.Google Scholar
Ferguson, T. S. (2006). Optimal Stopping and Applications. Available at http://www.math.ucla.edu/simtom/Stopping/Contents.html.Google Scholar
Ferguson, T. S. (2008). The sum-the-odds theorem with application to a stopping game of Sakaguchi. Preprint.Google Scholar
Frank, A. Q. and Samuels, S. M. (1980). On an optimal stopping problem of Gusein-Zade. Stoch. Process. Appl. 10, 299–311.CrossRefGoogle 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. (1996). On the full information best-choice problem. J. Appl. Prob. 33, 678–687.CrossRefGoogle Scholar
Gnedin, A. V. (2004). Best choice from the planar Poisson process. Stoch. Process. Appl. 111, 317–354.CrossRefGoogle Scholar
Gusein-Zade, S. M. (1966). The problem of choice and the optimal stopping rule for a sequence of independent trials. Theory Prob. Appl. 11, 472–476.CrossRefGoogle Scholar
Hill, T. P. and Krengel, U. (1992). A prophet inequality related to the secretary problem. In Strategies for Sequential Search and Selection in Real Time (Amherst, MA, 1990; Contemp. Math. 125), American Mathematical Society, Providence, RI, pp. 209–215.CrossRefGoogle Scholar
Hsiau, S.-R. and Yang, J.-R. (2000). A natural variation of the standard secretary problem. Statistica Sinica 10, 639–646.Google Scholar
Hsiau, S.-R. and Yang, J.-R. (2002). Selecting the last success in Markov-dependent trials. J. Appl. Prob. 39, 271–281.CrossRefGoogle Scholar
Knuth, D. E. (1992). Two notes on notation. Amer. Math. Monthly 99, 403–422.CrossRefGoogle Scholar
Krieger, A. M. and Samuel-Cahn, H. (2009). The secretary problem of minimizing the expected rank: a simple suboptimal approach with generalizations. Adv. Appl. Prob. 41, 1041–1058.CrossRefGoogle Scholar
Lindley, D. V. (1961). Dynamic programming and decision theory. Appl. Statist. 10, 39–51.CrossRefGoogle Scholar
Mucci, A. G. (1973). On a class of secretary problems. Ann. Prob. 1, 417–427.CrossRefGoogle Scholar
Presman, È. L. and Sonin, I. M. (1972). The best choice problem for a random number of objects. Theory Prob. Appl. 17, 657–668.CrossRefGoogle Scholar
Samuels, S. M. (1991). Secretary problem. In Handbook of Sequential Analysis, eds Ghosh, B. K. and Sen, P. K., Dekker, New York, pp. 381–405.Google Scholar
Samuels, S. M. (2004). Why do these quite different best-choice problems have the same solutions? Adv. Appl. Prob. 36, 398–416.CrossRefGoogle Scholar
Tamaki, M. (2009). Optimal choice of the best available applicant in full-information models. J. Appl. Prob. 46, 1086–1099.CrossRefGoogle Scholar