Предельные теоремы в задачах о плотном вложении и плотных сериях в дискретных случайных последовательностях

Введение
0 ВВЕДЕНИЕ 3
1 ОЦЕНКИ ДЛЯ ВЕРОЯТНОСТИ ПЛОТНОГО ВЛОЖЕНИЯ ОДНОЙ ДИСКРЕТНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ В ДРУГУЮ ' 10
1.1 Постановка задачи и формулировки результатов 10
1.2 Точные значения вероятности плотного вложения 12
1.3 Доказательство теорем 1.1 и 1.3 14
1.4 Доказательство теорем 1.2 и 1.4 19
1.5 Доказательства вспомогательных утверждений 22
1.6 Проверка гипотезы о плотном вложении 26
2 ПРЕДЕЛЬНЫЕ ТЕОРЕМЫ ДЛЯ ЧИСЛА ПЛОТНЫХ СЕРИЙ В СЛУЧАЙНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ 41
2.1 Предварительные замечания 41
2.2 О методе доказательства многомерных предельных теорем пуассоновского типа 43
2.3 Вероятность появления плотно заполненной серии заданной длины 52
2.4 Оценки расстояния по вариации -1 55
2.5 Оценки расстояния по вариации - 2 ] 60
2.6 Предельные теоремы для числа длинных плотных серий 67
2.7 Асимптотическое поведение распределения наибольших длин плотных серий 69
2.8 Предельная теорема для числа плотных серий большого веса 72
2.9 Формулы для вычисления точных распределений числа плотных серий 76
2.10 Оценивание точности пуассоновской аппроксимации 82
3 ЗАКЛЮЧЕНИЕ 87
4 СПИСОК ЛИТЕРАТУРЫ 91
Введение [
О Введение
Исследование свойств дискретных случайных последовательностей является одной из центральных задач теории вероятностей. Такие задачи тесно связаны с приложениями. Полученные результаты применяются для решения ряда экономических, технических, биологических, криптографических и других задач.
Одной из таких задач является изучение статистических свойств специальных комбинаций в дискретных случайных последовательностях. В диссертации в качестве специальных комбинаций рассматриваются плотно вложенные последовательности. Понятие плотного вложения было введено в
математическую литературу в работе (ХюНс, 1996). Пусть Хп = {х,}^ и
Ут = {у^_1 - последовательности знаков алфавита = {0, —,/V-1}. Согласно
(СоНс, 1996), последовательность Хп плотно вкладывается в начало
последовательности Ут, если п<т и найдутся такие натуральные числа
1 = Л <Л <•••</,-т> Л+1 - Л е {1,2), к = 1,...,п-1, (0.1)
что хк=у^,к = 1,...,п.
Понятие плотного вложения возникает при изучении свойств
последовательностей, генерируемых конечными автоматами из нескольких параллельно функционирующих блоков, выходные последовательности которых соединяются в одну общую последовательность без нарушения порядка
следования букв. Например, если генератор случайных' чисел состоит из двух блоков, в последовательность, вырабатываемую первы|ч блоком, добавляются знаки, выработанные вторым блоком, причем не более одного знака подряд, то выходная последовательность первого блока будет плотно вложена в выходную последовательность генератора. Роль этого свойства при изучении генераторов случайных чисел описана в работах Доукоугс, 1991), (СоНс, 1991), (СоНс, 1996).
Введение [
Качество сгенерированной случайной последовательности определяется близостью ее свойств к свойствам последовательности независимых случайных величин, равномерно распределенных на множестве знаков выходного алфавита. Для описанного выше класса генераторов одним из способов проверки его свойств является использование статистик, связанных с плотно вложенными последовательностями.
Диссертация посвящена выводу оценок и предельных соотношений для вероятности плотного вложения заданной последовательности и для распределений ряда случайных величин, связанных с задачей о плотном вложении.
Первая интересующая нас задача состоит в определении вероятности плотного вложения Рт(Хп) заданной последовательности Хп в начало
последовательности Ут, образованной независимыми случайными величинами, равномерно распределенными на множестве АВ случае двоичных последовательностей (/V = 2) верхняя оценка вероятности Рт[Х„) была получена в работе (Сойс, 1996). В первой главе диссертации получено обобщение результата (СоЙс, 1996) на случай конечного алфавита ЛЛ, с произвольным
числом букв Р^Х"'). Также построена оценка снизу для вероятности Рт[Хп) и
указаны классы последовательностей, на которых эти оценки достигаются. Приведены вытекающие из этих оценок предельные соотношения для вероятности плотного вложения, когда растут параметры п и т. В частности, получено предельное равенство для логарифма вероятности плотного вложения Рт(Хп) в схеме серий, когда размер алфавита также растет.
Нижняя оценка вероятности Рт[Хп] достигается на последовательностях
Хп, состоящих из п одинаковых знаков. Значит, при проверке гипотезы о том, что
заданная последовательность была плотно вложена в наблюдаемую случайную последовательность первое внимание следует уделять участкам выходной последовательности, в которые плотно вкладывались цепочки или серии одинаковых знаков.
Серии в достаточной для многих приложений, степени отражают
Введение 1 î)
статистические свойства случайной последовательности. Различные применения свойств серий в статистике хороню известны.
Одним из наиболее известных примеров является статистика критерия однородности Вальда-Вольфовица, предложенного в работе (Wald, 1940). Показано, что статистика, равная числу серий в объединенном вариационном ряду, построенном по двум независимым выборкам с непрерывными распределениями, может быть успешно применена для обнаружения малых систематических различий в их распределениях.
Задача о числе серий успехов в последовательности Бернулли хорошо известна в литературе. Одно из первых упоминаний этой задачи в контексте пуассоновской аппроксимации содержится в статье (von Mises, 1921). В дальнейшем было изучено предельное распределение цепочек из единиц, длины максимальной серии из единиц, времени до первого появления серии заданной длины и ряда сопутствующих величин (см., например, (Arratia, 1990), (Arratia,
1989), (Godbole, 1991) и др.). Подробное освещение этих вопросов имеется в разделах А и В книги (Balakrishnan N., 2002)). Рассматривались обобщения этих задач на более общие случайные последовательности, в частности, на цепи Маркова (см., например, (Самарова, 1981), (Савельев, 2003) и др.).
Понятие серии получило ряд обобщений. Например, в работе (Wolfowitz, 1944) было введено понятие монотонной серии как серии, образованной знаками последовательных разностей элементов случайной последовательности. Их изучению посвящены работы (Eagle, 1995), (GIaz, 1999), (Balakrishnan, 2002), (Chryssaphinou, 2001), (Меженная, 2007) и др.).
Важным для приложений обобщением задачи о сериях является задача изучения свойств дискретных сканирующих статистик. В книге (Balakrishnan, 2002) сканирующая статистика определена как максимальное число успехов, содержащихся в скользящем окне заданной длины. Подробный анализ этой задачи содержится в книгах (Balakrishnan, 2002), (GIaz, 1999), (Glaz, 2001). Подобные статистики получили широкое применение в генетике, биостатистике, контроле качества и ряде других областей. В частности, широкое применение получили статистики, являющиеся функциями от числа цепочек, обладающих некоторым свойством, которые появились в дискретной случайной
Введение [
последовательности. Интерес в таких задачах представляют как точные оценки для изучаемых величин, так и предельное поведение их распределений.
Задача об асимптотическом распределении числа цепочек, обладающих заданным свойством, рассматривалась многими авторами (см., например, (Arratia,
1990), (Barbour, 1987), (Barbour, 2002), (Chryssaphinou, 2001), (Erchardsson, 2005), (Fuchs, 1965), (Godbole, 1991), (Rajarshi, 1974),, (Barbour, 1992) и др.).
Вернемся к задаче о плотном вложении. Сериям одинаковых знаков во вкладываемой последовательности при плотном вложении соответствуют комбинации в результирующей последовательности генератора, которые в диссертации названы плотными сериями.
Отрезок последовательности xlt..,,xk из знаков алфавита AN мы называем
плотно заполненным знаком as=.AN, если ae{xi,xj+1},/ = — 1, то есть
пропуски между знаками а в нем могут состоять не более чем из одного символа отличного от а, и на концах содержится не более одного знака из Av\{a}.
Распределение числа плотно заполненных отрезков в случайной последовательности можно вывести из распределения числа плотно заполненных серий. Плотно заполненный (знаком а) отрезок назовем плотно заполненной ('знаком a J серией (или просто плотной а‘Серией), если он не содержится ни в каком плотно заполненном отрезке большей длины. Длиной плотной а-серии назовем длину минимального отрезка, содержащего все знаки плотной а -серии. Число входящих в плотную а -серию знаков а будем называть ее весом.
Вторая глава диссертации посвящена выводу предельных теорем для распределений числа плотных серий большой длины и числа плотных серий большого веса в последовательности независимых одинаково распределенных случайных величин со значениями в конечном алфавите.
Постановки задач для плотных серий в настоящей работе аналогичны классическим постановкам задач для серий успехов в последовательности Бернулли (это используется в доказательствах). Нас интересовала возможность использования пуассоновской аппроксимации (в том числе и многомерной) для распределений числа плотных 1-серий.
Основными объектами исследования во второй главе диссертации являются
Введение [
случайные величины д:Т и £5Т, равные числу плотных 1-серий, которые начинаются в моменты от 1 до Т и имеют длину 5 и не меньше 5 соответственно, и случайные величины д[чГ и £',т, равные числу плотных 1-
серий, которые начинаются в моменты от 1 до Г и имеют вес \м и не меньше и/ соответственно. Доказаны многомерные предельные теоремы Пуассона для случайных векторов И при
Т—>00 и согласованном изменении других параметров. В первом случае с помощью функциональной версии метода Чена-Стейна также получены явные оценки точности пуассоновской аппроксимации.
Из этих теорем и оценок выведено совместное предельное распределение нескольких старших членов вариационного ряда из длин (весов) плотных 1-серий. Этот результат может быть использован при построении критерия проверки качества случайной последовательности. Например, в работе (ВаЫтБИпап, 2002) вектор из нескольких старших членов вариационного ряда длин обычных серий единиц и длин обычных серий нулей использовался для построения оценки изменяющейся вероятности успеха в последовательности Бернулли.
Так как предельные теоремы и оценки точности применимы лишь при достаточно больших значениях параметров, интерес представляет разработка методов вычисления точных распределений изучаемых случайных величин при конкретных значениях параметров. В работах (Би, 1994), (Би, 2003), (Би, 2001) для аналогичной задачи относительно числа серий в случайных последовательностях с двумя состояниями использовался подход, основанный на аппарате цепей Маркова. Этот метод оказался полезным и в нашем случае. В диссертации построены рекуррентные формулы для вычисления распределений случайных величин £кт и в неоднородной цепи Маркова с двумя состояниями. С их
помощью удалось на конкретных примерах определить реальную точность пуассоновской аппроксимации для этих величин в равновероятной последовательности Бернулли, и, тем самым, продемонстрировать точность предельных теорем. ;