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

• Автор: Меженная, Наталья Михайловна
• Шифр специальности: 01.01.05
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Москва
• Количество страниц: 95 с.

Введение
0 ВВЕДЕНИЕ

1 ОЦЕНКИ ДЛЯ ВЕРОЯТНОСТИ ПЛОТНОГО ВЛОЖЕНИЯ ОДНОЙ ДИСКРЕТНОЙ

ПОСЛЕДОВАТЕЛЬНОСТИ В ДРУГУЮ

1.1 Постановка задачи и формулировки результатов

1.2 Точные значения вероятности плотного вложения

1.3 Доказательство теорем 1.1 и

1.4 Доказательство теорем 1.2 и

1.5 Доказательства вспомогательных утверждений

1.6 Проверка гипотезы о плотном вложении

2 ПРЕДЕЛЬНЫЕ ТЕОРЕМЫ ДЛЯ ЧИСЛА ПЛОТНЫХ СЕРИЙ В СЛУЧАЙНОЙ

ПОСЛЕДОВАТЕЛЬНОСТИ
2.1 Предварительные замечания
2.2 О методе доказательства многомерных предельных теорем пуассоновского типа
2.3 Вероятность появления плотно заполненной серии заданной длины
2.4 Оценки расстояния по вариации
2.5 Оценки расстояния по вариации - 2 I
2.6 Предельные теоремы для числа длинных плотных серий
2.7 Асимптотическое поведение распределения наибольших длин плотных серий
2.8 Предельная теорема для числа плотных серий большого веса
2.9 Формулы для вычисления точных распределений числа плотных серий
2.10 Оценивание точности пуассоновской аппроксимации
3 ЗАКЛЮЧЕНИЕ
4 СПИСОК ЛИТЕРАТУРЫ
Введение [
О Введение
Исследование свойств дискретных случайных последовательностей является одной из центральных задач теории вероятностей. Такие задачи тесно связаны с приложениями. Полученные результаты применяются для решения ряда экономических, технических, биологических, криптографических и других задач.
Одной из таких задач является изучение статистических свойств специальных комбинаций в дискретных случайных последовательностях. В диссертации в качестве специальных комбинаций рассматриваются плотно вложенные последовательности. Понятие плотного вложения было введено в
математическую литературу в работе (Golic, 1996). Пусть Xn = {xf}" и
Ym = {J/f.}I”i - последовательности знаков алфавита AN — 1}. Согласно
(Golic, 1996), последовательность Хп плотно вкладывается в начало последовательности Ym, если П <т и найдутся такие натуральные числа
l = h что xk=yk,k-l
Понятие плотного вложения возникает при изучении свойств последовательностей, генерируемых конечными автоматами из нескольких параллельно функционирующих блоков, выходные последовательности которых соединяются в одну общую последовательность без нарушения порядка следования букв. Например, если генератор случайных' чисел состоит из двух блоков, в последовательность, вырабатываемую первы|я блоком, добавляются знаки, выработанные вторым блоком, причем не более одного знака подряд, то выходная последовательность первого блока будет плотно вложена в выходную последовательность генератора. Роль этого свойства при изучении генераторов случайных чисел описана в работах (Zivkovic, 1991), (Golic, 1991), (Golic, 1996].
Введение [
Качество сгенерированной случайной последовательности определяется близостью ее свойств к свойствам последовательности независимых случайных величин, равномерно распределенных на множестве знаков выходного алфавита. Для описанного выше класса генераторов одним из способов проверки его свойств является использование статистик, связанных с плотно вложенными последовательностями.
Диссертация посвящена выводу оценок и предельных соотношений для вероятности плотного вложения заданной последовательности и для распределений ряда случайных величин, связанных с задачей о плотном вложении.
Первая интересующая нас задача состоит в определении вероятности плотного вложения Ет(Хп) заданной последовательности Хп в начало последовательности Ym, образованной независимыми случайными величинами, равномерно распределенными на множестве AN. В случае двоичных последовательностей (iV = 2) верхняя оценка вероятности РтХп} была получена в работе (Golic, 1996). В первой главе диссертации получено обобщение результата (Golic, 1996) на случай конечного алфавита Aw с произвольным числом букв Рт[Хп]. Также построена оценка снизу для вероятности Рт[Хп) и указаны классы последовательностей, на которых эти оценки достигаются. Приведены вытекающие из этих оценок предельные соотношения для вероятности плотного вложения, когда растут параметры п и т. В частности, получено предельное равенство для логарифма вероятности плотного вложения Рт(Хп] в схеме серий, когда размер алфавита также растет.
Нижняя оценка вероятности Рт(Хп) достигается на последовательностях Хп, состоящих из п одинаковых знаков. Значит, при проверке гипотезы о том, что заданная последовательность была плотно вложена в наблюдаемую случайную последовательность первое внимание следует уделять участкам выходной последовательности, в которые плотно вкладывались цепочки или серии одинаковых знаков.
Серии в достаточной для многих приложений, степени отражают
Оценки для вероятности плотного вложения одной дискретной
последовательности в другую
I н„}=/>{*, =Л}(1 - Р{Г. > 1(1.-1)1 н„}'
4(1-р{Г”>1с"-Ц|Ц
В силу леммы и формулы (1.40)
1 [0,75Ы-1)1
Р{Н0пН1п} = ± £ СаО.5“. (1.48)

Из формул (1.47) и (1.48) следует, что предложенный критерий является состоятельным.
Далее будем считать, что N = 2.
В таблице 1.6 приведены значения оценки сверху для вероятности ошибки первого рода по формуле (1.47), а также значения экспериментальной оценки по 10000 независимых испытаний. С ростом длины вкладываемой последовательности оценка сверху по формуле (1.47) и экспериментальная оценка вероятности ошибки первого рода убывают достаточно быстро, но из таблицы 1.6 видно, что оценка сверху по формуле (1.47) в среднем в 2,5 раза превышает значения экспериментальной вероятности ошибки первого рода.