×

Sum the odds to one and stop. (English) Zbl 1005.60055

Summary: The objective of this paper is to present two theorems which are directly applicable to optimal stopping problems involving independent indicator functions. The proofs are elementary. One implication of the results is a convenient solution algorithm to obtain the optimal stopping rule and the value. We will apply it to several examples of sequences of independent indicators, including sequences of random length. Another interesting implication of the results is that the well-known asymptotic value \(1/e\) for the classical best-choice problem is in fact a typical lower bound in a much more general class of problems.

MSC:

60G40 Stopping times; optimal stopping problems; gambling theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Billingsley, P. (1995). Probability and Measure. Wiley, New York. Bruss, F. T. (1984a). Patterns of relative maxima in random permutations. Ann. Société Scient. Bruxelles 98 19-28. Bruss, F. T. (1984b). A unifiedapproach to a class of best choice problems with an unknown number of options. Ann. Probab. 12 882-889.
[2] Chow, Y. S. Robbins, H. and Siegmund, D. (1971). The Theory of Optimal Stopping. Houghton Mifflin, Boston. · Zbl 0233.60044
[3] Dynkin, E. B. and Juschkewitsch, A. A. (1969). Markoffsche Prozesse. Springer, Berlin. · Zbl 0185.45601
[4] Gianini, J. and Samuels, S. M. (1976). The infinite secretary problem. Ann. Probab. 4 418-432. · Zbl 0341.60033 · doi:10.1214/aop/1176996090
[5] Grey, D. (1999). Private communication.
[6] Hill, T. P. and Kennedy, D. P. (1992). Sharp inequalities for optimal stopping with rewards based on ranks. Ann Appl. Probab. 2 503-517. · Zbl 0758.60041 · doi:10.1214/aoap/1177005713
[7] Hill T. P. and Krengel, U. (1992). A prophet inequality relatedto the secretary problem. Contemp. Math. 125 209-215. · Zbl 0760.60046
[8] Hsiau, S. R. and Yang, J. R. (2000). A natural variation of the standard secretary problem. Statist. Sinica 10. · Zbl 0963.62076
[9] Pfeifer, D. (1989). Extremal processes, secretary problems andthe 1/e-law. J. Appl. Probab. 26 722-733. JSTOR: · Zbl 0693.60030 · doi:10.2307/3214377
[10] Rocha, A. L. (1993). The infinite secretary problem with recall. Ann. Probab. 21 898-916. · Zbl 0776.60057 · doi:10.1214/aop/1176989273
[11] Samuel-Cahn, E. (1995). The best-choice secretary problem with random freeze on jobs. Stochatstic Process Appl. 55 315-327. · Zbl 0821.60051 · doi:10.1016/0304-4149(94)00042-R
[12] Samuels, S. M. (1993). Secretary problems as a source of benchmark bounds. In Stochastic Inequalities (M. ShakedandY. L. Tong, eds.) 371-387. IMS, Hayward, CA. · Zbl 1400.60057 · doi:10.1214/lnms/1215461963
[13] Shiryayev, A. N. (1978). Optimal Stopping Rules. Springer, New York. · Zbl 0391.60002
[14] Tamaki, M. (1999). Private communication.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.