On the number of f-Recurrent runs and tuples in a finite markov chain
F-Recurrent tuple is a segment of a discrete sequence with the letters obtained by sequential applying a function f to I 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 £ 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 As = E£, of the order O (sAs/n + eusvAS) for some u > 0. The Poisson and normal limit theorems for the random variable £ 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 - eA if n, s M ro such as s/n M 0, As/n M 0, and As M A. 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.
Keywords
цепь Маркова,
f-рекуррентная серия,
f-рекуррентная цепочка,
предельная теорема Пуассона,
нормальная предельная теорема,
метод Чена - Стейна,
Markov chain,
f -recurrent run,
f -recurrent tuple,
Poisson limit theorem,
normal limit theorem,
Chen - Stein methodAuthors
| Mezhennaya N. M. | N.E. Bauman Moscow State Technical University | natalia.mezhennaya@gmail.com |
Всего: 1
References
Розанов Ю.А. Случайные процессы. Краткий курс. М.: Наука, 1979. 184 с.
Михайлов В. Г. Об асимптотических свойствах числа серий событий // Тр. по дискр. ма-тем. 2006. Т. 9. С. 152-163.
Феллер В. Введение в теорию вероятностей и ее приложения. В 2-х т. Т. 1. М.: Мир, 1984. 528 с.
Савельев Л. Я., Балакин С. В., Хромов Б. В. Накрывающие серии в двоичных марковских последовательностях // Дискрет. матем. 2003. T. 15. №1. С. 50-76.
Савельев Л. Я., Балакин С. В. Некоторые применения стохастической теории серий // Сиб. журн. индустр. матем. 2012. Т. 15. №3. С. 111-123.
Тихомирова М. И. Предельные распределения числа непоявившихся цепочек одинаковых исходов // Дискрет. матем. 2008. Т. 20. №3. С. 293-300.
Erdos P. and Revesz P. On the length of the longest head-run // Topics in Inform. Theory. Colloquia Math. Soc. J. Bolyai 16 Keszthely. 1975. P. 219-228.
Fu J. C. Distribution theorem of runs and patterns associated with a sequence of multi-state trials // Statist. Sinica. 1996. V.6. P. 957-974.
Lou W. Y. W. On runs and longest runs tests: a method of finite Markov chain imbedding // J. Amer. Statist. Assoc. 1996. V.91. P. 1595-1601.
Vaggelatou E. On the length of the longest run in a multi-state Markov chain // Statist. Probab. Let. 2003. V.62. P. 211-221.
Chryssaphinou O., Papastavridis S., and Vaggelatou E. Poisson approximation for the number of non-overlapping appearances of several words in Markov chain // Combinatorics Probab. 2001. V. 10. P. 293-308.
Zhang Y. Z. and Wu X. Y. Some results associated with the longest run in a strongly ergodic Markov chain // Acta Mathematica Sinica. 2013. V.29. No. 10. P. 1939-1948.
Михайлов В. Г. О предельной теореме Б. А. Севастьянова для сумм зависимых случайных индикаторов // Обозрение прикладной и промышленной математики. 2003. Т. 10. №3. С.571-578.
Меженная Н. М. Предельные теоремы для числа плотных F-рекуррентных серий и цепочек в последовательности независимых случайных величин // Вестник Московского государственного технического университета им. Н. Э. Баумана. Сер. Естественные науки. 2014. №3. С. 11-25.
ШойтовА.М. Вероятностные модели псевдослучайных последовательностей в криптографии // Материалы Второй Междунар. науч. конф. по проблемам безопасности и противодействия терроризму. МГУ им. М.В. Ломоносова. М.: МЦНМО, 2006. С. 116-134.
Barbour A. D., HolstL., and Janson S. Poisson Approximation. Oxford: Oxford Univ. Press, 1992. 277 p.
Михайлов В. Г., Шойтов А. М. О длинных повторениях цепочек в цепи Маркова // Дискрет. матем. 2014. Т. 26. №3. С. 79-89.
Minakov A. A. Poisson approximation for the number of non-decreasing runs in Markov chains // Матем. вопр. криптогр. 2018. Т. 9. №2. С. 103-116.
