Compare the ratio of symmetric polynomials of odds to one and stop. (4th April 2017)

• Record Type: Journal Article
• Authors: Matsui, Tomomi; Ano, Katsunori
• Is Part Of: Journal of applied probability. Volume 54:Number 1(2017)
• Page Start: 12
• Page End: 22
• Publication Date: 2017-04-04
• Subjects: Optimal stopping, -- odds problem, -- lower bound, -- secretary problem, -- Newton's inequality; Primary 60G40, -- Secondary 60L15; 519.2
• DOI: 10.1017/jpr.2016.83
• Languages: English
• ISSNs: 0021-9002

Abstract

Abstract: 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.