Леса Гальтона-Ватсона и случайные подстановки Казимиров Николай Игоревич

Содержание к диссертации

Введение

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

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

1.2 Графы 16

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

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

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

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

2.1 Обозначения и сводка результатов 30

2.2 Случай N -> оо, п = const 38

2.3 Случай n/N -> О, N, п -* оо 50

2.4 Случай п х N, N, п -> оо 57

2.5 Случай n/N -» оо при некоторых ограничениях 65

2.6 Некоторые условия отсутствия гигантской компоненты . 73

3 Леса Гальтона—Ватсона 77

3.1 Определение леса Гальтона—Ватсона 77

3.2 Сводка результатов 87

3.3 Доказательство теорем об объемах деревьев 92

3.4 Доказательство теорем о/^ит 96

4 Случайные подстановки с известным числом циклов 100

4.1 Сводка результатов 100

4.2 Предельные распределения длин циклов при п = 0(Д7) . 104

4.3 Предельные распределения длин циклов в зоне 4 106

4.4 Предельное распределение длин циклов в зоне 5 111

4.5 Предельное распределение длин циклов в зоне 6 114

4.6 Условия возникновения гигантского цикла 119

Литература

• Примеры применения обобщенной схемы размещения
• Случай n/N -» оо при некоторых ограничениях
• Доказательство теорем об объемах деревьев
• Предельные распределения длин циклов в зоне 4

Введение к работе

^

