Selecting a sequence of last successes in independent trials

Bruss, F. Thomas and Paindaveine, Davy (2000): Selecting a sequence of last successes in independent trials. Published in: Journal of Applied Probability No. 37 (2000): pp. 389-399.

Abstract

Let I1, I2, . . . , In be a sequence of independent indicator functions de- fined on a probability space (Ω, A, P ). We say that index k is a success time if Ik = 1. The sequence I1, I2, . . . , In is observed sequentially. The objective of this article is to predict the l-th last success, if any, with maximum probability at the time of its occurence. We find the optimal rule and discuss briefly an algorithm to compute it in an efficient way. This generalizes the result of Bruss (1998) for l = 1, and is equivalent to the problem of (multiple) stopping with l stops on the last l successes. We extend then the model to a larger class allowing for an unknown number N of indicator functions, and present, in particular, a convenient method for an approximate solution if the success probabilities are small. We also discuss some applications of the results.

• Item Type: MPRA Paper
• Language: English
• Keywords: ”Sum the odds” algorithm, optimal stopping, multiple stop- ping, stopping islands, generating functions, modified secretary problems, unimodality.
• Subjects: C - Mathematical and Quantitative Methods > C0 - General > C02 - Mathematical Methods

References

Ano, K. (1989), Optimal selection with three stops, J. Op. Res. Soc. of Japan 32, 491-504.

Arnold, B.C., Balakrishan, N. and Nagaraja, H.N. (1998), Records, John Wiley and Sons.

Bruss, F. Thomas (1988), Invariant record processes and applications to best choice modeling, Stoch. Processes and Th. Applic., Vol. 30, 303-316.

Bruss, F. Thomas (1998), Sum the odds to one and stop, Research Report IS-P 1998-32, Prob. et Stat., Universit ́e Libre de Bruxelles.

David, F.N. and Kendall, M.G. (1966), Symmetric function and allied tables, Cambridge University Press, 1-7.

Gilbert, J. and Mosteller, F. (1966), Recognizing the maximum of a sequence, J. Amer. Statist. Assoc., Vol. 61, 35-73.

Praeter, J. (1994) On a multiple choice secretary problem, Math. of Oper. Res. 19, 597-602.

Renyi, A (1962), Th ́eorie des ́el ́ements saillants dans une suite d’observations, Proc. Coll. Comb. Methods, (Aarhus Universitet), 104-115.

Rose, J. (1982), A problem of optimal choice and assignment, Operations Re- search 30, 172-181.

Sakaguchi, M. (1978), Dowry problems and OLA policies, Rep. Statist. Appl. Res. JUSE, Vol. 25, 124-128.

Stadje, W. (1985), On multiple stopping rules, Optimization 16, 401-418.

Tamaki, M. (1979 a), A secretary problem with double choices, J. Oper. Res. Soc. Japan 22, 257-264.

Tamaki, M. (1979 b), Recognizing both the maximum and the second maximum of a sequence, J. Appl. Prob. 16, 803-812.