Explicit distributional results in pattern formation. (English) Zbl 0893.60005

The concept of runs, and more generally patterns, has been used in various areas. A new and unified approach is presented for constructing joint generating functions for quantities of interest associated with pattern formation in binary sequences. The methodology presented in this paper is based on first imbedding the problem into a more general one for an appropriate finite-state Markov chain with one absorbing state, and second, treating that chain by the tools of exponential families. The first step of imbedding the problem into a similar one is natural and it has been used earlier while the second step based on exponential families is new for this area. The technology presented in this article is general enough to cover all existing results in this direction for binary sequences as well as to provide explicit expressions for some patterns which were not available earlier.
Reviewer: S.Chukova (Flint)


60E10 Characteristic functions; other transforms
60J20 Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.)
60G40 Stopping times; optimal stopping problems; gambling theory
62H10 Multivariate distribution of statistics
68R99 Discrete mathematics in relation to computer science
Full Text: DOI


[1] Aki, S. and Hirano, K. (1994). Distributions of numbers of failures and successes until the first consecutive k successes. Ann. Inst. Statist. Math. 46 193-202. · Zbl 0806.60006
[2] Aki, S. and Hirano, K. (1995). Joint distributions of numbers of success-runs and failures until the first consecutive k successes. Ann. Inst. Statist. Math. 47 225-235. · Zbl 0831.60017
[3] Banjevic, D. (1994). Pattern recognition in Markov chains. In Runs and Patterns in Probability (A. P. Godbole and S. G. Papastavridis, eds.) 213-230. Kluwer, Dordrecht. · Zbl 0834.60081
[4] Barndorff-Nielsen, O. (1978). Information and Exponential Families. Wiley, Chichester. · Zbl 0387.62011
[5] Barndorff-Nielsen, O. (1980). Conditionality resolutions. Biometrika 67 293-310. JSTOR: · Zbl 0434.62005
[6] Biggins, J. D. and Cannings, C. (1987). Markov renewal processes, counters and repeated sequences in Markov chains. Adv. in Appl. Probab. 19 521-545. JSTOR: · Zbl 0629.60100
[7] Bishop, D. T., Williamson, J. A. and Skolnick, M. H. (1983). A model for restriction fragment length distributions. American Journal of Human Genetics 35 795-815.
[8] Blom, G. and Thorburn, D. (1982). How many random digits are required until given sequences are obtained? J. Appl. Probab. 19 518-531. JSTOR: · Zbl 0493.60071
[9] Breen, S., Waterman, M. S. and Zhang, N. (1985). Renewal theory for several patterns. J. Appl. Probab. 22 228-234. JSTOR: · Zbl 0564.60081
[10] Brown, L. (1986). Fundamentals of Statistical Exponential Families. IMS, Hay ward, CA. · Zbl 0685.62002
[11] Chry ssaphinou, O. and Papastavridis, S. (1988). A limit theorem on the number of overlapping appearances of a pattern in a sequence of independent trials. Probab. Theory Related Fields 79 129-143. · Zbl 0631.60027
[12] Chry ssaphinou, O. and Papastavridis, S. (1990). The occurrence of a sequence of patterns in repeated dependent experiments. Theory Probab. Appl. 35 167-173. · Zbl 0724.60082
[13] Feller, W. (1950). An Introduction of Probability Theory and Its Applications 1. Wiley, New York. · Zbl 0039.13201
[14] Fu, J. C. and Koutras, M. V. (1994). Distribution theory of runs: a Markov chain approach. J. Amer. Statist. Assoc. 89 1050-1058. JSTOR: · Zbl 0806.60011
[15] Gardner, M. (1988). Time Travel and Other Mathematical Bewilderments. W. H. Freeman, New York. · Zbl 0641.00005
[16] Gerber, H. and Li, S-Y. R. (1981). The occurrence of sequence patterns in repeated experiments and hitting times in a Markov chain. Stochastic Process. Appl. 11 101-108. · Zbl 0449.60050
[17] Godbole, A. P. and Schaeffner, A. A. (1993). Improved Poisson approximation for word patterns. Adv. in Appl. Probab. 25 334-347. JSTOR: · Zbl 0772.60013
[18] Guibas, L. J. and Odly zko, A. M. (1980). Long repetitive patterns in random sequences. Z. Wahrsch. Verw. Gebiete 53 241-262. · Zbl 0424.60036
[19] Guibas, L. J. and Odly zko, A. M. (1981). String overlaps, pattern matching, and nontransitive games. J. Combin. Theory A 30 183-208. · Zbl 0454.68109
[20] Li, S-Y. R. (1980). A martingale approach to the study of occurrence of sequence patterns in repeated experiments. Ann. Probab. 8 1171-1176. · Zbl 0447.60006
[21] Ling, K. D. (1988). On binomial distributions of order k. Statist. Probab. Lett. 6 247-250. · Zbl 0638.60024
[22] Mohanty, S. G. (1994). Success runs of length k in Markov dependent trials. Ann. Inst. Statist. Math. 46 777-796. · Zbl 0824.60016
[23] Mood, A. M. (1940). The distribution theory of runs. Ann. Math. Statist. 11 367-392. · Zbl 0024.05301
[24] Schbath, S. (1995). Compound Poisson approximation of word counts in DNA sequences. ESAIM: Probability and Statistics 1 1-16. · Zbl 0869.60067
[25] Stefanov, V. T. (1991). Noncurved exponential families associated with observations over finite state Markov chains. Scand. J. Statist. 18 353-356. · Zbl 0798.62096
[26] Stefanov, V. T. (1995). Explicit limit results for minimal sufficient statistics and maximum likelihood estimators in some Markov processes: exponential families approach. Ann. Statist. 23 1073-1101. · Zbl 0852.62076
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.