Hostname: page-component-586b7cd67f-t8hqh Total loading time: 0 Render date: 2024-11-26T03:08:15.377Z Has data issue: false hasContentIssue false

Markov renewal processes, counters and repeated sequences in Markov chains

Published online by Cambridge University Press:  01 July 2016

J. D. Biggins*
Affiliation:
The University of Sheffield
C. Cannings*
Affiliation:
The University of Sheffield
*
Postal address: Department of Probability and Statistics, The University of Sheffield, Sheffield S10 2TN, UK.
Postal address: Department of Probability and Statistics, The University of Sheffield, Sheffield S10 2TN, UK.

Abstract

The theory of Markov renewal processes is applied to study the occurrence of specific sequences of states in a Markov chain. Çinlar&s (1969) results are used to study both the basic process, and that obtained when the overlap of sequences is not permitted, as in the theory of counters. These results are applied to the fragments formed when DNA is digested using one, or more, restriction enzymes.

Type
Research Article
Copyright
Copyright © Applied Probability Trust 1987 

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

Benevento, R. V. (1984) The occurrence of sequence patterns in ergodic Markov chains. Stoc. Proc. Appl. 17, 369373.Google Scholar
Biggins, J. D. (1987) A note on repeated sequences in Markov chains. Adv. Appl. Prob. 19, 740743.Google Scholar
Bishop, D. T., Williamson, J. A. and Skolnick, M. H. (1983) A model for restriction fragment length distributions. Amer. J. Hum. Genet. 35, 795815.Google Scholar
Blom, G. and Thorburn, D. (1982) How many random digits are required until given sequences are obtained? J. Appl. Prob. 19, 518531.Google Scholar
Breen, S., Waterman, M. S. and Zhang, N. (1985) Renewal theory for several patterns. J. Appl. Prob. 22, 228234.CrossRefGoogle Scholar
Çinlar, E. (1969) Markov renewal theory. Adv. Appl. Prob. 1, 123187.Google Scholar
Gerber, H. U. and Li, S.-Y.P. (1981) The occurrence of sequence patterns in repeated experiments and hitting times in a Markov chain. Stoc. Proc. Appl. 11, 101108.Google Scholar
Guibas, L. J. and Odlyzko, A. M. (1981) String overlaps, pattern matching, and non-transitive games. J. Combinatorial Theory A 30, 183208.Google Scholar
Hunter, J. J. (1969) On the moments of Markov renewal processes. Adv. Appl. Prob. 1, 188210.Google Scholar
Kemeny, J. G. and Snell, J. L. (1976) Finite Markov Chains. Springer-Verlag, New York.Google Scholar
Schwager, S. J. (1983) Run probabilities in sequences of Markov-dependent trials. J. Amer. Statist. Assoc. 78, 168175.Google Scholar
Seneta, E. (1973) Non-Negative Matrices. Allen and Unwin, London.Google Scholar