О числе f-рекуррентных серий и цепочек в конечной цепи Маркова | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/4

О числе f-рекуррентных серий и цепочек в конечной цепи Маркова

Будем называть /-рекуррентной цепочкой отрезок дискретной последовательности, знаки которого получаются последовательным применением функции / к l предыдущим знакам, а цепочку, которую нельзя продлить ни в одну сторону с сохранением свойства /-рекуррентности, - /-рекуррентной серией. При помощи метода Чена - Стейна получена оценка расстояния по вариации между распределением числа £ /-рекуррентных серий длины не меньше s в отрезке длины n конечной эргодической стационарной цепи Маркова и сопровождающим законом распределения Пуассона, т. е. распределением Пуассона с параметром As = E£, порядка O(sAs/n + euss/A~s) при некотором u > 0. Из этой оценки стандартными методами выведены пуассоновская и нормальная предельные теоремы для случайной величины £ (при стремлении длины n отрезка цепи Маркова и параметра s к бесконечности). Также полученная оценка позволяет показать, что вероятность наличия /-рекуррентных цепочек длины не меньше s стремится к 1 - eA, если n, s ^ те так, что s/n ^ 0, As/n ^ 0 и As ^ A. Свойства распределений частот /-рекуррентных серий или цепочек с определёнными свойствами могут быть использованы при разработке статистических критериев для проверки качества псевдослучайных последовательностей.

On the number of f-Recurrent runs and tuples in a finite markov chain.pdf Пусть {Xj, j - 1,...,n} - эргодическая стационарная цепь Маркова с множеством состояний An - {1,...,N}, N ^ 2, матрицей переходных вероятностей P - - ||pa,bHa,beAN и распределением вероятностей {па,а Е AN}. Элементы матрицы Pn обозначим p^, ^ - Ра,ь. Известно [1, ч. 2, § 2, с. 100], что существуют константы С, y > 0, при которых |pOnb - пь| ^ Спьe-Yn, n > 1. (1) Пусть f : AN ^ AN -числовая функция, s ^ 2. Приведём определение f-рекуррентной цепочки и серии [2]. Определение 1. Случайные величины Xj+1,... , Xj+1+s образуют f -рекуррентную цепочку длины не меньше s, если Xj+l+1 - f (Xjj . . . j Xj+i-1)j . . . j Xj+l+s - f (Xj+sj . . . j Xj+1+s-1). (2) Определение 2. Случайные величины Xj,... ,Xj+1+s образуют f -рекуррентную серию длины не меньше s, если Xj+i - f (Xjj...j Xj+i-1) j (3) Xj+l+1 - f (Xj+1j . . . j Xj+1)j . . . j Xj++s - f (Xj+sj . . . j Xj+1+s-1). Обозначим Aj и Bj индикаторы событий (2) и (3) соответственно. Определение f-рекуррентной серии обобщает известное определение серии из одинаковых знаков [3, с. 62]. Действительно, если l - 1, функция f = а, а Е An, то Bj - {Xj+1 - aj Xj+2 - aj . . . j Xj+s+1 - а} и f -рекуррентная серия длины не меньше s совпадает с обычной серий знаков a длины не меньше s. Точные распределения чисел серий в двоичных марковских цепях изучены в [4, 5], а их предельные распределения в цепях Маркова с любым числом состояний получены в [6]. Распределение длины наибольшей серии одинаковых знаков рассмотрено в [7-9] для последовательности независимых случайных величин, в [10-12] -для цепи Маркова. Распределение числа f-рекуррентных серий в последовательности независимых случайных величин изучено в [2, 13]. В [14] получены аналогичные результаты для f-рекуррентных серий с возможными пропусками знаков. Большинство современных криптографических систем предполагает использование псевдослучайных последовательностей, обладающих свойствами, близкими к свойствам случайных равновероятных последовательностей. Для оценки их качества используются различные статистические критерии, в том числе основанные на статистиках от частот значений функций от s-цепочек: тест частот встречаемости s-грамм, покер-тест, тест линейной сложности, тест ранга случайной матрицы, тест интервалов и др. [15]. Для построения таких критериев могут быть использованы и частоты появлений f-рекуррентных цепочек и серий при подходящем выборе функции f. Будем считать, что задана функция f от l ^ 1 переменных. Пусть Г = {1,..., n - s - l}; {aj = : j G Г} и {в = IBj : j G Г} -наборы случайных индикаторов, соответствующих событиям {Aj : j G Г} и {Bj : j G Г}; Qs = P{Bj} - вероятность любого события из набора {Bj : j G Г}. n-s Определим случайную величину £ = £ в, равную числу f-рекуррентных серий j=i в {Xj, j = 1,..., n}, и её математическое ожидание As = E£ = (n - s - l)Qs, а такn- s же случайную величину £ * = £ aj, равную числу f -рекуррентных цепочек в {Xj, j=i j = 1,...,n}. Будем использовать следующие обозначения: L(£) -для закона распределения случайной величины £; Pois(A) -для распределения Пуассона с параметром A; N(0,1) - для стандартного нормального распределения; р (L(£), L(n)) -для расстояния по вариации между L(£) и L(n). Для неотрицательных целочисленных случайных величин ni и n2 оно задаётся формулой 1 те р (L(ni), L(n2)) = 1 Е |P{ni = u} - Р{П2 = u}|. 2 u=0 Теорема 1. Пусть s, l, m ^ 1 и As ^ 1. Тогда р(L(£),Pois(As)) ^ ^2(s + l + 2m) + 1 + е^2-^ Qs+ +Се-7(т+1)УА^ (2 + Ce-7(m+i) + e-Y(s+1+m+i)) , где константы C и y определены в (1). Следствие 1. Пусть число l ^ 1 фиксировано, s,n ^ то, так что s --> 0, Qs ^ 0, As ^ A G (0, то). n Тогда 1) L(£) ^ Pois(A); 2) Р{£* ^ 1} ^ 1 - е-л. Следствие 2. Пусть число l ^ 1 фиксировано, s,n ^ то, так что s As ^ то, -As ^ 0, n и существует константа u > 0, для которой As = o(eus). Тогда L (^)

Ключевые слова

цепь Маркова, f-рекуррентная серия, f-рекуррентная цепочка, предельная теорема Пуассона, нормальная предельная теорема, метод Чена - Стейна, Markov chain, f -recurrent run, f -recurrent tuple, Poisson limit theorem, normal limit theorem, Chen - Stein method

Авторы

ФИООрганизацияДополнительноE-mail
Меженная Наталья МихайловнаМосковский государственный технический университет им. Н. Э. Бауманакандидат физико-математических наук, доцент, доцент кафедры прикладной математикиnatalia.mezhennaya@gmail.com
Всего: 1

Ссылки

Розанов Ю.А. Случайные процессы. Краткий курс. М.: Наука, 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.
 О числе f-рекуррентных серий и цепочек в конечной цепи Маркова | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/4

О числе f-рекуррентных серий и цепочек в конечной цепи Маркова | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/4