В настоящее время широкое распространение в комбинаторном анализе получил теоретико-вероятностный подход. Хорошо развитые в теории вероятностей методы асимптотического анализа успешно используются при решении сложных комбинаторных задач. Впервые такой подход был использован В. Л. Гончаровым в статьях [6,7], применившим его к изучению случайных подстановок и (0, ^-последовательностей.

Применение вероятностных методов в решении перечислительных задач комбинаторики (см., например, [26,30,56,83]) связано с заданием вероятностей на множестве изучаемых комбинаторных объектов таким образом, чтобы эти вероятности определяли долю объектов с интересующими нас свойствами. Тогда, используя теоретико-вероятностный аналитический аппарат, можно получить точные или приближенные формулы для числа объектов, обладающих изучаемыми свойствами.

Одним из важнейших направлений исследований является изучение предельных свойств комбинаторных объектов, проявляющихся при неограниченном возрастании числа элементов, образующих такие объекты. Поэтому при анализе случайных структур использовались такие известные методы, как пуассоновская и гауссовская аппроксимации, производящие функции и их анализ методом перевала. В последние три десятилетия широкое распространение получил подход, основанный на применении обобщенной схемы размещения, введенной В. Ф. Колчи-ным [26,30,34]. Такой подход позволяет свести целый ряд комбинаторных задач к задачам о нахождении предельных распределений серий сумм независимых случайных величин.

Значительное внимание в работах по дискретной математике в настоящее время уделяется изучению случайных графов [30,31,34,50,56,58-60, 69,74-77,83]. С помощью обобщенной схемы размещения в этой области математики удается решать множество сложных и полезных в других областях науки задач. Так, случайные деревья, леса и подстановки находят применение в анализе вычислительных алгоритмов [77], статистических методах [11,38], моделировании транспортных [1,76] и информационных систем [76,86], генетике [81], криптографии [54,79], а также при решении собственно математических задач, например, в теории случайных уравнений [32,34] и проблеме эволюции случайных графов [3,31,60,69,82].

Объектами изучения в диссертации являются: собственно обобщенная схема размещения, леса Гальтона—Ватсона и случайные подстановки.

Так как к обобщенной схеме размещения сводится большое число задач комбинаторики, она представляет интерес как самостоятельный объект исследования. Свое название эта схема получила в связи с тем, что она является обобщением задачи о случайном равновероятном размещении п частиц в N ячеек, за которой утвердилось название классическая схема размещения. Терминология классической схемы размещения оказалась удобной для описания многих задач, в которых появляется полиномиальное распределение случайного вектора из N компонент. Классическая схема позволяет перейти от полиномиального распределения к распределению сумм независимых слагаемых с распределением Пуассона и усеченным распределением Пуассона. Введение обобщенной схемы размещения частиц не только расширяет область использования удобного языка для описания комбинаторных структур, но также дает возможность применять те методы, которые были развиты при анализе классической схемы [26]. Отметим, что все результаты, связанные с обобщенной схемой размещения, доказывались для каждого класса комбинаторных объектов отдельно. Однако некоторое сходство предельных теорем, получаемых в различных задачах с помощью обобщенной схемы размещения, позволяет надеяться на получение достаточно общих

предельных теорем для обобщенной схемы размещения. В диссертации сделана попытка реализовать этот замысел, и доказан ряд достаточно общих теорем, не охватывающих однако тех зон изменения параметров Nun, интерес к которым в последнее время особенно велик в связи с понятием гигантской компоненты [35].

Леса Гальтона—Ватсона представляют собой случайные леса, соответствующие траекториям ветвящегося процесса Гальтона—Ватсона, откуда и происходит это название. Термин лес Гальтона—Ватсона впервые, по-видимому, встречается в работе [84]. Применению методов теории ветвящихся процессов для изучения случайных лесов предшествовало рассмотрение случайных деревьев с занумерованными вершинами и соответствующих им процессов Гальтона—Ватсона с пуассоновским распределением числа прямых потомков каждой частицы. Впервые на эту возможность указано в статье В. Е. Степанова [59], а систематически такое исследование проведено в работах В. Ф. Колчина [27-29]. В [4,43,44] была установлена связь между начинающимися с одной частицы процессами Гальтона—Ватсона с геометрическим распределением числа прямых потомков каждой частицы и посаженными деревьями [53] (т. е. плоскими деревьями с висячими корнями и непомеченными вершинами). Связь между лесами, состоящими из N посаженных деревьев, и начинающимися с N частиц ветвящимися процессами Гальтона-Ватсона с геометрическим распределением числа прямых потомков одной частицы, впервые рассматривается в работах [10,47]. В [45,46,48-51] рассматривались случайные леса, для которых предполагалась связь с условными ветвящимися процессами Гальтона—Ватсона, распределение вероятностей на множестве лесов при этом не было обязательно равномерным. Однако ограничения на вероятностную меру не позволяли использовать полученные результаты для многих классов случайных лесов. В работах [67,83] эти ограничения были сняты, однако осталось одно существенное ограничение на распределение числа прямых потомков каждой частицы в процессах Гальтона—Ватсона, соответствующих рассматриваемым лесам: огра-

ниченность третьего момента этого распределения. В статье [16] удалось снять это ограничение для распределений максимального объема дерева, числа деревьев заданного объема и высоты леса Гальтона—Ватсона, показав, что оно может быть заменено более слабым, а именно, ограниченностью второго момента распределения числа прямых потомков каждой частицы. В статье [68] удалось обобщить эти результаты для распределений объемов наибольших деревьев. Кроме того, в диссертации с помощью общих результатов об обобщенной схеме размещения удалось получить также некоторые дополнительные результаты о предельном поведении объемов деревьев леса Гальтона—Ватсона.

Случайные подстановки занимают особое место в ряду комбинаторных задач, связанных с обобщенной схемой размещения. Как показано в статье [52], случайные подстановки с известным числом циклов соответствуют той же обобщенной схеме размещения, что и рекурсивные леса [87]. Как показано в [78], такие леса не могут быть изучены с помощью ветвящегося процесса Гальтона—Ватсона. Наиболее подробно результаты исследований случайных подстановок и история этих исследований изложены в [30,33,34]. Там же приведены теоремы о предельном распределении числа циклов случайной подстановки степени п при п-^оос ограничениями на длины циклов и без ограничений. В статье [52] получено полное описание предельного поведения максимальной длины цикла случайной подстановки с известным числом циклов при п -* оо, а в работе [61] получены некоторые результаты о распределении числа циклов заданной длины для таких подстановок. В диссертации получено полное описание предельного поведения р-то по величине цикла при фиксированном рив некоторых зонах изменения параметров — для р —^ оо.

В последнее время в работах по случайным графам повышенный интерес проявляется к возникновению гигантской компоненты, т. е. такой компоненты, которая с вероятностью, стремящейся к единице, имеет порядок п, где п — число вершин графа, а следующая по величине компонента имеет порядок о[п) [35]. В работе [66] были найдены условия

возникновения гигантского дерева в лесе Гальтона—Ватсона, а из результатов статьи [52] следует, что гигантский цикл в случайной подстановке степени п с N циклами при п -> оо возникает при условии N/ In п -> 0 и не возникает при условии N/\nn -» оо. В диссертации доказано, что при N/ In п -» а > 0, где а — константа, гигантский цикл также не возникает.

Целью диссертации является получение новых результатов о предельном поведении важнейших характеристик лесов Гальтона—Ватсона и случайных подстановок с известным числом циклов. В частности, предполагалось, во-первых, снятие ограничения конечности третьего момента распределения числа прямых потомков каждой частицы в ветвящемся процессе, генерирующем лес Гальтона—Ватсона, для изучения всех известных характеристик леса, во-вторых, получение полного спектра теорем, описывающих предельное поведение наибольших длин циклов случайной подстановки с известным числом циклов, в-третьих, выявление условий возникновения гигантского цикла в случайной подстановке. Для достижения этой цели предполагалось получение новых результатов об обобщенной схеме размещения и использование этих результатов для получения предельных распределений числовых характеристик различных комбинаторных объектов.

Основными методами исследования в диссертации являются обобщенная схема размещения, теория ветвящихся процессов Гальтона—Ватсона и методы получения предельных теорем для сумм независимых решетчатых случайных величин, включая локальную сходимость в схеме серий. В настоящее время известные достаточные условия такой сходимости не покрывают все зоны изменения параметров многих комбинаторных объектов (по этому поводу см. параграф 1.4 книги [30]). И хотя в последних работах (см., например, [39]) имеются определенные достижения в этом направлении, эта проблема по-прежнему остается актуальной, а проверка известных условий часто оказывается весьма трудной задачей. В диссертации удалось для некоторых случаев применить результаты статьи [39] и получить несколько общих теорем для обобщенной

схемы размещения. Эти теоремы были использованы для достижения целей диссертации. Однако, возникающие здесь технические трудности, к сожалению, не позволили получить весь спектр предельных теорем для обобщенной схемы размещения. Кроме того, удалось получить несколько дополнительных результатов, а именно: а) предельные распределения всех компонент леса Гальтона—Ватсона с N корнями и п некорневыми вершинами при N -» оо и п = const, б) предельные распределения р-ой по величине компоненты леса Гальтона—Ватсона с N корнями и п некорневыми вершинами и случайной подстановки степени п с N циклами при N,n,p -> оо так, что п = O(N), с некоторыми ограничениями на скорость роста р.

