Hostname: page-component-745bb68f8f-l4dxg Total loading time: 0 Render date: 2025-02-06T07:42:52.109Z 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.
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 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 

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