×

The intersite distances between pattern occurrences in strings generated by general discrete- and continuous-time models: an algorithmic approach. (English) Zbl 1054.60022

Summary: The formation of patterns from letters of a finite alphabet is considered. The strings of letters are generated by general discrete- and confinuous-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.

MSC:

60E10 Characteristic functions; other transforms
60K20 Applications of Markov renewal processes (reliability, queueing networks, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Antzoulakos, D. L. (2001). Waiting times for patterns in a sequence of multistate trials. J. Appl. Prob. 38, 508–518. · Zbl 0985.60072
[2] Balakrishnan, N. and Koutras, M. (2002). Runs and Scans with Applications. John Wiley, New York. · Zbl 0991.62087
[3] Biggins, J. D. (1987). A note on repeated sequences in Markov chains. Adv. Appl. Prob. 19, 739–742. · Zbl 0634.60083
[4] Biggins, J. D. and Cannings, C. (1987). Markov renewal processes, counters and repeated sequences in Markov chains. Adv. Appl. Prob. 19, 521–545. · Zbl 0629.60100
[5] Blom, G. and Thorburn, D. (1982). How many random digits are required until given sequences are obtained? J. Appl. Prob. 19, 518–531. · Zbl 0493.60071
[6] 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. · Zbl 0963.60003
[7] Chryssaphinou, O. and Papastavridis, S. (1990). The occurrence of a sequence of patterns in repeated dependent experiments. Theory Prob. Appl. 35, 167–173. · Zbl 0724.60082
[8] \cCinlar, E. (1975). Introduction to Stochastic Processes. Prentice-Hall, Englewood Cliffs, NJ.
[9] Feller, W. (1950). An Introduction to Probability Theory and Its Applications , Vol. 1. John Wiley, New York. · Zbl 0039.13201
[10] Fu, J. C. (1996). Distribution theory of runs and patterns associated with a sequence of multistate trials. Statistica Sinica 6, 957–974. · Zbl 0857.60068
[11] 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. · Zbl 1008.60031
[12] 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. · Zbl 0449.60050
[13] Guibas, L. J. and Odlyzko, A. M. (1981). String overlaps, pattern matching, and nontransitive games. J. Combinatorial Theory A 30, 183–208. · Zbl 0454.68109
[14] Kijima, M. (1997). Markov Processes for Stochastic Modelling. Chapman and Hall, London. · Zbl 0866.60056
[15] Li, S.-Y. R. (1980). A martingale approach to the study of occurrence of sequence patterns in repeated experiments. Ann. Prob. 8, 1171–1176. · Zbl 0447.60006
[16] Reinert, G., Schbath, S. and Waterman, M. (2000). Probabilistic and statistical properties of words: an overview. J. Comput. Biol. 7, 1–46.
[17] Robin, S. and Daudin, J. (1999). Exact distribution of word occurrences in a random sequence of letters. J. Appl. Prob. 36, 179–193. · Zbl 0945.60008
[18] Stefanov, V. T. (2000). On some waiting time problems. J. Appl. Prob. 37, 756–764. · Zbl 0969.60021
[19] Stefanov, V. T. and Pakes, A. G. (1997). Explicit distributional results in pattern formation. Ann. Appl. Prob. 7, 666–678. · Zbl 0893.60005
[20] Syski, R. (1992). Passage Times for Markov Chains. IOS Press, Amsterdam. · Zbl 0804.60065
[21] Szpankowski, W. (2001). Average Case Analysis of Algorithms on Sequences. John Wiley, New York. · Zbl 0968.68205
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.