Диссертация состоит из четырех глав. Первая глава носит вводный характер. В этой главе даются все основные определения и обозначения (параграфы 1.1 и 1.2), приводится ряд примеров применения обобщенной схемы размещения (параграф 1.3). В четвертом параграфе этой главы приводится описание изучаемых в дальнейшем в общем виде схем размещения. Такие схемы (названные для краткости каноническими) охватывают широкий спектр задач, сводимых к обобщенной схеме размещения. В этом же параграфе показано, что не все схемы размещения могут быть сведены к такому виду, но приведенные примеры являются скорее исключением, подтверждающим правило, т. к. большинство известных в литературе примеров обобщенной схемы размещения все же сводятся к такому виду, который рассмотрен в диссертации. В параграфе 1.5 дается описание рассматриваемых случайных подстановок степени п с N циклами и приводится ряд известных ранее результатов о цикле максимальной длины.

Вторая глава целиком посвящена исследованию обобщенной схемы размещения. Здесь для схем, определенных в параграфе 1.4, с N компонентами, сумма которых равна п, найдены предельные распределения всех компонент в случае п = const, а при N, п —> оо так, что п = O(N), найдены предельные распределения р-х по величине компонент, причем как

для фиксированного р, так и для р —> оо так, что р³ = о(тг). Кроме того, при усилении ограничений на рассматриваемые схемы размещения получены предельные распределения для р-х компонент при фиксированном р и n/N -» оо, причем на скорость роста дроби n/N также накладываются определенные ограничения. Эти результаты используются в последующих главах для получения теорем о лесах Гальтона—Ватсона и случайных подстановках. В первом параграфе главы 2 указывается также граница применимости полученных теорем: они не могут быть использованы, например, для получения предельных распределений объемов деревьев случайного леса из некорневых деревьев. В конце главы 2 (параграф 2.6) приводятся теоремы, дающие достаточные условия невозникновения гигантской компоненты в обобщенной схеме размещения. Эти теоремы получены из предыдущих результатов главы 2 и не охватывают всех зон изменения параметров.

В третьей главе рассматриваются леса Гальтона—Ватсона. Сначала (параграф 3.1) приводится определение леса Гальтона—Ватсона по схеме, предложенной В. А. Ватутиным [4]. Затем (параграф 3.2) перечислены все результаты о лесах Гальтона—Ватсона, для которых в дальнейшем (параграфы 3.3 и 3.4) будет установлена избыточность условия конечности третьего момента распределения числа прямых потомков каждой частицы в соответствующем процессе Гальтона—Ватсона. Здесь же (параграф 3.2) перечислены теоремы, доказанные на основе результатов главы 2 и дающие предельные распределения объемов деревьев леса Гальтона— Ватсона в тех зонах изменения параметров N, п,р, которые ранее не были изучены.

Четвертая глава посвящена случайным подстановкам с известным числом циклов. В параграфе 4.1 приводится список всех полученных в диссертации результатов об асимптотике наибольших длин циклов случайной подстановки, а в последующих параграфах 4.2-4.5 приводится их доказательство. В параграфе 4.6 доказывается, что только в последней зоне изменения параметров (N/ In п -» 0) возникает гигантский цикл.

Основными результатами диссертации являются:

1. Предельные распределения при N -> оо: а) всех компонент обобщенной схемы размещения п частиц по N ячейкам при п = const; б) р-ых по величине компонент (р = О соответствует максимальной компоненте) при N, п -> оо, р³ = о(п), п = О (А/), где р принимает значения из множества {0,1,..., N — 1}; в) р-ых по величине компонент при р = const и n/N -> оо, с ограничением на скорость роста n/N.

2. Доказательство того, что в известных ранее теоремах о предельном поведении наибольших объемов деревьев леса Гальтона—Ватсона, числа деревьев заданного объема и высоты леса, условие конечности третьего момента распределения числа прямых потомков каждой частицы в процессе, генерирующем лес Гальтона—Ватсона, может быть заменено на условие конечности второго момента.

