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

Tomomi Matsui, Katsunori Ano

Research output: Contribution to journalArticlepeer-review


In this paper we deal with an optimal stopping problem whose objective is to maximize the probability of selecting k out of the last l successes, given a sequence of independent Bernoulli trials of length N, where k and l are predetermined integers satisfying 1≤k≤l<N. This problem includes some odds problems as special cases, e.g. Bruss' odds problem, Bruss and Paindaveine's problem of selecting the last l 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.

Original languageEnglish
Pages (from-to)12-22
Number of pages11
JournalJournal of Applied Probability
Issue number1
Publication statusPublished - 2017 Mar 1


  • Newton's inequality
  • Optimal stopping
  • lower bound
  • odds problem
  • secretary problem

ASJC Scopus subject areas

  • Statistics and Probability
  • General Mathematics
  • Statistics, Probability and Uncertainty


Dive into the research topics of 'Compare the ratio of symmetric polynomials of odds to one and stop'. Together they form a unique fingerprint.

Cite this