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

• Автор: Черепанова, Елена Владимировна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2004
• Место защиты: Петрозаводск
• Количество страниц: 137 с.

1 Обобщенная схема размещения
1.1 Определение и основные свойства обобщенной схемы размещения
1.2 Примеры комбинаторных задач, сводимых к обобщенной схеме размещения
1.3 Леса Гальтона — Ватсона
2 Предельные распределения числа циклов заданной длины в случайной подстановке с известным числом циклов
2.1 Формулировки результатов
2.2 Предельные распределения сумм вспомогательных
случайных величин при Ж/Inn -> оо
2.3 Предельные распределения сумм вспомогательных
случайных величин при N/nn = 0(1)
2.4 Доказательства теорем 2.1.5-2.1
3 Предельное поведение компонент малого объема в случайных подстановках и лесах
3.1 Постановка задач и формулировки результатов
3.2 Вспомогательные утверждения
3.3 Доказательства теорем 3.1.1-3.1
3.4 Доказательства теорем 3.1.5-3.1
3.5 Доказательства теорем 3.1.9, 3.1
4 Предельные распределения числа пар в обобщенной схеме размещения
4.1 Формулировки результатов
4.2 Предельные распределения (Cn,Vn)
4.3 Доказательства теорем 4.1.1-4.1.3
5 Некоторые статистические приложения
5.1 Асимптотика статистики типа х2 в некоторых комбинаторных задачах
5.2 Доказательства теорем 5.1.1-5.1
5.3 Критерий пустых ящиков для случайных лесов
5.4 Доказательства теорем 5.3.1, 5.3
Литература
В настоящее время в комбинаторном анализе широко применяются хорошо развитые в теории вероятностей методы. Впервые вероятностный подход при изучении комбинаторных объектов был использован В.Л. Гончаровым в статьях [6, 7]. Среди многочисленных работ, опубликованных с тех пор по этой тематике, отметим только несколько важнейших (на наш взгляд) книг [15,21,24,25,29,39-41,57,59,64,67]. Возможность применения вероятностных методов при решении комбинаторных задач обеспечивается заданием распределения вероятностей на множестве изучаемых комбинаторных объектов, поскольку в этом случае их числовые характеристики можно рассматривать как случайные величины. При этом, задание равномерного распределения позволяет исключить из рассмотрения ту небольшую часть исследуемых объектов, которые обладают нетипичными свойствами. В современных работах по дискретной математике значительное внимание уделяется изучению случайных комбинаторных структур (см., например, [24]). Примерами таких структур являются случайные графы, случайные подстановки, урновые схемы.
К настоящему времени множество работ посвящено изучению случайных графов [21,22,24,29,40,43-45,57,61-64,68,70]. Графы являются удобным средством моделирования разнообразных объектов. Результаты, полученные для случайных деревьев, лесов, графов подстановок, находят применение в анализе вычислительных алгоритмов [64], статистических методах [8,26], мо-
Ь/п ^ е для всех г

|#( Доказательство. По лемме 4.2.2 [24], существуют постоянные С, е > 0 такие, что при |£/п|
^(г/п^С^П. (2.3.4)
Поскольку Ырг = 0(1) и а = N — ЛГрг + о (./Vрг), при |£/п|
(2.3.5)
Так как для |
рйг/п
1р{Ь/п)
учитывая (2.1.1) и равенство врг = 0(1), находим, что
1 +
< Отсюда и из (2.3.3), (2.3.5) следует утверждение леммы.
В лемме 4.2.3 [24] доказано, что если п -> оо, 0 < е ^ |£| ^ тг, где е — постоянная, то найдется постоянная С > О такая, что при достаточно больших п
|(р (£)| ^ С/1пп.
(2.3.6)
Отсюда и из (2.1.1), (2.2.4) нетрудно получить следующее утверждение.
Лем(ма 2.3.3. Если п -> оо и 0 < е ^ |£| ^ 7г, где е — постоянная, то существует положительная постоянная С такая, что при достаточно больших п
Рг (*)| ^ С/1пга.