3. Предельные распределения объемов всех деревьев леса Гальтона— Ватсона при постоянном числе п некорневых вершин.

4. Предельные распределения р-ых по величине объемов деревьев леса Гальтона—Ватсона при N,n,p -> оо так, что р³ = о(п), п = О (А/).

5. Полное описание предельного поведения длин р-ых по величине длин циклов случайной подстановки степени п с N циклами при п -> оо, включая случай р -» оо при ограничениях п — N = O(N),

р³ = о{п - N).

6. Доказательство того, что в случайной подстановке степени п с N
циклами гигантский цикл возникает только при N, п -ь оо так, что
N/\nn->0.

Основные результаты диссертации опубликованы автором в пятнадцати работах [13-24,71-73], из них 3 статьи в журнале "Дискретная математика" [16,18,22], 1 статья в трудах международной конференции [72], 5 статей в сборниках трудов [13, 14, 19,23,24], 6 тезисов докладов на международных, всероссийских и региональных конференци-

ях [15, 17,20,21,71,73]. Результаты также докладывались на IV Санкт-Петербургской ассамблее молодых ученых и специалистов (1999 г.), V Петрозаводской международной конференции "Вероятностные методы в дискретной математике" (2000 г.), Kalashnikov Memorial Seminar (Петрозаводск, 2002 г.), научной конференции "Карелия и РФФИ" (Петрозаводск, 2002 г.), IV Всероссийском симпозиуме по прикладной и промышленной математике (Петрозаводск, 2003 г.), международной конференции "Колмогоров и современная математика" (Москва, 2003 г.). В 2000-2002 гг. автор являлся одним из исполнителей гранта РФФИ 00-01-00233 "Вероятности на деревьях и лесах". В рамках этого проекта создан интернет-ресурс "Случайные леса" [85].

Результаты диссертации были получены в ходе проработки темы "Вероятностные и алгебраические методы исследования дискретных объектов", входившей в 1997-2000 гг. в план научно-исследовательских работ Института прикладных математических исследований Карельского научного центра РАН (№ гос. регистрации 01.9.60 0 12636) и выполнявшейся в рамках проекта "Интеграция высшего образования и фундаментальной науки Республики Карелия" ФЦП "Интеграция" (per. №634). В 2001-2003 гг. исследования проводились в рамках темы плана научно-исследовательских работ этого же института "Вероятности на деревьях и лесах", № гос. регистрации 01.2.00 1 03997. В 2003 г. работа проводилась также по государственному контракту "Исследование случайных комбинаторных структур" по программе фундаментальных исследований РАН "Современные проблемы теоретической математики" (госконтракт № 100002-251/ОМН-01/018-026/090703-1029).

В диссертации принята двойная нумерация параграфов и тройная нумерация теорем, лемм, формул и замечаний. Это значит, что параграф 3.4 является четвертым по порядку в главе 3, а теорема 2.1.2 является второй по порядку в параграфе 2.1.

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

Ниже приведен ряд примеров обобщенной схемы размещения. Примеры 1-3 и 5 взяты у В. Ф. Колчина [26,30,34], пример 4 был подробно изучен в работах Ю. Л. Павлова [25,40-42], а пример 6 — в статье [52]. Все они демонстрируют применение обобщенной схемы размещения в перечислительных задачах комбинаторики. Первый пример является классической задачей размещения разных частиц, второй пример — это задача размещения одинаковых частиц, третий показывает, что в обобщенной схеме размещения св. &, і = 1,N, не обязательно одинаково распределены, а в 4-6 примерах описываются объекты, изучению которых посвящена основная часть диссертации. 1. Рассмотрим равновероятное размещение п занумерованных частиц по N занумерованным ячейкам. Пусть 7Гі,...,7гп — независимые св., равные номерам ячеек, в которые попадают частицы с номерами, соответственно, 1,...,п. При равновероятном размещении частиц имеем Р{тГ = J} = 1/-W ПРИ г = V"r 3 = !»№ Таким образом, щ = {г : щ = к}\. где A/" — это число всех возможных размещений. Такое совместное распределение св. щ,...,г]ы называется полиномиальным, а за соответствующей схемой размещения частиц закрепилось название классической [34]. Пусть независимые св. &,...,# имеют распределение Пуассона с произвольным параметром х 0: Тогда равенство (1.1.1) выполнено, если (771,...,77 ) имеет полиномиальное распределение. Следовательно, классическая схема размещения частиц является частным случаем обобщенной схемы размещения. Классическая схема была подробно изучена в книге [26]. 2. Рассмотрим все различные разбиения целого положительного числа п на N упорядоченных слагаемых, не меньших числа г 0. Заметим, что число п можно представить как множество п одинаковых частиц и, таким образом, задачу о разбиении числа п на N упорядоченных слагаемых свести к задаче о размещении п одинаковых частиц по N занумерованным ячейкам. Число таких размещений равно ("" l "1) [62]. Зададим равномерное распределение на множестве всех разбиений числа п на N упорядоченных слагаемых, не меньших г, приписав каждому такому разбиению вероятность (п 1)

