Hostname: page-component-745bb68f8f-grxwn Total loading time: 0 Render date: 2025-02-06T11:27:37.903Z Has data issue: false hasContentIssue false
  • English
  • Français

Compare the ratio of symmetric polynomials of odds to one and stop

Part of: Stochastic processes

Published online by Cambridge University Press:  04 April 2017

Tomomi Matsui  and
Katsunori Ano
Tomomi Matsui*
Affiliation:
Tokyo Institute of Technology
Katsunori Ano*
Affiliation:
Shibaura Institute of Technology
*
* Postal address: Department of Social Engineering, Graduate School of Decision Science and Technology, Tokyo Institute of Technology, Ookayama, Meguro-ku, Tokyo, 152-8550, Japan. Email address: matsui.t.af.@m.titech.ac.jp
** Postal address: Department of Mathematical Sciences, Shibaura Institute of Technology, Fukasaku, Minuma-ku, Saitama-shi, Saitama, 337-8570, Japan.
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.

In this paper we deal with an optimal stopping problem whose objective is to maximize the probability of selecting k out of the last ℓ successes, given a sequence of independent Bernoulli trials of length N, where k and ℓ are predetermined integers satisfying 1≤k≤ℓ<N. This problem includes some odds problems as special cases, e.g. Bruss’ odds problem, Bruss and Paindaveine’s problem of selecting the last ℓ successes, and Tamaki’s multiplicative odds problem for stopping at any of the last m successes. We show that an optimal stopping rule is obtained by a threshold strategy. We also present the tight lower bound and an asymptotic lower bound for the probability of a win. Interestingly, our asymptotic lower bound is attained by using a variation of the well-known secretary problem, which is a special case of the odds problem. Our approach is based on the application of Newton’s inequalities and optimization technique, which gives a unified view to the previous works.

Keywords

Optimal stoppingodds problemlower boundsecretary problemNewton’s inequality

MSC classification

Primary: 60G40: Stopping times; optimal stopping problems; gambling theory
Type
Research Papers
Information
Journal of Applied Probability , Volume 54 , Issue 1 , March 2017 , pp. 12 - 22
Copyright
Copyright © Applied Probability Trust 2017 

References

[1] Bartoszyński, R. (1974).On certain combinatorial identities.Colloq. Math. 30,289–293.Google Scholar
[2] Bruss, F. T. (1984).Patterns of relative maxima in random permutations.Ann. Soc. sci. Brux. 98,19–28.Google Scholar
[3] Bruss, F. T. (2000).Sum the odds to one and stop.Ann. Prob. 28,1384–1391.Google Scholar
[4] Bruss, F. T. (2003).A note on bounds for the odds theorem of optimal stopping.Ann. Prob. 31,1859–1861.Google Scholar
[5] Bruss, F. T. and Paindaveine, D. (2000).Selecting a sequence of last successes in independent trials.J. Appl. Prob. 37,389–399.Google Scholar
[6] Chow, Y. S., Robbins, H. and Siegmund, D. (1971).Great Expectations: The Theory of Optimal Stopping,Houghton Mifflin,Boston, MA.Google Scholar
[7] Ferguson, T. S. (2006).Optimal stopping and applications. Unpublished manuscript. Available at http://www.math.ucla.edu/~tom/Stopping/Contents.html.Google Scholar
[8] Ferguson, T. S. (2008).The sum-the-odds theorem with application to a stopping game of Sakaguchi. Preprint. Available at http://www.math.ucla.edu/~tom/papers/oddsThm.pdf.Google Scholar
[9] Gilbert, J. P. and Mosteller, F. (1966).Recognizing the maximum of a sequence.J. Amer. Statist. Assoc. 61,35–73.Google Scholar
[10] Matsui, T. and Ano, K. (2014).A note on a lower bound for the multiplicative odds theorem of optimal stopping.J. Appl. Prob. 51,885–889.Google Scholar
[11] Newton, I. (1707).Arithmetica Universalis, sive de compositione et resolutione arithmetica liber Google Scholar
[12] Sakaguchi, M. (1978).Dowry problems and OLA policies.Rep. Statist. Appl. Res. Japan. Un. Sci. Eng. 25,24–28.Google Scholar
[13] Tamaki, M. (2010).Sum the multiplicative odds to one and stop.J. Appl. Prob. 47,761–777.Google Scholar