On the number of $f$-recurrent runs and tuples in a finite Markov chain

N. M. Mezhennaya

Prikladnaya Diskretnaya Matematika. Supplement, no. 12 (2019), pp. 18-21.

Résumé

$f$-Recurrent tuple is a segment of a discrete sequence with the letters obtained by sequential applying a function $f$ to $l$ previous letters, and $f$-recurrent run is a tuple that cannot be extended in both directions while maintaining the $f$-recurrence property. Using the Chen–Stein method, we obtain the estimate for the total variation distance between the distribution of the number $\xi$ of $f$-recurrent runs of at least $s$ length in a segment of a finite stationary ergodic Markov chain of length $n$ and the accompanying Poisson distribution, i.e., Poisson distribution with parameter $\lambda_s=\mathsf{E} \xi$, of the order O$\left(s \lambda_s/n+\text{e}^{u s} \sqrt{\lambda_s}\right)$ for some $u>0$. The Poisson and normal limit theorems for the random variable $\xi$ are derived from the estimate by standard methods (as the length $n$ of a segment of a Markov chain and parameter $s$ tend to infinity). Moreover, the estimate results in that the probability for the presence of $f$-recurrent tuples of at least $s$ length tends to $1-\text{e}^{\lambda}$ if $n,s\to \infty$ such as $s/n\to 0$, $\lambda_s/n \to 0$, and $\lambda_s\to \lambda$. The properties of distributions of frequencies of $f$-recurrent runs or tuples with certain parameters can be used in the development of statistical tests for the quality of pseudo-random sequences.

Détail

Mots-clés : Markov chain, Poisson limit theorem
Keywords: $f$-recurrent run, $f$-recurrent tuple, normal limit theorem, Chen–Stein method.

Bibliographie

[1] Rozanov Yu. A., Sluchainye protsessy. Kratkii kurs, Nauka, M., 1979, 184 pp.

[2] Mikhailov V. G., “Ob asimptoticheskikh svoistvakh chisla serii sobytii”, Tr. po diskr. matem., 9 (2006), 152–163

[3] Feller V., Vvedenie v teoriyu veroyatnostei i ee prilozheniya, V 2-kh t., v. 1, Mir, M., 1984, 528 pp. | MR

[4] Savelev L. Ya., Balakin S. V., Khromov B. V., “Nakryvayuschie serii v dvoichnykh markovskikh posledovatelnostyakh”, Diskret. matem., 15:1 (2003), 50–76 | DOI | Zbl

[5] Savelev L. Ya., Balakin S. V., “Nekotorye primeneniya stokhasticheskoi teorii serii”, Sib. zhurn. industr. matem., 15:3 (2012), 111–123 | MR | Zbl

[6] Tikhomirova M. I., “Predelnye raspredeleniya chisla nepoyavivshikhsya tsepochek odinakovykh iskhodov”, Diskret. matem., 20:3 (2008), 293–300 | DOI | MR | Zbl

[7] Erdos P., Revesz P., “On the length of the longest head-run”, Topics in Inform. Theory, Colloquia Math. Soc. J. Bolyai, 16, Keszthely, 1975, 219–228 | MR

[8] Fu J. C., “Distribution theorem of runs and patterns associated with a sequence of multi-state trials”, Statist. Sinica, 6 (1996), 957–974 | MR | Zbl

[9] Lou W. Y. W., “On runs and longest runs tests: a method of finite Markov chain imbedding”, J. Amer. Statist. Assoc., 91 (1996), 1595–1601 | DOI | MR | Zbl

[10] Vaggelatou E., “On the length of the longest run in a multi-state Markov chain”, Statist. Probab. Let., 62 (2003), 211–221 | DOI | MR | Zbl

[11] Chryssaphinou O., Papastavridis S., Vaggelatou E., “Poisson approximation for the number of non-overlapping appearances of several words in Markov chain”, Combinatorics Probab., 10 (2001), 293–308 | DOI | MR | Zbl

[12] Zhang Y. Z., Wu X. Y., “Some results associated with the longest run in a strongly ergodic Markov chain”, Acta Mathematica Sinica, 29:10 (2013), 1939–1948 | DOI | MR | Zbl

[13] Mikhailov V. G., “O predelnoi teoreme B. A. Sevastyanova dlya summ zavisimykh sluchainykh indikatorov”, Obozrenie prikladnoi i promyshlennoi matematiki, 10:3 (2003), 571–578 | MR

[14] Mezhennaya N. M., “Predelnye teoremy dlya chisla plotnykh $F$-rekurrentnykh serii i tsepochek v posledovatelnosti nezavisimykh sluchainykh velichin”, Vestnik Moskovskogo gosudarstvennogo tekhnicheskogo universiteta im. N. E. Baumana. Ser. Estestvennye nauki, 2014, no. 3, 11–25 | Zbl

[15] Shoitov A. M., “Veroyatnostnye modeli psevdosluchainykh posledovatelnostei v kriptografii”, Materialy Vtoroi Mezhdunar. nauch. konf. po problemam bezopasnosti i protivodeistviya terrorizmu (MGU im. M. V. Lomonosova), MTsNMO, M., 2006, 116–134

[16] Barbour A. D., Holst L., Janson S., Poisson Approximation, Oxford Univ. Press, Oxford, 1992, 277 pp. | MR | Zbl

[17] Mikhailov V. G., Shoitov A. M., “O dlinnykh povtoreniyakh tsepochek v tsepi Markova”, Diskret. matem., 26:3 (2014), 79–89 | DOI

[18] Minakov A. A., “Poisson approximation for the number of non-decreasing runs in Markov chains”, Matem. vopr. kriptogr., 9:2 (2018), 103–116 | DOI | MR