Леса Гальтона-Ватсона и случайные подстановки

• Автор: Казимиров, Николай Игоревич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2003
• Место защиты: Петрозаводск
• Количество страниц: 127 с.

Оглавление
Введение

1 Обобщенная схема размещения

1.1 Основные определения и обозначения

1.2 Графы

1.3 Примеры применения обобщенной схемы размещения . . .

1.4 Описание класса рассматриваемых схем

размещения

1.5 Случайные подстановки и случайные

рекурсивные леса

2 Некоторые свойства обобщенной схемы размещения

2.1 Обозначения и сводка результатов
2.2 Случай N -» со, п = const
2.3 Случай n/N -» О, N, п -* оо
2.4 Случай п х N, N, п -* оо
2.5 Случай n/N —» оо при некоторых
ограничениях
2.6 Некоторые условия отсутствия гигантской компоненты . . .
3 Леса Гальтона—Ватсона
3.1 Определение леса Гальтона—Ватсона
3.2 Сводка результатов
3.3 Доказательство теорем об объемах деревьев
3.4 Доказательство теорем о и г

4 Случайные подстановки с известным числом циклов
4.1 Сводка результатов
4.2 Предельные распределения длин циклов при п = 0(ЛГ)
4.3 Предельные распределения длин циклов в зоне 4..
4.4 Предельное распределение длин циклов в зоне 5..
4.5 Предельное распределение длин циклов в зоне 6..
4.6 Условия возникновения гигантского цикла
Литература

Введение
В настоящее время широкое распространение в комбинаторном анализе получил теоретико-вероятностный подход. Хорошо развитые в теории вероятностей методы асимптотического анализа успешно используются при решении сложных комбинаторных задач. Впервые такой подход был использован В. Л. Гончаровым в статьях [6,7], применившим его к изучению случайных подстановок и (0, ^-последовательностей.
Применение вероятностных методов в решении перечислительных задач комбинаторики (см., например, [26,30,56,83]) связано с заданием вероятностей на множестве изучаемых комбинаторных объектов таким образом, чтобы эти вероятности определяли долю объектов с интересующими нас свойствами. Тогда, используя теоретико-вероятностный аналитический аппарат, можно получить точные или приближенные формулы для числа объектов, обладающих изучаемыми свойствами.
Одним из важнейших направлений исследований является изучение предельных свойств комбинаторных объектов, проявляющихся при неограниченном возрастании числа элементов, образующих такие объекты. Поэтому при анализе случайных структур использовались такие известные методы, как пуассоновская и гауссовская аппроксимации, производящие функции и их анализ методом перевала. В последние три десятилетия широкое распространение получил подход, основанный на применении обобщенной схемы размещения, введенной В. Ф. Колчи-ным [26,30,34]. Такой подход позволяет свести целый ряд комбинаторных задач к задачам о нахождении предельных распределений серий сумм независимых случайных величин.
и (NPr)3 = о{п). Тогда для любого целого фиксированного hup — NPr+h + 0(^NPT+h) справедливы соотношения:
(p-NPr+hyy/NP^:
р{щн-р) < г+h) ~ -|= J е-(>/2.

Эти теоремы будут использованы в главах 3 и 4 для нахождения предельных распределений объемов деревьев в лесе Гальтона—Ватсона (см. теоремы 3.2.3, 3.2.5 и 3.2.1-3.2.6) и длин циклов случайной подстановки (см. теоремы 4.1.1-4.1.5).
Теорема 2.1.7. Пусть 6* ж k~5, 1 < 5 < 2. Пусть n/N —> оо так, что N( 1 - x)s~l -4 ос, где х выбрано как корень уравнения Na = п. Кроме того, пусть параметр г удовлетворяет соотношению NPr -4 у, где у — положительная постоянная. Тогда при любом фиксированном р
piV(N-p) < г} -> e~7X,jr-i=o *•
Данная теорема будет использована при доказательстве теоремы 3.2.7 о лесах Гальтона—Ватсона. Более общих результатов в четвертой зоне пока получить не удалось.
Применяя теоремы 2.1.3, 2.1.5 и 2.1.7 для р = 0,1, мы ответим на вопрос о существовании гигантской компоненты в параграфе 2.6, где будут доказаны следующие утверждения.
Теорема 2.1.8. Пусть параметр х определяется равенством Na = п, N, п -» оо так, что п = O(N) и Nx’ -4 оо; кроме того, последовательность Ъ удовлетворяет условию (2.1.3). Тогда в канонической обобщенной схеме размещения гигантской компоненты нет.
Теорема 2.1.9. Пусть bk х k~s, х определяется уравнением Na = п, N —> оо так, что Nxs -4 оо и N( 1 — ж)*-1 -4 оо. Тогда в канонической обобщенной схеме размещения гигантской компоненты нет.
Применение этих теорем найдет место в параграфе 4.6.
Заметим, что случай а < оо также имеет известные примеры. Так, в книге [34] рассмотрены случайные леса из некорневых деревьев. Там же