Optimal stopping on patterns in strings generated by independent random variables

DOI10.1239/JAP/1044476827MaRDI QIDQ4408535zbMATH OpenOpenAlexFDO

Authors F. Thomas Bruss, Guy Louchard

Publication date 3 November 2003

Published in Journal of Applied Probability (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/6d7de3bf897a5c8a7c54583bcb129f5413aafe25

zbMATH Keywords

algorithms on wordsodds algorithmonline decisionspattern correlation

Mathematics Subject Classification ID

Combinatorial probability (60C05) Stopping times; optimal stopping problems; gambling theory (60G40)

Review text

The aim of this paper is to give an algorithm for the optimal stopping problem in the homogeneous case with uncorrelated pattern. Moreover, the asymptotic properties of this algorithm are analysed. Finally, an explicit numerical example is given. Related papers: \textit{L. J. Guibas} and \textit{A. M. Odlyzko} [J. Comb. Theory, Ser. A 30, 183-208 (1981; Zbl 0454.68109)]; \textit{D. E. Knuth, J. Morris} and \textit{V. Pratt} [Sci. Math. Japon. 7, 209-223 (2002)] and \textit{S.-Y. R. Li} [Ann. Probab. 8, 1171-1176 (1980; Zbl 0447.60006)].

Recommendations

• Optimal pattern matching algorithms
• Explicit Distributional Results In Pattern Formation II
• Sum the odds to one and stop
• Stopping Probabilities for Patterns in Markov Chains
• On optimal stopping of random sequences modulated by Markov chain

Cited in

(2)

• Selecting the last consecutive record in a record process
• The odds algorithm based on sequential updating and its performance

This page was built for publication: Optimal stopping on patterns in strings generated by independent random variables

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4408535)