Тогда п можно записать в виде n = rji-\ \)N, где св. %,...,т)м имеют совместное распределение, определяемое равенством fi, ч 6v образуют обобщенную схему размещения. 3. Пусть в урне, содержащей т,- шаров г-го цвета, і = 1, А/, с помощью случайной выборки без возвращения извлекается п шаров. Обозначим щ число извлеченных шаров г-го цвета. Тогда для неотрицательных целых Лі,...,кні сумма которых равна п, имеем где m = ті Ч h TUN. Равенство (1.3.1) легко проверить, полагая равно вероятными все выборки без возвращения п шаров из тп имеющихся в урне. Действительно, число таких выборок равно \\, а число выборок, содержащих ровно по ki шаров г-го цвета, равно (Л и"). Однако эту же формулу можно получить способом, аналогичным примеру 1. Пусть 7Г,- — св., равная номеру цвета j-oro вынимаемого из урны шара, j = 1, п. Если перед выниманием j-ro шара в урне имеется tІ шаров цвета і, г = 1, А/, то P{XJ = і} = U/(t\. -і f-1 ). Понятно, что каждая св. 7Г; зависит от предыдущих 7Гі, — ,7Гу_і. Рассмотрим такую выборку, при которой сначала вынули ki шаров 1-го цвета, затем / шаров 2-го цвета, и т.д., а в конце вынули &дг шаров JV-го цвета. Тогда Отсюда легко видеть, что при смене порядка цветов вытаскиваемых ша ров мы получим такое же значение вероятности, т. е. вероятность каж дой конкретной выборки п шаров, из которых к{ шаров имеют цвет г, к\-\ Ь kN = п, не зависит от порядка вытаскивания этих шаров, поэто му N. Тогда, как легко видеть, для св. rji,...,rjN и 6,...,лг выполнено равенство (1.1.1), т.е. они образуют обобщенную схему размещения. m 4. Рассмотрим множество FN)Tl всех лесов, состоящих из N корневых деревьев и п некорневых вершин, в которых корни занумерованы числами 1,..., N, а некорневые вершины занумерованы числами 1,..., п. Задав на этом множестве равномерное распределение, мы получим случайный лес. Обозначим через щ число некорневых вершин дерева, корень кото рого имеет номер г, г = 1,N. По формуле Кэли имеем F1 n = (тг + 1)п-1. Поэтому число лесов в FN)n, имеющих ki некорневых вершин в дереве с где Лі Н Ь &лг = п и n\/(ki\... к ї) — число способов разместить п некор невых вершин в N деревьях ск\,...,кы некорневыми вершинами, номера корней которых равны 1,..., N соответственно. В [55] доказано, что \FN n\ = N(N + п)п 1, поэтому рассматриваемый случайный лес равен любому лесу из FNjV, с вероятностью N l(N + n)1_n. Отсюда и из (1.3.3) получаем, что равенство (1.1.1), т.е. они образуют обобщенную схему размещения. Случайный лес, построенный в этом примере, является частным случаем леса Гальтона—Ватсона, который будет рассмотрен в параграфе 3.1. 5. Рассмотрим множество Sn подстановок степени п, т. е. всех взаим но однозначных отображений множества из п элементов в себя. Каждой подстановке о є Sn соответствует единственный псевдограф с вершина ми 1,...,п и ребрами (к,а(к)), к = 1,п. Компонентой связности такого графа является ориентированный простой цикл, либо петля. Рассмотрим множество подстановок степени п, содержащих ровно N циклов, зану мерованных произвольным образом.

Зададим на множестве всех этих подстановок равномерное распределение и обозначим 771,...,77 длины циклов с соответствующими номерами. Известно (см., например, [34]), что для изучения длин циклов случайной подстановки можно использовать обобщенную схему размещения, в которой св. и... ,лг имеют распределение логарифмического ряда: В параграфе 1.5 мы более подробно рассмотрим этот пример, а в главе 4 будут приведены доказательства полученных автором результатов об асимптотическом поведении членов вариационного ряда компонент случайной подстановки с известным числом циклов. 6. Ориентированное дерево объема п, вершинами которого являются числа 1,...,п, причем все дуги направлены от меньшего числа к больше му, называется рекурсивным [78]. Лес, построенный аналогичным спосо бом, также называется рекурсивным [52]. Задавая равномерное распре деление на множестве всех рекурсивных лесов объема п с N деревьями, мы получаем случайный рекурсивный лес. Обозначим TJI,...,T]N объемы деревьев в случайном рекурсивном лесе объема п с N деревьями, занумеровав их в произвольном порядке. Из результатов статьи [52] видно, что 77i,..., T]N и fi,..., лгі имеющие распределение логарифмического ряда (1.3.5), образуют обобщенную схему размещения. Кроме того, примеры 5 и 6 эквивалентны с точки зрения обобщенной схемы размещения, поэтому результаты главы 4, полученные для случайной подстановки, справедливы и для случайного рекурсивного леса.

Случай n/N -» оо при некоторых ограничениях

