Hostname: page-component-78c5997874-94fs2 Total loading time: 0 Render date: 2024-11-14T03:24:02.897Z Has data issue: false hasContentIssue false
  • English
  • Français

Recursive relations for the distribution of waiting times in a Markov chain

Part of: Stochastic processes Combinatorial probability Markov processes

Published online by Cambridge University Press:  14 July 2016

Dragan Banjevic
Dragan Banjevic*
Affiliation:
University of Toronto
*
∗Postal address: Department of Statistics, University of Toronto, 100 St. George Street, Toronto, M5S 1A1, Canada.
Get access Rights & Permissions [Opens in a new window]

Abstract

A Markov chain is used as a model for a sequence of random experiments. The waiting time for sequence patterns is considered. Recursive-type relations for the distribution of waiting times are obtained.

Keywords

SEQUENCE PATTERNSWAITING TIMEFIRST APPEARANCE

MSC classification

Primary: 60C05: Combinatorial probability
Secondary: 60G40: Stopping times; optimal stopping problems; gambling theory 60J10: Markov chains (discrete-time Markov processes on discrete state spaces)
Type
Research Papers
Information
Journal of Applied Probability , Volume 33 , Issue 1 , March 1996 , pp. 48 - 56
Copyright
Copyright © Applied Probability Trust 1996 

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.)

Footnotes

The author is a visiting professor at the University of Toronto.

References

Banjevic, D. (1988) On some statistics connected with runs in Markov chains. J. Appl. Prob. 25, 815–821.Google Scholar
Banjevic, D. (1990) On order statistics in waiting time for runs in Markov chains. Stat. Prob. Lett. 9, 125–127.Google Scholar
Banjevic, D. (1994) Pattern recognition in Markov chains. Runs and Patterns in Probability: Selected Papers. ed. Godbole, A. P. and Papastavridis, S. G. pp. 213–230. Kluwer, Dordrecht.Google Scholar
Biggins, J. D. and Cannings, C. (1987) Markov renewal processes, counters and repeated sequences in Markov chains. Adv. Appl. Prob. 19, 521–545.CrossRefGoogle Scholar
Blom, G. and Thorburn, D. (1982) How many random digits are required until given sequences are obtained? J. Appl. Prob. 19, 518–531.CrossRefGoogle Scholar
Breen, S., Waterman, M. S. and Zhang, N. (1985) Renewal theory for several patterns. J. Appl. Prob. 22, 228–234.CrossRefGoogle Scholar
Chrysaphinou, O. and Papastavridis, S. (1991) The occurrence of sequence patterns in repeated dependent experiments. Theory Prob. Appl. 35, 145–152.CrossRefGoogle Scholar
Feller, W. (1968) An Introduction to Probability Theory and its Applications, I. Wiley, New York.Google Scholar
Gerber, H. U. and Li, S. R. (1981) The occurrence of sequence patterns in repeated experiments and hitting times in a Markov chain. Stoch. Proc. Appl. 11, 101–108.Google Scholar
Godbole, A. P. (1991) Poisson approximations for runs and patterns of rare events. Adv. Appl. Prob. 23, 851–865.Google Scholar
Godbole, A. P. and Schaffner, A. A. (1993) Improved Poisson approximations for word patterns. Ado. Appl. Prob. 25, 334–347.Google Scholar
Guibas, L. J. and Odlyzko, A. M. (1981) String overlaps, pattern matching, and non-transitive games. J. Combin. Theory A30, 183–208.Google Scholar
Li, S. R. (1980) A martingale approach to the study of occurrence of sequence patterns in repeated experiments. Ann. Prob. 8, 1171–1176.Google Scholar
Móri, T. F. (1991) On the waiting time till each of some given patterns occurs as a run. Prob. Theory Rel. Fields 87, 313–323.CrossRefGoogle Scholar
Nielsen, P. T. (1973) On the expected duration of a search for a fixed pattern in random data. IEEE Trans. Inform. Theory 19, 702–704.Google Scholar
Schwager, S. J. (1983) Run probabilities in sequences of Markov-dependent trials. J. Amer. Stat. Assoc. 78, 168–175.Google Scholar