Введение к работе
Актуальность.
Исследование свойств дискретных случайных
последовательностей является одной из центральных задач теории вероятностей. Такие задачи тесно связаны с приложениями. Одной из таких задач является изучение статистических свойств специальных комбинаций в дискретных случайных последовательностях. В диссертации в качестве специальных комбинаций рассматриваются плотно вложенные последовательности.
Понятие плотного вложения было введено в математическую
литературу в работе (Golic, 1996]. Пусть Хп={х(}" и Ут = (.7,-}^ -последовательности знаков алфавита AN = {О,...,N-1}. Согласно (Golic, 1996], последовательность Хп плотно вкладывается в начало последовательности Ym, если п<т и найдутся такие натуральные числа
1 = Л < h < < h ^ т> Л+1 - Л є {1,2}, /с = 1,.. .,п -1, [1] что xk = yjk,k = l,...,n.
Понятие плотного вложения возникает при изучении свойств последовательностей, генерируемых конечными автоматами из нескольких параллельно функционирующих блоков, выходные последовательности которых соединяются в одну общую последовательность без нарушения порядка следования букв. Роль этого свойства при изучении генераторов случайных чисел описана в работах (Zivkovic, 1991], [Golic, 1991],
(Golic, 1996].
Качество случайной последовательности определяется близостью ее свойств к свойствам последовательности независимых случайных величин, равномерно распределенных на множестве знаков выходного алфавита. Для описанного выше класса генераторов одним из способов проверки его свойств является использование статистик, связанных с плотно вложенными последовательностями.
Диссертация посвящена выводу оценок и предельных соотношений для вероятности плотного вложения заданной последовательности и для распределений ряда случайных величин, связанных с задачей о плотном вложении.
Серии в достаточной для многих приложений степени
отражают статистические свойства случайной
последовательности. Задача о числе серий успехов в последовательности Бернулли хорошо известна в литературе. Одно из первых упоминаний этой задачи в контексте пуассоновской аппроксимации содержится в статье (von Mises, 1921]. В дальнейшем было изучено предельное распределение цепочек из единиц, длины максимальной серии из единиц, времени до первого появления серии заданной длины и ряда сопутствующих величин (см., например, (Arratia, 1990], (Arratia, 1989], (Godbole, 1991], (Rajarshi, 1974], (Balakrishnan, 2002], (Савельев, 2003], (Barbour, 1987], (Barbour, 1992], (Barbour, 2002], (Chryssaphinou, 1989], (Chryssaphinou, 2001], (Erchardsson, 2005], (Fuchs, 1965] и др.].
Понятие серии получило ряд обобщений (см., например,
(Wolfowitz, 1944], (Chryssaphinou, 2001]]. Различные применения теории серий в статистике хорошо известны (см., например, (Glaz, 2001], (Balakrishnan, 2002] и др.].
В работе (Golic, 1996] была получена оценка сверху для вероятности Рт[Хп) плотного вложения последовательности Хп в
последовательность 5^ = {.У,-} независимых случайных величин, распределенных равномерно на множестве А2. В диссертации
получено обобщение результата работы (Golic, 1996] на случай конечного алфавита AN с произвольным числом букв и показано,
что эта верхняя оценка не улучшаема. Построена также неулучшаемая оценка снизу для вероятности Рт{Хп~), которая
достигается на последовательностях Хп, состоящих из п
одинаковых знаков.
Это свойство минимальности вероятности плотного вложения для последовательности из одинаковых знаков в контексте криптографических проблем, рассматривавшихся в работе (Golic, 1996], привлекает интерес к специальному изучению плотно заполненных отрезков в случайной последовательности. Отрезок последовательности х1,...,хк из
знаков алфавита AN мы называем плотно заполненным знаком
aeAN, если ає{хі,хі+1},і = 1,...,к-1. Распределение числа плотно
заполненных отрезков в случайной последовательности можно вывести из распределения числа плотно заполненных серий. Плотно заполненный (знаком а] отрезок назовем плотной а-серией, если он не содержится ни в каком плотно заполненном отрезке большей длины. Длиной плотной а-серии назовем длину
минимального отрезка, содержащего все знаки плотной а-серии. Число входящих в плотную а -серию знаков а будем называть ее весом.
Цель работы.
Основные цели диссертационной работы:
1. вывод неулучшаемых верхней и нижней оценок
вероятности плотного вложения Рт[Хп) заданной дискретной
последовательности в последовательность независимых случайных величин Ym, равномерно распределенных на
множестве AN = {0,...,N-1},N>2;
2. доказательство предельных теорем пуассоновского типа
для числа плотных серий большой длины и для числа плотных
серий большого веса в последовательности независимых
случайных величин со значениями в множестве AN, а также для
ряда связанных с ними случайных величин. Методы исследования.
В работе используются метод рекуррентных уравнений, метод Чена-Стейна, метод производящих функций, аппарат цепей Маркова.
Научная новизна.
Результаты диссертации являются новыми. Основными результатами диссертации являются:
Явные верхняя и нижняя оценки для вероятности плотного вложения с указанием классов вкладываемых последовательностей, на которых они достигаются.
Многомерная предельная теорема Пуассона для числа плотных серий большой длины с оценкой точности
пуассоновской аппроксимации.
3. Многомерная предельная теорема Пуассона для числа плотных серий большого веса.
Теоретическая и практическая значимость.
Работа носит теоретический характер. Задачи, рассмотренные в диссертации, обобщают ряд классических задач о сериях одинаковых знаков в последовательности независимых случайных величин.
Результаты диссертации могут представлять интерес для специалистов, занимающихся приложениями теоретико-вероятностных методов в экономических, технических и других областях. Разработанные в диссертации приемы реализации метода Чена-Стейна могут быть полезны при доказательстве предельных теорем в задачах дискретной теории вероятностей.
Апробация работы.
Результаты диссертации докладывались на 5-8 Всероссийских симпозиумах по прикладной и промышленной математике (2005-2007 гг.], на VII Международной Петрозаводской конференции «Вероятностные методы в дискретной математике» (2008 г.], в Московском государственном институте электроники и математики (2006-2009 гг.], на семинаре отдела дискретной математики Математического института им. В.А. Стеклова РАН (2009 г.].
Публикации.
Основные результаты диссертации опубликованы в 10 работах, работы [1] и [10] - в изданиях, входящих в утвержденный ВАК перечень ведущих рецензируемых научных
изданий, в которых должны быть опубликованы основные результаты диссертации на соискание ученой степени кандидата наук. Список работ приведен в конце автореферата.
Структура и объем диссертации.
Диссертация состоит из введения, двух глав, заключения и списка литературы. Общий объем диссертации 95 страниц. Нумерация разделов, формул и утверждений в каждой главе своя.