Перейдем к рассмотрению ситуации, в которой n/N -» оо. Напомним, что в параграфе 2.1 было принято ограничение а = оо (см. (2.1.2)), где a = lima, х определяется равенством (2.1.1). В том же параграфе было показано, что в таком случае соотношения n/N -» оо и х -» 1 эквивалентны. В этом параграфе рассматриваются лишь такие последовательности Ь = {b0,bi,...), для которых выполнено соотношение bk х k s, где 1 6 2. Усиление ограничений на bk связано с тем, что при условии n/N — оо возникает необходимость в более точном представлении о поведении моментов &. Кроме того, здесь рассматривается предельное поведение компонент щы-р) только при фиксированных значениях р. Мы принимаем также еще одно ограничение: Далее будут последовательно доказаны слабая и локальная сходимость распределений сумм N и Jlp + к нормальному закону (леммы 2.5.1 и 2.5.2), что позволит, используя лемму 1.1.1, найти предельные распределения компонент щы-р) при фиксированном р в рассматриваемой зоне изменения параметров N,n с ограничением (2.5.1). Пусть По теореме Линдеберга для слабой сходимости распределения лг к нормальному закону с центрирующими А/о и нормирующими ОУ/N достаточно показать, что при любом т О имеет место соотношение: Ь (т) -» О при N - оо. Поскольку из соотношения /х4 = о(а4А7) следует слабая сходимость распределения Слг к нормальному закону. Найдем оценку моментов i при х - 1. Поскольку при 1 5 2 величина В (я) ограничена, имеет место соотношение: Заменяя суммирование интегрированием, легко получить, что при q — 6 -1 где Г(г) — гамма-функция. Кроме того, при q — S = —l (а при ограничении 1 5 2 это возможно лишь когда 9=1, (5 = 2) имеем: Отсюда легко получить, что для любых 91,92 1г 9 = Qi + 9г. выполнено соотношение: Поэтому асимптотика моментов совпадает с асимптотикой соответствующих центральных моментов, в частности, Таким образом, условие /х4 = o(a4N) может быть переписано в виде: ЛГ(1 - x)s l - оо.

Пусть г выбрано так, что NPr - 71 гАе 7 — некоторая положительная постоянная. Производя выкладки, аналогичные (2.5.3), находим: Отсюда видно, что т. к. в противном случае мы получим NPT - 00. Наконец, мы можем найти асимптотику ат при 1 6 2: Оценивая NPteajj точно так же, как в (2.3.6), и пользуясь соотношениями ц\ = o(a4N) и NPT х. 1, находим, что Легко найти также оценки для моментов ц\ и а2.. Действительно, а последняя сумма имеет порядок поскольку г (1-а;) -» оо. Таким образом, Е( ) Eff, откуда, в частности, получаем, что Поэтому из теоремы Линдеберга следует слабая сходимость распределения $ к нормальному закону, т. е. при любом фиксированном t. Кроме того, поскольку аг г (т. к. принимает значения не больше г) и ог ж г, нетрудно видеть, используя разложения (р( ;и) = 1 + 0(аги) и v di » и) = 1+ 0{аги) при и -» 0, что при любых фиксированных р и t где мы существенным образом использовали доказанное выше соотношение г = o{p\/N). Таким образом, мы показали справедливость следующего утверждения. Лемма 2.5.1. Пусть n/N - оо так, что N(l — x)s x -» оо, где х выбрано как корень уравнения Na = п. Кроме того, пусть параметр г удовлетворяет соотношению NPr — у, где у — положительная постоянная. Тогда для любых фиксированных put Рассмотрим вопрос о локальной сходимости распределений рассматриваемых сумм к нормальному закону. Лемма 2.5.2. Пусть n/N - 00 так, что N(1 — х)6 1 - оо, где х выбрано как корень уравнения Na = п. Кроме того, пусть параметр г удовлетворяет соотношению NPr -» у, где у — положительная постоянная. Тогда для любого фиксированного р равномерно по целым h имеют место соотношения

Доказательство теорем об объемах деревьев

Пусть У = {уі,...,2/ -}. В [2] (с.206) доказана лемма, из которой следует, что существует такое к0, что для всех к к0 существуют такие целые числа xi,...,Xj 0, что A; = xiyi -\ Ь Xjjjj. Будем нумеровать частицы процесса по порядку в соответствии с отношением "родитель-потомок" и линейным порядком частиц одного поколения. Одной из возможных реализаций рассматриваемого процесса Гальтона—Ватсона является следующая: первые xi частиц порождают по ух потомков, следующие х2 частиц порождают по у2 потомков, и т.д. Наконец, частицы с номерами Х\Ух Н 1-xj-iyj-i +2-Xj, ..., xiyl Л ЬZj-ij/j-i + 1 порождают по у, потомков. Таким образом, мы получим к +1 частиц в данной реализации для любого наперед заданного к ко. Отсюда и следует утверждение леммы. Чтобы использовать результаты главы 2 о канонической схеме размещения, вновь рассмотрим независимые св. & = ( (Л) — l)/d, і = 1,N, где d — максимальный шаг распределения св. 6, равной числу прямых потомков каждой частицы в критическом процессе G Гальтона— Ватсона, генерирующем лес Гальтона—Ватсона $м,п- Напомним также, что bk = Р{ і = 1 + kd}, к = 0,1,..., где v\ — св., равная числу всех частиц, существовавших в критическом процессе Гальтона—Ватсона G, начавшемся с одной частицы, vx (Л) — св., равная числу частиц, существовавших в докритическом процессе Гальтона—Ватсона С?(А), начавшемся с одной частицы. В параграфе 3.1 было доказано, что св. {щ — l)/d,&, г = 1,А/, образуют каноническую схему размещения, в которой роль параметра п играет отношение n/d. Причем, как видно из (3.1.10), имеет место соотношение Ьк х Аг3/2, а из леммы 3.3.1 следует, что Ьк 0 начиная с некоторого А;. Это означает, что условие (2.1.3) выполнено, и мы можем использовать все теоремы главы 2 для получения результатов о рассматриваемом лесе Гальтона—Ватсона.

Уравнение (2.1.1), определяющее выбор параметра х в главе 2, здесь принимает вид о = n/(Nd), т.к. вместо п мы рассматриваем n/d. Это уравнение обеспечивает связь параметров я и А, приведенную в (3.1.11). Таким образом, условие a = n/(Nd) эквивалентно уравнению (3.1.12), определяющее выбор параметра А при условии га/А/2 - 0. Теоремы 3.2.1 и 3.2.2 непосредственно следуют из теорем 2.1.1 и 2.1.2. Пользуясь тем, что при х - 0 имеет место соотношение P{fi = г} с. r zl2xr, из условий N P{ i(A) = 1+rd} - оо и г s теоремы 3.2.3 получаем, что Nxs - оо. Для i O это соотношение, очевидно, истинно. Заметим также, что NPr, определенное для 1г в точности совпадает с NP{v\(\) 1 + (r+)d}, откуда в условиях теоремы 3.2.3 мы имеем NPr -» j. Кроме того, условие (3.2.1) теоремы 3.2.5 эквивалентно условию NP{i/i(X) 1 + (r+)d) - 7i что было показано в [83], поэтому и в условиях теоремы 3.2.5 выполняется NPr - 7 Теперь, применяя теоремы 2.1.3 и 2.1.5 и учитывая, что NPr+h = A/P{ i(A) 1 + (г + h + l)d} 7Q +1/(! а) гАе а определено в теореме 3.2.5, получаем утверждения теорем 3.2.3 и 3.2.5 соответственно. Из теорем 2.1.4 и 2.1.6 непосредственно следуют теоремы 3.2.4 и 3.2.6 соответственно. Перейдем к доказательству теоремы 3.2.7. Поскольку ЬА х. Аг3/2, 5 = 3/2 и по формуле (2.5.3) получаем ox(l-i)"1/2, Отсюда и из соотношения Nda = п получаем, что условие Д/(1 — x)s x - оо, принятое в теореме 2.1.7, равносильно условию га/Л/2 - 0 теоремы 3.2.7. Из (3.1.10) следует, что Пусть /(у) = y zl2xy. Эта функция монотонно убывает на интервале (0;оо). Следовательно, Последнее асимптотическое соотношение легко проверить по правилу Лопиталя, дифференцируя данный интеграл по нижнему пределу. Аналогично, Следовательно, шШк Пусть теперь 7 = е-2, г = {{a + z)/fi — l)/d, где a,/3,z определены в условиях теоремы 3.2.7. Из (3.1.11) и из условий (3.2.2) следует: Действительно, Теперь, применяя теорему 2.1.7 к канонической схеме с компонентами (Т]І - I)/d, і = 1,N, получаем что и доказывает теорему 3.2.7. Заметим, что приведенное доказательство теорем не использует условия F "(l) оо. Однако условие F"(l) оо используется, т.к. мы пользовались соотношением (3.1.10), которое доказывается в [30] с помощью данного условия. Доказательство теорем 3.2.8 и 3.2.9 в [66] не использует условия F "(l) оо. Таким образом, мы доказали, что в предельных теоремах об объемах деревьев леса Гальтона—Ватсона условие F "(l) оо может Шь быть ослаблено до F"(l) оо, и, кроме того, доказали четыре новые те оремы (3.2.1, 3.2.2, 3.2.4, 3.2.6) в тех зонах изменения параметров N,n,p, которые ранее не рассматривались.

Предельные распределения длин циклов в зоне 4

Рассмотрим зону 4. Как уже отмечалось ранее, мы не можем использовать здесь результаты главы 2, поэтому здесь мы рассматриваем св. ь »АГ С распределением Р{6 }- 1.(1-,)- -1 Я fl и на основании заданных таким образом св. ,-, мы используем все вве денные ранее обозначения: Слл, С&\ S? (параграф 1.1), а, аг, а2, а2, //4, /4г), «г (параграф 2.1). По теоремам 4.2.5, 4.2.7, 4.2.9 книги [34] и лемме 15 работы [52] при условии NPT - 7« гАе 7 — некоторая положительная постоянная, получаем, что равномерно Доказательство. Нетрудно видеть, что Пользуясь соотношениями (4.3.3), (4.3.2) и (4.1.1), легко показать, что aT/{aT\/N) - 0. Отсюда и из представления p(d 5 и) = 1 + 0(аги) следует, 4TO p(c,(r);f/( W ))-H Нетрудно показать также, что аг ж г. Действительно, # _ г = Т&г+іхї/к = Pr(l-x)ln(l-x)-i = РТ = ЛРГ-В условиях теоремы 4.1.6 имеем nxr/r -» 7 и NPr - 7» откуда получаем ar г. Оценивая NPeay/ff так же, как в (2.3.6), и используя соотношение Hi/(oAN) - 0, доказанное для зоны 4 в параграфе 4.1, получаем, что Отсюда и из представления f (i[r ;t/(ary/NJ) = 1 + 0(ar/(ary/N)) с помощью соотношения (4.3.3) находим, что р (Ci ft/(crry/N)\ -» 1. Теперь, используя (4.3.1), получаем утверждение леммы. Докажем локальную сходимость распределения 1, + с/г к нормальному закону. ЩШ Лемма 4,3.2. В условиях теоремы 4.1.6 для фиксированного 1 = 0,1,2,... равномерно по всем к таким, что иТ лежит в любом конечном фиксированном интервале. Доказательство. Следуя классическому доказательству локальной теоремы (см., например, [5]), представим вероятность P{CN--J + С/г) = к} по формуле обращения в виде интеграла Лемма будет доказана, если мы покажем, что выбором достаточно больших N,n,A разность R можно сделать сколь угодно малой. Для этого мы рассмотрим отдельно интегралы I\-h и покажем, что каждый из них можно сделать сколь угодно малым. Из леммы 4.3.1 следует, что i\ - 0. Далее, следовательно, интеграл /3 можно сделать сколь угодно малым выбором достаточно большого А. Для оценки /2 заметим, что означает множество таких t из области интегрирования /2, что a fi2 — множество остальных t из области интегрирования /2. Для t є fi2, очевидно, имеет место неравенство В [52] доказано, что интеграл J может быть сделан сколь угодно малым выбором достаточно больших N, п, А. Отсюда, а также из (4.3.6) и (4.3.9) получаем, что 12 можно сделать сколь угодно малым выбором достаточно больших N, п, А. Лемма доказана. Теперь, используя соотношения (4.3.1) и (4.3.5) при к = п и учитывая соотношения а о (см. (4.3.3)) и (п — Nar)2 = o(Na ), доказанное в [52], по лемме 1.1.1 получаем, что Далее, при N - оо и фиксированном / Теперь теорема 4.1.6 следует из соотношений (4.3.10), (4.3.11) и NPT -» 7 где « Далее, по теореме 4.2.1 [34] св. Сдг/n сходится к гамма-распределению с параметрами (а, 1), т. е. для целых ип равномерно по у в любом положительном конечном фиксированном интервале, Г(а) — значение гамма-функции в точке а. Найдем предельное распределение Q/_j + Cj Лемма 4.4.1. Пусть г = zn, постоянная z Є (0; 1/(crry/N)\ -» 1. Теперь, используя (4.3.1), получаем утверждение леммы. Докажем локальную сходимость распределения 1, + с/г к нормальному закону. ЩШ Лемма 4,3.2.

В условиях теоремы 4.1.6 для фиксированного 1 = 0,1,2,... равномерно по всем к таким, что иТ лежит в любом конечном фиксированном интервале. Доказательство. Следуя классическому доказательству локальной теоремы (см., например, [5]), представим вероятность P{CN--J + С/г) = к} по формуле обращения в виде интеграла Лемма будет доказана, если мы покажем, что выбором достаточно больших N,n,A разность R можно сделать сколь угодно малой. Для этого мы рассмотрим отдельно интегралы I\-h и покажем, что каждый из них можно сделать сколь угодно малым. Из леммы 4.3.1 следует, что i\ - 0. Далее, следовательно, интеграл /3 можно сделать сколь угодно малым выбором достаточно большого А. Для оценки /2 заметим, что означает множество таких t из области интегрирования /2, что a fi2 — множество остальных t из области интегрирования /2. Для t є fi2, очевидно, имеет место неравенство В [52] доказано, что интеграл J может быть сделан сколь угодно малым выбором достаточно больших N, п, А. Отсюда, а также из (4.3.6) и (4.), х = 1 — п х. Тогда в зоне 5 при любых фиксированных t и I Доказательство. Легко видеть, что Нетрудно показать, что аТ = о(п), используя (4.3.3) и (4.1.1). Отсюда следует, что (p(dr)\t/n) -+ 1. При доказательстве леммы 1.8.8 из [30] показано, что