Главная » 2014 » Июль » 29 » Скачать Леса Гальтона-Ватсона и случайные подстановки. Казимиров, Николай Игоревич бесплатно
10:01 PM
Скачать Леса Гальтона-Ватсона и случайные подстановки. Казимиров, Николай Игоревич бесплатно
Леса Гальтона-Ватсона и случайные подстановки
Диссертация
Автор: Казимиров, Николай Игоревич
Название: Леса Гальтона-Ватсона и случайные подстановки
Справка: Казимиров, Николай Игоревич. Леса Гальтона-Ватсона и случайные подстановки : диссертация кандидата физико-математических наук : 01.01.09 Петрозаводск, 2003 127 c. : 61 04-1/438
Объем: 127 стр.
Информация: Петрозаводск, 2003
Содержание:
Введение
1 Обобщенная схема размещения
11 Основные определения и обозначения
12 Графы
13 Примеры применения обобщенной схемы размещения
14 Описание класса рассматриваемых схем размещения
15 Случайные подстановки и случайные рекурсивные леса
2 Некоторые свойства обобщенной схемы размещения
21 Обозначения и сводка результатов
22 Случай N оо, п = const
23 Случай n/N О, N, п оо
24 Случай пх N, N,n-t оо
25 Случай n/N оо при некоторых ограничениях
26 Некоторые условия отсутствия гигантской компоненты
3 Леса Гальтона—Ватсона
31 Определение леса Гальтона—Ватсона
32 Сводка результатов
33 Доказательство теорем об объемах деревьев
34 Доказательство теорем о/^ит
4 Случайные подстановки с известным числом циклов
41 Сводка результатов
42 Предельные распределения длин циклов при п = O(N)
43 Предельные распределения длин циклов в зоне 4
44 Предельное распределение длин циклов в зоне 5
45 Предельное распределение длин циклов в зоне 6
46 Условия возникновения гигантского цикла
Введение:
В настоящее время широкое распространение в комбинаторном анализе получил теоретико-вероятностный подход. Хорошо развитые в теории вероятностей методы асимптотического анализа успешно используются при решении сложных комбинаторных задач. Впервые такой подход был использован В. Л. Гончаровым в статьях [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), найдены предельные распределения р-х по величине компонент, причем как для фиксированного р, так и для р —> оо так, что р3 = о(п). Кроме того, при усилении ограничений на рассматриваемые схемы размещения получены предельные распределения для р-х компонент при фиксированном р и 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) возникает гигантский цикл.
Основными результатами диссертации являются:
2. Доказательство того, что в известных ранее теоремах о предельном поведении наибольших объемов деревьев леса Гальтона—Ватсона, числа деревьев заданного объема и высоты леса, условие конечности третьего момента распределения числа прямых потомков каждой частицы в процессе, генерирующем лес Гальтона—Ватсона, может быть заменено на условие конечности второго момента.
3. Предельные распределения объемов всех деревьев леса Гальтона— Ватсона при постоянном числе п некорневых вершин.
4. Предельные распределения р-ых по величине объемов деревьев леса Гальтона—Ватсона при N,n,p оо так, что р3 = о(п), п = O(N).
5. Полное описание предельного поведения длин р-ых по величине длин циклов случайной подстановки степени п с N циклами при п -» оо, включая случай р -> оо при ограничениях п — N = O(N), р3 — о{п — N).
6. Доказательство того, что в случайной подстановке степени п с N циклами гигантский цикл возникает только при 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 гг. автор являлся одним из исполнителей гранта РФФИ 0001-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.