Hostname: page-component-586b7cd67f-l7hp2 Total loading time: 0 Render date: 2024-11-22T04:05:50.443Z Has data issue: false hasContentIssue false

A sharp lower bound for choosing the maximum of an independent sequence

Published online by Cambridge University Press:  09 December 2016

Pieter C. Allaart*
Affiliation:
University of North Texas
José A. Islas*
Affiliation:
University of North Texas
*
* Postal address: Department of Mathematics, University of North Texas, 1155 Union Circle #311430, Denton, TX 76203-5017, USA.
* Postal address: Department of Mathematics, University of North Texas, 1155 Union Circle #311430, Denton, TX 76203-5017, USA.

Abstract

In this paper we consider a variation of the full-information secretary problem where the random variables to be observed are independent but not necessary identically distributed. The main result is a sharp lower bound for the optimal win probability. Precisely, if X 1,...,X n are independent random variables with known continuous distributions and V n (X 1,...,Xn ):=supτℙ(X τ=M n ), where M n ≔max{X 1,...,X n } and the supremum is over all stopping times adapted to X 1,...,X n then V n (X 1,...,X n )≥(1-1/n)n-1, and this bound is attained. The method of proof consists in reducing the problem to that of a sequence of random variables taking at most two possible values, and then applying Bruss' sum-the-odds theorem, Bruss (2000). In order to obtain a sharp bound for each n, we improve Bruss' lower bound, Bruss (2003), for the sum-the-odds problem.

Type
Research Papers
Copyright
Copyright © Applied Probability Trust 2016 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Bruss, F. T. (2000).Sum the odds to one and stop.Ann. Prob. 28,13841391.Google Scholar
[2] Bruss, F. T. (2003).A note on bounds for the odds theorem of optimal stopping.Ann. Prob. 31,18591861.CrossRefGoogle Scholar
[3] Ferguson, T. S. (1989).Who solved the secretary problem? With comments and a rejoinder by the author.Statist. Sci. 4,282296.Google Scholar
[4] Gilbert, J. P. and Mosteller, F. (1966).Recognizing the maximum of a sequence.J. Amer. Statist. Assoc. 61,3573.Google Scholar
[5] Samuels, S. M. (1991).Secretary problems.In Handbook of Sequential Analysis,Dekker,New York,pp. 381405.Google Scholar