Abstract
Suppose that C is a finite collection of patterns. Observe a Markov chain until one of the patterns in C occurs as a run. This time is denoted by τ. In this paper, we aim to give an easy way to calculate the mean waiting time E(τ ) and the stopping probabilities P(τ = τ A ) with A ∈ C, where τ A is the waiting time until the pattern A appears as a run.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
J Brofos. A Markov chain analysis of a pattern matching coin game, arXiv preprint, arXiv: 1406.2212, 2014.
O Chrysaphinou, S Papastavridis. The occurrence of sequence patterns in repeated dependent experiments, Theory Probab Appl, 1991, 35(1): 145–152.
JC Fu, YM Chang. On probability generating functions for waiting time distributions of compound patterns in a sequence of multistate trials, J Appl Probab, 2002, 39: 70–80.
RJ Gava, D Salotti. Stopping probabilities for patterns in Markov chains, J Appl Probab, 2014, 51(1): 287–292.
HU Gerber, SR Li. The occurrence of sequence patterns in repeated experiments and hitting times in a Markov chain, Stochastic Process Appl, 1981, 11(1): 101–108.
J Glaz, M Kulldorff, V Pozdnyakov, JM Steele. Gambling teams and waiting times for patterns in two-state Markov chains, J Appl Probab, 2006, 43(1): 127–140.
LJ Guibas, AM Odlyzko. String overlaps, pattern matching, and nontransitive games, J Combin Theory Ser A, 1981, 30(2): 183–208.
SR Li. A martingale approach to the study of occurrence of sequence patterns in repeated experiments, Ann Probab, 1980, 8(6): 1171–1176.
JI Naus. The distribution of the size of the maximum cluster of points on a line, J Amer Statist Assoc, 1965, 60(310): 532–538.
J I Naus, VT Stefanov. Double-scan statistics, Methodol Comput Appl Probab, 2002, 4(2): 163–180.
Y Nishiyama. Pattern matching probabilities and paradoxes as a new variation on Penney’s coin game, Int J Pure Appl Math, 2010, 59(3): 357–366.
V Pozdnyakov. On occurrence of patterns in Markov chains: method of gambling teams, Statist Probab Lett, 2008, 78(16): 2762–2767.
Acknowledgements
The authors wish to express their thanks to the referee for his/her constructive suggestions and many helpful comments.
Author information
Authors and Affiliations
Corresponding author
Additional information
Supported by the National Natural Science Foundation of China (11771286, 11371317) and by the Zhejiang Provincial Natural Science Foundation of China (LQ18A010007).
Rights and permissions
About this article
Cite this article
Zhao, Mz., Xu, D. & Zhang, Hz. Waiting times and stopping probabilities for patterns in Markov chains. Appl. Math. J. Chin. Univ. 33, 25–34 (2018). https://doi.org/10.1007/s11766-018-3522-z
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11766-018-3522-z