Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-23T05:52:23.857Z Has data issue: false hasContentIssue false
  • English
  • Français

Optimal stopping on patterns in strings generated by independent random variables

Part of: Stochastic processes

Published online by Cambridge University Press:  14 July 2016

F. Thomas Bruss  and
Guy Louchard
F. Thomas Bruss*
Affiliation:
Université Libre de Bruxelles
Guy Louchard*
Affiliation:
Université Libre de Bruxelles
*
∗ Postal address: Université Libre de Bruxelles, Département de Mathématiques et ISRO, CP 210, Boulevard du Triomphe, B-1050 Bruxelles, Belgium. Email address: [email protected]
∗∗ Postal address: Université Libre de Bruxelles, Département d’Informatique, CP 212, Boulevard du Triomphe, B-1050 Bruxelles, Belgium.
Get access Rights & Permissions [Opens in a new window]

Abstract

Strings are generated by sequences of independent draws from a given alphabet. For a given pattern H of length l and an integer n ≥ l, our goal is to maximize the probability of stopping on the last appearance of the pattern H in a string of length n (if any), given that, if we choose to stop on an occurrence of H, we must do so right away. This contrasts with the goals of several other investigations on patterns in strings such as computing the expected occurrence time and the probability of finding exactly r patterns in a string of fixed length. Several motivations are given for our problem ranging from relatively simple best choice problems to more difficult stopping problems allowing for a variety of interesting applications. We solve this problem completely in the homogeneous case for uncorrelated patterns. However, several of these results extend immediately to the inhomogeneous case. In the homogeneous case, optimal success probabilities are shown to vary, depending on characteristics of the pattern, essentially between the value 1/e and a new asymptotic constant 0.619…. These results demonstrate a considerable difference between the true optimal success probability compared with what a first approximation by heuristic arguments would yield. It is interesting to see that the so-called odds algorithm which gives the optimal rule for l = 1 yields an excellent approximation of the optimal rule for any l. This is important for applications because the odds algorithm is very convenient. We finally give a detailed asymptotic analysis for the homogeneous case.

Keywords

Odds algorithmsimple odds algorithmalgorithms on wordsinvestment problemssecretary problemsapartment problemsingle-island stopping ruleonline decisionspattern correlationPoisson clumping heuristicasymptotic analysis

MSC classification

Primary: 60G40: Stopping times; optimal stopping problems; gambling theory
Type
Research Papers
Information
Journal of Applied Probability , Volume 40 , Issue 1 , March 2003 , pp. 49 - 72
Copyright
Copyright © Applied Probability Trust 2003 

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] Abramowitz, M., and Stegun, I. A. (1965). Handbook of Mathematical Functions. Dover, New York.Google Scholar
[2] Aldous, D. (1989). Probability Approximations via the Poisson Clumping Heuristic. Springer, New York.Google Scholar
[3] Allard, P., and Monticino, M. (2001). Optimal stopping rules for directionally reinforced processes. Adv. Appl. Prob. 33, 483–504.Google Scholar
[4] Ano, K., and Ando, M. (2000). A note on Bruss’ stopping problem with random availability. In Game Theory, Optimal Stopping, Probability and Statistics (IMS Lecture Notes Monogr. Ser. 35), Institute of Mathematical Statistics, Beachwood, OH, pp. 71–82.CrossRefGoogle Scholar
[5] Barbour, A. D., and Chryssaphinou, O. (2001). Compound Poisson approximations: a user's guide. Adv. Appl. Prob. 2, 964–1002.Google Scholar
[6] Bruss, F. T. (1987). On an optimal selection problem of Cowan and Zabczyk. J. Appl. Prob. 24, 918–928.Google Scholar
[7] Bruss, F. T. (2000). Sum the odds to one and stop. Ann. Prob. 28, 1384–1391.Google Scholar
[8] Bruss, F. T., and Paindaveine, D. (2000). Selecting a sequence of last successes in independent trials. J. Appl. Prob. 37, 389–399.CrossRefGoogle Scholar
[9] Chow, Y. S., Robbins, H., and Siegmund, D. (1991). The Theory of Optimal Stopping. Dover, New York.Google Scholar
[10] Cowan, R., and Zabczyk, J. (1978). An optimal selection problem associated with the Poisson process. Theory Prob. Appl. 23, 584–592.Google Scholar
[11] Flajolet, P., and Sedgewick, B. (1993). Analytic combinatorics: complex asymptotics and generating functions. Tech. Rep. 2026, INRIA.Google Scholar
[12] Gnedin, A. (2002). Best choice from the planar Poisson process. Tech. Rep. Available at http://arxiv.org/.Google Scholar
[13] Graham, R. L., Knuth, D. E., and Patashnik, O. (1988). Concrete Mathematics, A Foundation for Computer Science. Addison-Wesley, Reading, MA.Google Scholar
[14] Guibas, L. J., and Odlyzko, A. M. (1981). String overlaps, pattern matching, and nontransitive games. J. Combinatorial Theory 30, 183–208.Google Scholar
[15] Hsiau, S. R., and Yang, J. R. (2000). A natural variation of the standard secretary problem. Statist. Sinica 10, 639–646.Google Scholar
[16] Hsiau, S. R., and Yang, J. R. (2002). Selecting the last success in Markov-dependent trials. J. Appl. Prob. 39, 271–281.Google Scholar
[17] Knuth, D. E., Morris, J., and Pratt, V. (1977). Fast pattern matching in strings. SIAM J. Comput. 6, 189–195.Google Scholar
[18] Kurishima, A., and Ano, K. (2002). A Poisson arrival selection problem for Gamma prior intensity with natural number parameter. Sci. Math. Japon. 7, 209–223.Google Scholar
[19] Li, S. Y. R. (1980). A martingale approach to the study of the occurrence of patterns in repeated experiments. Ann. Prob. 8, 1171–1175.Google Scholar
[20] Mauldin, R. D., Monticino, M. and von Weizsäcker, H. (1996). Directionally reinforced random walks. Adv. Math. 117, 239–252.Google Scholar
[21] Presman, E. L., and Sonin, I. M. (1972). The best choice problem for a random number of objects. Theory Prob. Appl. 17, 657–668.Google Scholar
[22] Samuel-Cahn, E. (1995). The best choice problem with random freeze on jobs. Stoch. Process. Appl. 55, 315–327.Google Scholar
[23] Samuels, S.M. (1991). Secretary problems. In Handbook of Sequential Analysis, eds Gosh, B. K. and Sen, P. K., Marcel Dekker, New York, pp. 381–405.Google Scholar
[24] Suchwalko, A., and Szajowski, K. (2002). Extension of Bruss’ problem to choosing the best or the second best option. In Proc. 10th Internat. Symp. Dynamic Games Appl. (Petrozavodsk, 12–15 July 2002). Available at http://www.krc.karelia.ru/events/isdg/.Google Scholar
[25] Szajowski, K. (2002). Game version of the Bruss problem (abstract). In Optimal Stopping and Stochastic Games Workshop (Bȩdlewo, 1–7 July 2002). Available at http://neyman.im.pwr.pl/ossg2002/.Google Scholar
[26] Szpankowski, W. (2001). Average Case Analysis of Algorithms on Sequences. John Wiley, New York.Google Scholar
[27] Tamaki, M. (2001). Optimal stopping on trajectories and the ballot theorem. J. Appl. Prob. 38, 946–959.Google Scholar