Geodesic
Pattern correlation matrices for Markov sequences and tests of randomness
Teoriâ veroâtnostej i ee primeneniâ, Tome 51 (2006) no. 4, pp. 712-731 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The paper establishes some properties of the so-called pattern correlation matrices which are useful in statistical analysis of random Markov sequences. Asymptotic expansions for the probability of the occurrence of a given word a given number of times and of joint occurrences for two words are derived. These expansions give accurate approximations for the first two moments of the number of occurrences. The covariance matrix of the joint distribution of frequencies of all patterns is expressed in terms of the pattern correlation matrix, and a simple generalized inverse of this covariance matrix is given. Relevant statistical implications for goodness-of-fit testing are formulated.
Keywords: asymptotic expansions, resolvent, generating function, $\chi$-square, fundamental matrix.
Mots-clés : pseudo-inverse matrix 
@article{TVP_2006_51_4_a3,
     author = {A. L. Rukhin},
     title = {Pattern correlation matrices for {Markov} sequences and tests of randomness},
     journal = {Teori\^a vero\^atnostej i ee primeneni\^a},
     pages = {712--731},
     year = {2006},
     volume = {51},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TVP_2006_51_4_a3/}
}
TY  - JOUR
AU  - A. L. Rukhin
TI  - Pattern correlation matrices for Markov sequences and tests of randomness
JO  - Teoriâ veroâtnostej i ee primeneniâ
PY  - 2006
SP  - 712
EP  - 731
VL  - 51
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/TVP_2006_51_4_a3/
LA  - ru
ID  - TVP_2006_51_4_a3
ER  - 
%0 Journal Article
%A A. L. Rukhin
%T Pattern correlation matrices for Markov sequences and tests of randomness
%J Teoriâ veroâtnostej i ee primeneniâ
%D 2006
%P 712-731
%V 51
%N 4
%U http://geodesic.mathdoc.fr/item/TVP_2006_51_4_a3/
%G ru
%F TVP_2006_51_4_a3
A. L. Rukhin. Pattern correlation matrices for Markov sequences and tests of randomness. Teoriâ veroâtnostej i ee primeneniâ, Tome 51 (2006) no. 4, pp. 712-731. http://geodesic.mathdoc.fr/item/TVP_2006_51_4_a3/

[1] Billingsley P., Statistical Inference for Markov Processes, Univ. of Chicago Press, Chicago, 1961, 75 pp. | MR | Zbl

[2] Belyaev P. F., “O veroyatnosti nepoyavleniya zadannogo chisla $s$-tsepochek v slozhnykh tsepyakh Markova”, Teoriya veroyatn. i ee primen., 10:3 (1965), 547–551

[3] Brainerd B., Chang S. M., “Number of occurrences in two-state Markov chains, with an application in linguistics”, Canad. J. Statist., 10:3 (1982), 225–231 | DOI | MR

[4] Good I. J., “The serial test for sampling numbers and other tests for randomness”, Proc. Cambridge Philos. Soc., 49 (1953), 276–284 | DOI | MR | Zbl

[5] Good I. J., “Quadratics in Markov-chain frequencies and the binary chain of order 2”, J. Roy. Statist. Soc. Ser. B, 25 (1963), 383–391 | MR | Zbl

[6] Guibas L., Odlyzko A., “String overlaps, pattern matching and nontransitive games”, J. Combin. Theory, 30:2 (1981), 183–208 | DOI | MR | Zbl

[7] Kemeni Dzh. Dzh., Snell Dzh. L., Konechnye tsepi Markova, Nauka, M., 1970, 271 pp.

[8] Kolchin V. F., Sevastyanov B. A., Chistyakov V. P., Sluchainye razmescheniya, Nauka, M., 1976, 223 pp. | MR

[9] Marsaglia G., “A current view of random number generation”, Computer Science and Statistics, Proceedings of the Sixteenth Symposium on the Interface, Elsevier, New York, 1985, 3–10

[10] Mikhailov V. G., “Asimptoticheskaya normalnost v skheme konechno-zavisimogo razmescheniya chastits po yacheikam”, Matem. sb., 119(161):4(12) (1982), 509–520 | MR

[11] Mikhailov V. G., “Ob asimptoticheskoi normalnosti simmetricheskikh razdelimykh statistik ot chastot $m$-tsepochek”, Diskretn. matem., 1:4 (1989), 92–103 | MR

[12] Odlyzko A., “Asymptotic enumeration methods”, Handbook of Combinatorics, ed. R. L. Graham, M. Grötshel, and L. Lovácz, Elsevier, Amsterdam, 1995, 1063–1229 | MR | Zbl

[13] Rao C. R., Mitra S. K., Generalized Inverse of Matrices and its Applications, Wiley, New York, 1971, 240 pp. | MR

[14] Reinert G., Schbath S., Waterman M. G., “Probabilistic and statistical properties of words: an overview”, J. Comput. Biol., 7:1–2 (2000), 1–46 | DOI

[15] Regnier M., Szpankowski W., “On pattern frequency occurrences in a Markovian sequence”, Algorithmica, 22:4 (1998), 631–649 | DOI | MR | Zbl

[16] Rukhin A. L., “Testing randomness: a suite of statistical procedures”, Teoriya veroyatn. i ee primen., 45:1 (2000), 137–162 | MR | Zbl

[17] Rukhin A. L., “Distribution of the number of words with a prescribed frequency and tests of randomness”, Adv. in Appl. Probab., 34:4 (2002), 775–797 | DOI | MR | Zbl

[18] Solovev A. D., “Odno kombinatornoe tozhdestvo i ego primenenie k zadache o pervom nastuplenii redkogo sobytiya”, Teoriya veroyatn. i ee primen., 11:2 (1966), 313–320 | MR

[19] Szpankowski W., Average Case Analysis of Algorithms on Sequences, Wiley-Interscience, New York, 2001, 551 pp. | MR

[20] Tikhomirova M. I., Chistyakov V. P., “Ob asimptotike momentov chisla nepoyavivshikhsya $s$-tsepochek”, Diskretn. matem., 9:1 (1997), 12–29 | MR | Zbl

[21] Tikhomirova M. I., Chistyakov V. P., “O statisticheskikh kriteriyakh otsutstvuyuschikh 3-gramm”, Trudy po diskretnoi matematike, 1, TVP, M., 1997, 265–278 | MR | Zbl