Электронная библиотека диссертаций и авторефератов России
dslib.net
Библиотека диссертаций
Навигация
Каталог диссертаций России
Англоязычные диссертации
Диссертации бесплатно
Предстоящие защиты
Рецензии на автореферат
Отчисления авторам
Мой кабинет
Заказы: забрать, оплатить
Мой личный счет
Мой профиль
Мой авторский профиль
Подписки на рассылки



расширенный поиск

Предельные теоремы для лесов Гальтона - Ватсона Чеплюкова, Ирина Александровна

Диссертация, - 480 руб., доставка 1-3 часа, с 10-19 (Московское время), кроме воскресенья

Автореферат - бесплатно, доставка 10 минут, круглосуточно, без выходных и праздников

Чеплюкова, Ирина Александровна. Предельные теоремы для лесов Гальтона - Ватсона : диссертация ... кандидата физико-математических наук : 01.01.05.- Петрозаводск, 2000.- 112 с.: ил. РГБ ОД, 61 01-1/443-2

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

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

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

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

  1. Получить предельные распределения к — ых наибольших объемов деревьев, к — 1,2,...

  2. Выявить условия возникновения гигантского дерева.

  3. Получить предельные теоремы для числа вершин в слоях.

Объекты исследования. Объектами исследования являются леса Гальтона — Ватсона. Эти леса состоят из N корневых деревьев, принадлежащих просто генерируемому семейству. Понятие просто генерируемого семейства деревьев было введено Meir А. и Moon J.W. в 1978 г. Существует связь между такими лесами и совокупностью реализаций ветвящегося процесса Гальтона — Ватсона, начинающегося с N частиц. Точнее говоря, существует взаимно однозначное соответствие между реализациями ветвящегося процесса и классами лесов, в каждом из которых леса отличаются друг от друга только нумерацией вершин (то есть в каждом классе леса изоморфны конкретной реализации). Главное внимание в диссертации уделяется множеству лесов Гальтона — Ватсона, состоящих из N корневых деревьев и п некорневых вершин. Для таких лесов исследуются характеристики, не зависящие от нумерации вершин. В работе рассматривается предельное поведение наибольших объемов деревьев и числа вершин в слоях леса.

Методы исследования. Основными методами, используемыми в диссертации, являются обобщенная схема размещения частиц по ячейкам, методы теории ветвящихся процессов, методы характеристических и производящих функций, а также прямые комбинаторные методы. В большинстве случаев задачи о лесах сводятся к получению предельных теорем для сумм независимых одинаково распределенных случайных величин. Главной технической трудностью получения этих результатов явилось доказательство локальных предельных теорем для таких сумм в схеме серий, включая двумерный случай.

Научная новизна. В работе впервые рассматриваются леса Гальтона — Ватсона. Показано, что изучение характеристик таких лесов может быть сведено к исследованию соответствующих характеристик ветвящихся процессов Гальтона —Ватсона при уело-

вий, что общее число частиц, существовавших в процессе, фиксировано. На этом факте основаны доказательства предельных теорем. Все полученные результаты являются новыми.

Основные положения диссертации, выносимые на защиту. На защиту выносятся:

  1. Установленная связь между просто генерируемыми лесами и ветвящимися процессами Гальтона—Ватсона при условии, что общее число частиц в процессе фиксировано.

  2. Полное описание предельного поведения наибольших к —

ых, к — 1,2,..., членов вариационного ряда объемов дере-

вьев, расположенных в неубывающем порядке.

  1. Условия возникновения гигантского дерева (то есть дерева, число вершин которого имеет порядок п, в то время как каждое из остальных деревьев содержит меньшее по порядку число верщин).

  2. Предельные распределения числа вершин в слоях во всех зонах изменения параметров N, п.

Связь работы с крупными научными программами, темами.

Результаты диссертации были получены в ходе проработки темы "Вероятностные и алгебраические методы исследования дискретных объектов", входящей в план научно — исследовательских работ Института прикладных математических исследований Карельского научного центра РАН (№ гос. регистрации 01.9.60 0 12636) и выполняющейся совместно с кафедрой алгебры и теории вероятностей математического факультета Петрозаводского университета в рамках проекта "Интеграция высшего образования и фундаментальной науки Республики Карелия" Федеральной целевой программы "Государственная поддержка интеграции высшей школы и фундаментальной науки на 1997 — 2000 годы"(ФЦП "Интеграция", per. №634). В 1997 — 98 г.г. автор диссертации была руководителем гранта РФФИ 97 — 01 —00065 "Исследование случайных лесов", в 2000 г. автор входит в состав исполнителей гранта РФФИ 00 — 01 — 00233 "Вероятности на деревьях и лесах" и является победителем конкурса персональных грантов для аспиран-

тов, проведенного Администрацией Санкт-Петербурга, Министерством образования РФ и РАН при участии ФЦП "Интеграция".

Апробация результатов диссертации. Основные результаты диссертации докладывались на IV и V Петрозаводских международных конференциях "Вероятностные методы в дискретной математике" (1996, 2000), 2—ой Международной школе по теории графов (Новосибирск, 1997), 7 —ой Вильнюской конференции по теории вероятностей и математической статистике (1998), семинаре Института прикладных математических исследований Карельского научного центра РАН (2000).

Публикация результатов. По теме диссертационной работы опубликовано 7 научных работ, из них 3 статьи в центральном журнале, 1 статья в сборнике трудов международной конференции, 2 статьи в сборниках научных трудов и 1 тезисы доклада на международной конференции.

Структура и объем диссертации. Диссертация состоит из введения, трех глав и списка литературы. Общий объем диссертации составляет 112 страниц. Список литературы содержит 69 наименований.