A sharp lower bound for choosing the maximum of an independent sequence. (English) Zbl 1355.60055

Allaart, Pieter C.; Islas, José A.

J. Appl. Probab. 53, No. 4, 1041-1051 (2016).

Summary: 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},\ldots ,X_{n}\) are independent random variables with known continuous distributions and \(V_{n}(X_{1},\ldots ,X_{n}):= \sup_\tau \mathbb{P}(X_\tau = M_{n})\), where \(M_{n} := \max \{ X_{1},\ldots ,X_{n}\}\) and the supremum is over all stopping times adapted to \(X_{1},\ldots ,X_{n}\) then \(V_{n}(X_{1},\ldots ,X_{n}) \geq (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 F. T. Bruss’ sum-the-odds theorem [Ann. Probab. 28, No. 3, 1384–1391 (2000; Zbl 1005.60055)]. In order to obtain a sharp bound for each \(n\), we improve F. T. Bruss’ lower bound [Ann. Probab. 31, No. 4, 1859–1861 (2003; Zbl 1059.60056)], for the sum-the-odds problem.

MSC:

60G40	Stopping times; optimal stopping problems; gambling theory
60G70	Extreme value theory; extremal stochastic processes
62L15	Optimal stopping in statistics

Keywords:

independent sequence; maximum; stopping time; sum-the-odds theorem

Citations:

Zbl 1005.60055; Zbl 1059.60056

References:

[1]	Bruss, F. T. (2000). Sum the odds to one and stop. Ann. Prob. 28, 1384-1391. · Zbl 1005.60055 · doi:10.1214/aop/1019160340
[2]	Bruss, F. T. (2003). A note on bounds for the odds theorem of optimal stopping. Ann. Prob. 31, 1859-1861. · Zbl 1059.60056 · doi:10.1214/aop/1068646368
[3]	Ferguson, T. S. (1989). Who solved the secretary problem? With comments and a rejoinder by the author. Statist. Sci. 4, 282-296. · Zbl 0788.90080 · doi:10.1214/ss/1177012493
[4]	Gilbert, J. P. and Mosteller, F. (1966). Recognizing the maximum of a sequence. J. Amer. Statist. Assoc. 61, 35-73. · doi:10.1080/01621459.1966.10502008
[5]	Samuels, S. M. (1991). Secretary problems. In Handbook of Sequential Analysis , Dekker, New York, pp. 381-405.