Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-23T05:49:20.219Z Has data issue: false hasContentIssue false
  • English
  • Français

The intersite distances between pattern occurrences in strings generated by general discrete- and continuous-time models: an algorithmic approach

Part of: Special processes Distribution theory - Probability

Published online by Cambridge University Press:  14 July 2016

Valeri T. Stefanov
Valeri T. Stefanov*
Affiliation:
University of Western Australia
*
∗Postal address: School of Mathematics and Statistics, University of Western Australia, Crawley, WA 6009, Australia. Email address: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

The formation of patterns from letters of a finite alphabet is considered. The strings of letters are generated by general discrete- and continuous-time models which embrace as particular cases all models considered in the literature. The letters of the alphabet are identified by the states of either discrete- or continuous-time semi-Markov processes. A new and unifying method is introduced for evaluation of the generating functions of both the intersite distance between occurrences of an arbitrary, but fixed, pattern and the waiting time until the first occurrence of that pattern. Our method also covers in a unified way relevant and important joint generating functions. Furthermore, our results lead to an easy and efficient implementation of the relevant evaluations.

Keywords

Patternprobability generating functionsemi-Markov processrandom sum

MSC classification

Primary: 60E10: Characteristic functions; other transforms
Secondary: 60K20: Applications of Markov renewal processes (reliability, queueing networks, etc.)
Type
Research Papers
Information
Journal of Applied Probability , Volume 40 , Issue 4 , September 2003 , pp. 881 - 892
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

Antzoulakos, D. L. (2001). Waiting times for patterns in a sequence of multistate trials. J. Appl. Prob. 38, 508–518.CrossRefGoogle Scholar
Balakrishnan, N., and Koutras, M. (2002). Runs and Scans with Applications. John Wiley, New York.Google Scholar
Biggins, J. D. (1987). A note on repeated sequences in Markov chains. Adv. Appl. Prob. 19, 739–742.CrossRefGoogle 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
Chadjiconstantinidis, S., Antzoulakos, D. L., and Koutras, M. V. (2000). Joint distributions of successes, failures and patterns in enumeration problems. Adv. Appl. Prob. 32, 866–884.CrossRefGoogle Scholar
Chryssaphinou, O., and Papastavridis, S. (1990). The occurrence of a sequence of patterns in repeated dependent experiments. Theory Prob. Appl. 35, 167–173.Google Scholar
Çinlar, E. (1975). Introduction to Stochastic Processes. Prentice-Hall, Englewood Cliffs, NJ.Google Scholar
Feller, W. (1950). An Introduction to Probability Theory and Its Applications, Vol. 1. John Wiley, New York.Google Scholar
Fu, J. C. (1996). Distribution theory of runs and patterns associated with a sequence of multistate trials. Statistica Sinica 6, 957–974.Google Scholar
Fu, J. C., and Chang, Y. M. (2002). On probability generating functions for waiting time distributions of compound patterns in a sequence of multistate trials. J. Appl. Prob. 39, 70–80.CrossRefGoogle Scholar
Gerber, H. and Li, S.-Y. R. (1981). The occurrence of sequence patterns in repeated experiments and hitting times in a Markov chain. Stoch. Process. Appl. 11, 101–108.CrossRefGoogle Scholar
Guibas, L. J., and Odlyzko, A. M. (1981). String overlaps, pattern matching, and nontransitive games. J. Combinatorial Theory A 30, 183–208.CrossRefGoogle Scholar
Kijima, M. (1997). Markov Processes for Stochastic Modelling. Chapman and Hall, London.CrossRefGoogle Scholar
Li, S.-Y. R. (1980). A martingale approach to the study of occurrence of sequence patterns in repeated experiments. Ann. Prob. 8, 1171–1176.CrossRefGoogle Scholar
Reinert, G., Schbath, S., and Waterman, M. (2000). Probabilistic and statistical properties of words: an overview. J. Comput. Biol. 7, 1–46.CrossRefGoogle ScholarPubMed
Robin, S., and Daudin, J. (1999). Exact distribution of word occurrences in a random sequence of letters. J. Appl. Prob. 36, 179–193.CrossRefGoogle Scholar
Stefanov, V. T. (2000). On some waiting time problems. J. Appl. Prob. 37, 756–764.CrossRefGoogle Scholar
Stefanov, V. T., and Pakes, A. G. (1997). Explicit distributional results in pattern formation. Ann. Appl. Prob. 7, 666–678.Google Scholar
Syski, R. (1992). Passage Times for Markov Chains. IOS Press, Amsterdam.Google Scholar
Szpankowski, W. (2001). Average Case Analysis of Algorithms on Sequences. John Wiley, New York.CrossRefGoogle Scholar