×

A limit theorem on the number of overlapping appearances of a pattern in a sequence of independent trials. (English) Zbl 0631.60027

A sequence of independent experiments is performed, each one producing a letter from a given alphabet. We study the number of overlapping appearances of a given pattern of letters and we prove that, under quite general conditions, the number of overlapping appearances of long patterns is approximately distributed according to a Polya-Aeppli distribution.

MSC:

60F05 Central limit and other weak theorems
60C05 Combinatorial probability
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Barbour, A.D., Eagleson, G.K.: Poisson convergence for dissociated statistics. J.R. Statist. Soc. B 46, 397-402 (1984) · Zbl 0567.62062
[2] Benevento, R.V.: The occurrence of sequence patterns in ergodic Markov chains. Stochastic Processes Appl. 17, 369-373 (1984) · Zbl 0535.60057 · doi:10.1016/0304-4149(84)90012-7
[3] Blom, G., Thorburn, D.: How many random digits are required until given sequences are obtained? Appl. Probab. 19, 518-531 (1982) · Zbl 0493.60071 · doi:10.2307/3213511
[4] Chrysaphinou, O., Papastavridis, S.: A limit theorem for the number of non-overlapping occurrences of a pattern in a sequence of independent trials. J. Appl. Probab. 25 (1988) · Zbl 0631.60027
[5] Erd?s, P., R?v?sz, P.: On the length of the longest head-run. Colloq. Math. Soc. Janos Bolyai, Keszthely 16, 219-228 (1975)
[6] Feller, W.: An introduction to probability theory and its application. New York: Wiley 1968 · Zbl 0155.23101
[7] F?ldes, A.: The limit distribution of the length of the longest head-run. Period. Math. Hung. 10, 301-310 (1970) · Zbl 0414.60034 · doi:10.1007/BF02020027
[8] Gerber, H.U., Li, S.-Y.: The occurrence of sequence patterns in repeated experiments and hitting times in a Markov chain. Stochastic Processes Appl. 11, 101-108 (1981) · Zbl 0449.60050 · doi:10.1016/0304-4149(81)90025-9
[9] Guibas, L.J., Odlyzko, A.M.: Maximal prefix-synchronized codes. SIAM J. Appl. Math. 35, 401-418 (1978) · Zbl 0394.94024 · doi:10.1137/0135034
[10] Guibas, L.J., Odlyzko, A.M.: Long repetive patterns in random sequences. Z. Wahrscheinlichkeitstheor. Verw. Geb. 53, 241-262 (1980) · Zbl 0424.60036 · doi:10.1007/BF00531434
[11] Guibas, L.J., Odlyzko, A.M.: Periods of strings. J. Comb. Theory Ser. A, 30, 19-42 (1981) · Zbl 0464.68070 · doi:10.1016/0097-3165(81)90038-8
[12] Guibas, L.J., Odlyzko, A.M.: String overlaps, pattern matching and non-transitive games. J. Comb. Theory Ser. A, 30, 183-208 (1981) · Zbl 0454.68109 · doi:10.1016/0097-3165(81)90005-4
[13] Johnson, N.L., Kotz, S.: Discrete distributions. Boston: Houghton Mifflin 1969 · Zbl 0292.62009
[14] Koml?s, J., Tusn?dy, G.: On sequences of ?pure heads?. Ann. Probab. 3, 608-617 (1975) · Zbl 0335.60022 · doi:10.1214/aop/1176996304
[15] Nemetz, T., Kusolitsch, N.: On the longest run of coincidences. Z. Wahrscheinlichkeitstheor. Verw. Geb. 61, 59-73 (1982) · Zbl 0491.05009 · doi:10.1007/BF00537225
[16] R?v?sz, P.: Strong theorems on coin tossing. Proc. 1978 Int. Congress of Mathematicians, Helsinki, pp. 749-754 (1980)
[17] Samarova, S.S.: On the length of the longest head-run for a Markov chain with two states. Theory Probab. Appl. 26, 498-509 (1981) · Zbl 0487.60061 · doi:10.1137/1126056
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.