Предельные теоремы для лесов Гальтона - Ватсона тема автореферата и диссертации по математике, 01.01.05 ВАК РФ

На правах рукописи

РГБ ОД

1 7 яня шО

Чеплюкова Ирина Александровна

ПРЕДЕЛЬНЫЕ ТЕОРЕМЫ ДЛЯ ЛЕСОВ ГАЛЬТОНА-ВАТСОНА

01.01.05 - теория вероятностей и математическая статистика

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико - математических наук

Москва 2000

Работа выполнена на кафедре алгебры и теории вероятностей Петрозаводского государственного университета.

Научный руководитель: доктор физико-математических наук, профессор Ю.Л.Павлов.

Официальные оппоненты: доктор физико-математических наук, профессор В.Ф.Колчин, доктор физико-математических наук, профессор А.А.Грушо.

Ведущая организация: Математический институт Российской Академии Наук им. В.А.Стеклова.

Защита состоится 19 декабря 2000 г. в 16 часов на заседании диссертационного совета К.063.68.05 в Московском государственном институте электроники и математики (МГИЭМ) по адресу: 109028, Москва, Б.Трехсвятительский пер., 3/12

С диссертацией можно ознакомиться в библиотеке Московского государственного института электроники и математики.

Автореферат разослан " 40 " иОЛЛ)/М 2000 г.

Ученый секретарь диссертационного совета,

к.ф.-м.н., доцент

П.В.Шнурков

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

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

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

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

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

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

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

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

ых, к = 1,2,..., членов вариационного ряда объемов дере- • вьев, расположенных в неубывающем порядке.

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

4. Предельные распределения числа вершин в слоях во всех зонах изменения параметров 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 наименований.

СОДЕРЖАНИЕ РАБОТЫ

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

Первая глава носит вспомогательный характер и содержит понятия, определения и результаты других авторов, которые будут использованы в последующих главах. В п. 1.1 дано определение просто генерируемых лесов, в основе которого лежит определение просто генерируемого семейства корневых деревьев (Meir A., Moon J.W., 1978 г.). Во многих работах отмечалась связь между просто генерируемыми семействами корневых деревьев и совокупностью реализаций некоторого ветвящегося процесса

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

В п. 1.3 дано описание класса рассматриваемых в диссертации лесов. Согласно п. 1.2, множеству лесов, состоящих из N деревьев, принадлежащих просто генерируемому семейству, естественным образом соответствует ветвящийся процесс Гальтона — Ватсона С?, начинающийся с N частиц. Обозначим множество таких лесов, состоящих из N корневых деревьев с п некорневыми вершинами. Процесс С? индуцирует распределение вероятностей на при этом, если дм,„ — реализация процесса О с N + п частицами, то

„т0 пц т„

где 1/дг — общее число частиц, существовавших в ветвящемся процессе <3 до его вырождения, т,,0 < г ^ п, — число частиц, имеющих ровно г потомков,

то + тп1 + • • • + тп = N + п, ГП1 + 2т2 + • • • + птп — п

и рк — вероятность рождения к прямых потомков у одной частицы, к — 0,1,2,... Там же доказана теорема (теорема 1.3.1) являющаяся главным результатом главы 1.

Пусть т](дм,?г) — некоторая числовая характеристика реализации ди.п, — аналогичная характеристика ветвящегося процесса С. Пусть А(дн:П) означает класс лесов из Удг.п изоморфных реализации дм,п- Если лес / из Здг.п, принадлежит множеству А(дм,п)5 т° положим

т] = т](Л =

Это означает, что величина т] принимает одинаковые значения на всех лесах из множества А(д^1П).

ТЕОРЕМА 1,3.1. Справедливо равенство

Р{?? = х) = Р{т?(С) = х\иц = N + п}.

Эта теорема показывает, что изучение числовых характеристик леса Гальтона — Ватсона можно свести к исследованию аналогичных характеристик ветвящихся процессов С при условии, что общее число частиц, существовавших в процессе до его вырождения, равно N+4. Теорема 1.3.1 лежит в основе доказательства результатов, полученных во второй и третьей главах.

Для того, чтобы описать рассматриваемый в диссертации класс лесов, введем вспомогательную случайную величину £, имеющую целочисленное распределение

Р{£ = А}=Рь ¿ = 0,1,...,

с максимальным шагом с( и производящей функцией

оо к=0

где множество значений имеющих положительную вероятность, содержит ноль и не совпадает с множеством {0,1}. Пусть

М£ = 1, Щ = В, 1)<оо.

В диссертации рассматривается множество лесов Гальтона— Ватсона З^.п, состоящих из N корневых деревьев и п некорневых вершин, определяемое ветвящимся процессом С, у которого начальное число частиц равно ЛГ, распределение числа прямых потомков имеет вид

Р*(А) = Л*рк/ПЛ), (1)

где 0 < А < 1. Легко видеть, что при Л < 1 процесс С является докритическим, а при А = 1 — критическим. В п. 1.3 показано, что для решения поставленных в диссертации задач такой выбор распределения (1) всегда возможен. Более того, утверждение теоремы 1.3.1 остается справедливым при любых значениях параметра А, для которого ^(А) существует. Отсюда следует, что мы можем задавать А наиболее удобным для доказательства результатов способом.

В п. 1.3 показано, что класс лесов Гальтона — Ватсона шире класса лесов рассматриваемого в монографии Ю.Л. Павлова "Случайные леса" (1996), где исследовано предельное поведение максимального объема дерева в лесе, число деревьев заданного объема и высоты леса. Теорема 1.3.1 позволяет утверждать, что все эти результаты остаются справедливыми и для лесов Гальтона — Ватсона.

В п. 1.4 приведены хорошо известные результаты о ветвящихся процессах, которые используются при доказательстве основных теорем диссертации в следующих главах.

Вторая глава посвящена исследованию предельного поведения наибольших к — ых, к = 1,2,..., членов вариационного ряда объемов деревьев расположенных в неубывающем порядке и выявлению условий возникновения гигантского дерева. В п. 2.1 дается постановка задачи и сводка полученных во второй главе результатов. Обозначим ^(У),... — случайные величины, равные объемам деревьев из 3"лг,и и имеющие корневые вершины с номерами 1,...,ЛГ соответственно, а 1/(1) (З7), • ■ • ,г/(^)(3") — вариационный ряд объемов деревьев в лесе, полученный расположением 1>1 (З7),..., 1>м (3") в неубывающем порядке. Классу соответствует ветвящийся процесс й, распадающийся на N процессов , ■ ■ • начинающихся с одной частицы. Введем случайные величины г/(1>,... ,г>(ЛГ), равные числу частиц, существовавших соответственно в процессах Оь ... ,(7дг до их вырождения.

Из теоремы 1.3.1 следует, что для всех п, удовлетворяющих условию Р{г/дг = N +п} > 0, справедливо соотношение

Р{1/1(3") = ки...,1= /глг} = = Р{г/(1) =кг,..., = кы\иц =N+71). (2)

Это соотношение показывает, что рассматриваемая задача сводится к обобщенной схеме размещения частиц по ячейкам, введенной и исследованной в работах В.Ф.Колчина.

Введем вспомогательные независимые одинаково распреде-

11} IN) -(1) -(N)

ленные случайные величины г^ ,..., иг и ит ,..., уг для ко-

торых

=к} = Р{г^(,) = к\и{1) ^ г + 1},

Р{Р«0 = к} = Р{1/(г) = > г + 1}, г = 1,..., Лг, к = 1, 2,... Обозначим также

= 1/(4 + ... + „(лг-0 + р(лг-«+1) + ... + £>(аг)) г = 0,1,..., ЛГ — 1

Рг = Р{г/(1> >г+ 1}, ог^б^1». Из (2) и соотношения

г=0 ^ 1 >

> г + 1,... <С г + 1}-

вытекает следующее утверждение. ч

. ЛЕММА 2.1.1. При 5 = 0,1,2,... ип таких, что Р{^л- = N + + п} > 0

-ЧГп -Р ^Р' -l)...(N-i+ 1) = N + п}

~ ¿3 г'! Р{^ = А'+п}'

Эта лемма сводит исследование случайных величин 1/(Л-_5)(3') к изучению предельного поведения сумм вспомогательных независимых одинаково распределенных слагаемых. Основные результаты второй главы (теоремы 2.1.6 — 2.1.10) доказаны с помощью леммы 2.1.1, приведем некоторые из полученных в этой главе теорем.

и

ТЕОРЕМА 2.1.7. Пусть N, п -> оо так, что п пробегает значения, кратные d, и 0 < сх < n/N < с2 < со. Пусть А = A(N,n) определяется соотношением

AF'(A) _ п F(А) ~ N + n'

а = (X/F(X))d.

Если г = r(N,n) пробегает значения, кратные d, и такие, что

N / А V d F{\) \F(X)) гЗ/з^/^Тв^7'

где 7 — положительная постоянная, то для любых фиксированных к = 0,±1,±2,... u s = 0,1,2,...

P{^._S)(J) ^ г + kd + 1} = ехр ¿ i (^у) + о(1).

ТЕОРЕМА 2.1.9. Пусть N, п -» со так, что п пробегает значения, кратные d, и Bn/N2 7, где 7 — некоторая положительная постоянная. Тогда для любого фиксированного положительного z и любого фиксированного s = 0,1,2,...

С 1 •> 00 s 1

Р{^Л'-.)(Э-)/п < Z} 73/2ехр | —I £ — £ -Ik+ibzn),

где

I0(u,v) = (v3 ехр{1/и})-1/2,

Г ехр{ —1/(2(г> - а?!-----.. .xk

h(u,v)~ j {27r)k/4xí...xk(v-x1-----^-))3/2 '

Xfclu, v)

Xk(u, v) = {Xj > 11, i=l,...,k, x\ H-----hXfc íC u}, k - 1,2,...

ТЕОРЕМА 2.1.10. Пусть N,n оо так, что п пробегает значения, кратные d,n/N2 оо. Тогда для любого фиксированного положительного z

< ^iV2} ехр{-Е(0, z)} £ ~}Е*{0, z),

i=о г'

где

E{0,z) = v?2/zkB, s = 1,2,...

Теоремы 2.1.6 — 2.1.10 дают полное описание предельного поведения наибольших членов вариационного ряда объемов деревьев. Такое исследование позволяет сравнить эти результаты с поведением максимального объема дерева и установить условия возникновения гигантского дерева. В результате этого оказалось, что гигантское дерево появляется только в случае п —> оо так, что n/N2 оо. .

В п.п. 2.2 — 2.4 рассматривается асимптотика распределения случайной величины uTti в различных зонах изменения параметров N и n, а в п. 2.5 с помощью леммы 2.1.1 и результатов п.п. 2.2 — 2.4 доказаны теоремы 2.1.6 — 2.1.10.

Третья глава посвящена исследованию распределения числа вершин в слоях леса Гальтона —Ватсона. Назовем i-ым слоем леса множество вершин, для которых число дуг, образующих путь от корня до вершины, равно t. В п. 3.1 дана постановка задачи и сводка полученных в третьей главе результатов. Обозначим /г(£,3"лг,п) число вершин в t — ом слое леса 3"дг,„,/хлг(<) — число частиц t — го поколения ветвящегося процесса G. Распределения p-it^N^) и pn{î) связаны следующим образом.

ЛЕММА 3.1.1. При любых х и t справедливо равенство

Р {fi(t, 3"ллп) = = P{aîjv(î) = x\i>N = N + п].

Эта лемма показывает, что изучение поведения числа вершин в слоях леса 3"л?,„ сводится к рассмотрению числа частиц соответствующих поколений ветвящегося процесса G, начинающегося с N частиц при условии, что общее число частиц, существовавших

в процессе до его вырождения, равно N+п. В третьей главе получены предельные теоремы для fx(t, Tjv.n) во всех зонах изменения параметров N и п и для большинства номеров слоев t (теоремы 3.1.1 - 3.1.11).

Номера t слоев леса в полученных результатах удовлетворяет соотношению t < т, где г — высота леса (максимальный номер слоя). Ниже приводится таблица 1, где отдельно указаны номера слоев t, для которых получены предельные распределения 3"jv,n), а также номера слоев, для которых такое исследование провести не удалось. В начале таблицы перечислены возможные значения высоты леса, откуда видно, что в некоторых случаях полученные результаты охватывают нижние и средние слои, и не охватывают верхние слои, примыкающие к высоте. Столбцы таблицы соответствуют четырем зонам изменения параметров N, п, задаваемым следующим образом:

I : N,n -» oo,n/N 0;

II : N, n -»• oo, 0 < c3 ^ n/N ^ 04 < 00;

III : N, n 00, n/N 00, n/N2 0;

IV : n oo,n/N2 ^ c5 > 0.

Заметим, что в зоне I рассмотрены слои с номерами t ^ 3. Это значит, что для этой зоны задача решена полностью, поскольку при ¿ = 1,2 распределение частиц по слоям легко получить непосредственно из (1). Из приведенной таблицы видно, что полное описание предельного поведения случайной величины получено в зонах I и IV, а в зоне II не рассмотрены только самые верхние слои. Наиболее сложная ситуация оказалась в зоне III, где остались некоторые области изменения параметров, не охваченные полученными результатами. Провести исследование в этих областях не удалось по-видимому, из-за технических сложностей использованных в работе методов доказательств. Заметим также, что полученные предельные теоремы в зонах I - III являются локальными, а в зоне IV доказана лишь слабая сходимость к предельным распределениям.

Приведем некоторые из полученных в главе 3 результатов.

ТЕОРЕМА 3.1.1. При n,t -» 00,N/Jn 0,N/t -» 0,t/yß -> 0, для

Таблица 1: Сводка результатов

I II III /1/

т NmT~1 00 NmT = 0(1) г = 0(пМ£М) r = O(Vn)

н е и с с л е Д о в а н о t = т — к, k= 1,2,... 1. tiV/n oo, не выполнено хотя бы одно из условий: tN , л. nln(JV*/ns) U' N/y/n^. (Nimt/n3)L, где 0 < £ < oo. 2. i = 0(n/N), не выполнено хотя бы одно из условий: п3/^4 0, iiV/n -> оо. 3. t = o(n/N), не выполнено неравенство Nt/^ß < (N/t3)L.

и с с л е Д о в а н о tz з, Nm? оо < > 1, ЛГтг -»■ oo 1. tJV/n оо, tN . n nln(W4/n3) u> JV/v/n ^ (Nimt/n3)L. 2. t = 0(n/N), n3/iV4 0, N/\/n < (М*/п?)ь. 3. i = o(n/N), NW/n3 >c> 0, Nt/^/n < (N/t3)L. 4. NH2/n3 = o{ 1). t ^ Cv/n, 0 < с < oo

любого фиксированного х > О

ТЕОРЕМА 3.1.2. Пусть N,n,t oo,N/y/n 0,2N/{Bt) а, где а — некоторая положительная постоянная. Тогда для любого фиксированного х > 0

|2 ß(t,3N,n) \ _üf а* Р\-+i{

где K2k+i(2x) — значение функции распределения х2 с 2к + 4 степенями свободы в точке 2х.

ТЕОРЕМА 3.1.6. Пусть N, п оо так, что n/N ^ с < оо, Nm1 оо. Пусть так же t ^ 3 при n/N -)■ 0 и t -» оо в противном случае. Тогда равномерно относительно к, для которых у = (к --Nm1)/\J{N + п)В\т1~1 лежит в любом фиксированном конечном интервале,

¿(1 + о(1))

yj2ix{N + njßxm'-1

'К}-

ТЕОРЕМА 3.1.9. Пусть N,n -> оо лшк, что n/N -> оо, а t = = t(N,n) выбрано так, что tN/n -> О, NH2/пъ ^ 0 а для некоторого L > 0 лри достаточно больших N,n выполняется неравенство Nt/^/n < (N/t3)1. Тогда равномерно относительно к, для которых у = (к- Nml)/y/NBt лежит в любом фиксированном конечном интервале,

В п.3.2 рассматривается асимптотика распределения случайной величины pw(t) при условии ßN(t) > 0 в критическом случае. В п.3.3 доказана слабая сходимость совместного распределения (wv(i), ^Vv(f)) к нормальному закону в докритическом случае, где viv(i) = /ijv(O) + ••• +pN(t - 1W(0) = 0,i = 1,2,... С помощью результатов п.3.3 и оценок для характеристической функции

случайного вектора (^(г) - М/хх(<), (¿) - полученных в

п.3.4, в п.3.5 доказана локальная сходимость совместного распределения (/м^), 1/лг(<)) к нормальному закону. В п.3.6 с помощью результатов п.п.3.2 и 3.4 изучается предельное поведение /лле(£) при условии им = N + п. Доказательства теорем 3.1.1 — 2.1.11, основанные на лемме 3.1.1 и вспомогательных утверждений п.3.6, приведены в п.3.7.

СПИСОК ОПУБЛИКОВАННЫХ РАБОТ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Чеплкжова И.А. О распределении числа деревьев заданного объема в случайном плоском лесе. Статистический анализ нелинейных систем. ПетрГУ, 1996, с.48 —55.

2. Чеплюкова И.А. Предельные распределения наибольших деревьев в случайном лесе. Труды Петрозаводского ун-та. Сер. математика, 1997, вып.4, с. 130— 138.

3. Чеплюкова И.А. Предельные распределения числа вершин в слоях случайного леса. Дискретная математика. 1997, т.9, вып.4, с. 150-157.

4. Egorova I.A. The distribution of vertices in strata of plane planted forest. In: Probabilitic Methods in Discrete Mathematics : Proc. 4th Inter. Petrozavodsk Conf. YSP, Utrecht, 1997, p.p.179-188.

5. Cheplykova I.A., Pavlov Yu.L. Random simply generated forests. 7th Vilnius Conf. on Probab. Theory. 1998, p. 177.

6. Чеплюкова И.А. Возникновение гигантского дерева в случайном лесе. Дискретная математика. 1998, т.10, вып.1, с.П 1-126.

7. Павлов Ю.Л., Чеплюкова И.А. Предельные распределения числа вершин в слоях просто генерируемого леса. Дискретная математика. 1999, т. 11, вып.1, с.97 —112.

АР №040110 от 10.11.96. Гигиенический сертификат №10.КЦ.34.953.П.00136.03.99 от

05.03.99. Подписано в печать 30.10.2000. Формат 60 х 84 1/16. Бумага офсетная. Офсетная печать. 1 уч.-изд.л. 6 усл. кр.-отт. Тираж 100 экз. Изд. №211. Издательство Петрозаводского государственного университета 185640, Петрозаводск, пр. Ленина, 33

Введение

1. Леса Гальтона-Ватсона

1.1. Определение просто генерируемых лесов.

1.2. Связь между просто генерируемыми семействами деревьев и ветвящимися процессами Гальтона-Ватсона

1.3. Описание класса рассматриваемых лесов.

1.4. Вспомогательные утверждения.

2. Возникновение гигантского дерева

2.1. Постановка задачи и сводка результатов.

2.2. Асимптотика распределения vrj при n/N2 —» 0.

2.3. Асимптотика распределения vr>t при Bn/N2 —>• 7.

2.4. Асимптотическое распределение ur>t при n/N2 —>00.

2.5. Доказательство основных результатов.

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

3.1. Постановка задачи и сводка результатов.

3.2. Асимптотика распределения при условии ¡iN(t) > 0 в критическом случае

3.3. Слабая сходимость к нормальному закону совместного распределения \ßi(t),vi(t)) в докритическом случае.

3.4. Некоторые оценки для характеристической функции ^(Вь©2).

3.5. Локальная сходимость совместного распределения (ддг(£), ^м^)) к нормальному закону в докритическом случае

3.6. Асимптотика поведения при условии и^ = N + п

3.7. Доказательство основных результатов.

Вероятностные методы широко применяются для решения комбинаторных задач (см., например, [21, 24, 47, 69]). При задании вероятностной меры на множестве изучаемых комбинаторных объектов различные числовые характеристики таких объектов можно рассматривать как случайные величины и использовать для их исследования методы теории вероятностей. В этом случае вероятностные формулировки комбинаторных задач дают возможность использовать хорошо развитый теоретико-вероятностный аналитический аппарат, что позволяет во многих случаях существенно упростить получение результатов о комбинаторных объектах или даже находить решения, которые не удается получить с помощью других методов. Вероятностный подход обеспечивает удобную форму изложения и помогает применять хорошо развитые методы асимптотического анализа. Одним из важнейших направлений исследований является изучение предельных свойств комбинаторных объектов, проявляющихся при неограниченном возрастании числа элементов, образующих такие объекты. Во многих случаях распределение характеристик комбинаторных объектов удается представить в виде условных распределений сумм независимых случайных величин. Это дает возможность использовать для их изучения предельные теоремы для сумм независимых случайных величин.

Впервые вероятностный анализ дискретных объектов осуществлен В. А. Гончаровым в статьях [8, 9]. С тех пор по данной тематике появилось множество публикаций. Одним из направлений работ, сформировавшихся к настоящему времени, является изучение случайных графов [21, 47, 49-51, 57, 61, 63].

Объектом исследования диссертации являются деревья и леса, являющиеся удобным средством моделирования разнообразных природных и технических систем. Они находят применение при моделировании транспортных и телекоммуникационных систем [1, 63], в прикладной статистике [13, 26], для исследования систем случайных уравнений [23], в анализе вычислительных алгоритмов [64]. Деревья и леса часто являются подграфами графов более сложной структуры, поэтому их изучение полезно в целом для теории графов [5, 21, 22, 51, 57, 66]. Значительное развитие в этом направлении получило исследование случайных однозначных отображений конечного множества в себя [21]. Такие отображения можно представить ориентированным графом, из каждой вершины которого выходит одна дуга, соединяющая вершину с ее образом при отображении. Следовательно, любая компонента связности графа содержит ровно один цикл, при этом циклические вершины являются корнями деревьев. Если убрать дуги, соединяющие циклические вершины, то полученный подграф представляет собой лес, состоящий из корневых деревьев. Это означает, что результаты о случайных лесах можно использовать для изучения случайных отображений.

Систематическое изучение случайных лесов началось в работах [28 — 31] с помощью обобщенной схемы размещения [21, 24]. В этих работах получены предельные распределения числа частиц заданного объема и предельные распределения максимального объема дерева для лесов, состоящих из N корневых деревьев с п помеченными вершинами, где корни занумерованы числами 1,.,ЛГ, а некорневые вершины — 1,., п. При этом на множестве всех таких лесов задавалось равномерное распределение вероятностей. Применению методов теории ветвящихся процессов для изучения случайных лесов предшествовало рассмотрение случайных деревьев с занумерованными вершинами и соответствующих им процессов Галътона—Ватсона с пуассоновским распределением числа потомков каждой частицы. Впервые на эту возможность указано в статье В.Е. Степанова [50], а систематически такое исследование проведено в работах В.Ф. Колчина [18 — 20], причем рассматривались и случайные деревья, имеющие ограничения на кратности вершин. Ветвящиеся процессы Галътона — Ватсона с пуассоновским распределением числа потомков одной частицы при изучении случайных лесов, состоящих из корневых деревьев с занумерованными вершинами, впервые использованы в статьях [15, 32, 33], где рассматривались распределения кратностей вершин и предельные распределения высоты леса, равновероятно выбранного из множества таких лесов. В работах [34, 67, 68] получены предельные распределения числа вершин в слоях леса, а в [16, 17] исследуется аналогичная задача для лесов с ограничениями на кратности вершин. Следующий этап развития этого направления начался с установления связи между начинающимися с одной частицы процессами Галътона—Ватсона с геометрическим распределением числа потомков каждой частицы и посажеными деревьями [45] (то есть плоскими деревьями с висячими корнями и непомеченными вершинами). Эта связь впервые установлена в [6, 35, 36]. В работах [35, 36] связь между ветвящимися процессами и деревьями основывалась на том факте, что если /4.(Тп) является числом вершин кратности г в ¿-ом слое дерева Тп объема п, то распределение матрицы совпадает с распределением матрицы \\цг({)\\^=0, где — число частиц в ветвящемся процессе, имеющего в момент t ровно г потомков при условии, что общее число частиц в процессе равно п. В [6] установлено более тонкое, "потраекторное", соответствие между ветвящимися процессами Галътона — Ватсона с пуассоновским и геометрическим распределениями потомков частицы и двумя множествами корневых деревьев — деревьев с помеченными вершинами и посажеными деревьями. Связь между лесами, состоящими из N посаженых деревьев, и начинающимися с N частиц ветвящимися процесса Гальтона—Ватсона с геометрическим распределением числа прямых потомков одной частицы, впервые рассматривается в работах [11,38]. Там же получены число различных лесов в таком множестве и предельные распределения высоты, при этом на множестве всех этих лесов задавалось равномерное распределение вероятностей. В [2 — 4, 62] изучались случайные леса, состоящие из некорневых деревьев с помеченными вершинами, для которых были получены предельные распределения ряда характеристик. Сходство предельных распределений числовых характеристик деревьев и лесов различных классов, а также сходство методов их получения, привело к появлению общих теорем, остающихся справедливыми при достаточно общих ограничениях на классы деревьев и лесов. Для случайных деревьев такие общие теоремы были приведены в [37], а для случайных лесов — в [39 — 41]. Систематическое изложение результатов о случайных лесах содержится в монографии Ю.Л. Павлова [42].

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

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

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

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

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

Основными методами исследования в диссертации являются обобщенная схема размещения и методы теории ветвящихся процессов. Главную трудность при получении этих результатов составляет доказательство локальных предельных теорем в схеме серий, включая область больших уклонений. В последнее время появились работы (см. [27]), дающие ряд достаточных условий локальной сходимости. Хотя проверка таких условий весьма трудоемкая, в некоторых случаях их использование позволяет упрощать получение результатов о комбинаторных объектах и даже обобщать их. Например, в [14] показано, что ряд результатов [42] остается справедливым при отказе от условия существования третьего момента распределения числа потомков каждой частицы процесса Гальтона — Ватсона. Можно надеяться, что в дальнейших исследованиях подобные утверждения можно будет получить и для характеристик лесов Гальтона — Ватсона, рассматриваемых в диссертации.

Диссертация состоит из трех глав. Первая глава носит вспомогательный характер. В первом параграфе первой главы (п. 1.1) дано определение просто генерируемых лесов, в основе которого лежит, введенное Мейром и Муном [65], определение просто генерируемого семейства корневых деревьев. Во втором параграфе первой главы рассматривается связь между просто генерируемыми семействами корневых деревьев и совокупностью реализаций некоторого ветвящегося процесса Гальтона — Ватсона, начинающегося с одной частицы. В третьем параграфе первой главы дано описание класса рассматриваемых лесов. Эти леса состоят из п некорневых вершин и N просто генерируемых деревьев, поэтому их можно назвать просто генерируемыми лесами, а в силу существования связи с ветвящимися процессами — лесами Гальтона —Ватсона. Там же доказана теорема, которая показывает, что изучение числовых характеристик случайного леса можно свести к исследованию аналогичных характеристик ветвящихся процессов при условии, что общее число частиц, существовавших в процессе, фиксировано. Эта теорема является главным результатом первой главы и лежит в основе доказательства всех полученных в диссертации теорем. В четвертом параграфе этой главы (п. 1.4) приведены хорошо известные результаты о ветвящихся процессах, которые используются при доказательстве основных теорем диссертации в следующих главах.Вторая глава посвящена исследованию предельного поведения членов вариационного ряда объемов деревьев, расположенных в неубывающем порядке. Результаты этой главы сформулированы в первом параграфе, а доказаны в пятом с помощью вспомогательных утверждений, доказательства которых приведены в параграфах 2 —4. В [42] получены предельные распределения максимального объема дерева в случайном лесе, однако, этого недостаточно, чтобы выяснить, является ли максимальное дерево гигантским. В результате исследования, проведенного во второй главе, оказалось, что гигантское дерево появляется лишь в случае стремления к бесконечности отношения п/И2. В третьей главе получены предельные распределения числа вершин в слоях. Эти результаты сформулированы в первом параграфе, а их доказательства приведены в седьмом параграфе 7 с помощью вспомогательных утверждений, полученных в параграфах 2 — 4.

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

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

2) Полное описание предельного поведения наибольших к — ых, к = = 1,2,. , членов вариационного ряда объемов деревьев, расположенных в неубывающем порядке.

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

4) Предельные распределения числа вершин в слоях во всех зонах изменения ЛГ, п.

Основные результаты диссертации опубликованы автором в семи работах [43, 52 — 55, 58, 59], из них 3 статьи в центральном журнале, 1 статья в сборнике трудов международной конференции, 2 статьи в сборниках научных трудов и 1 тезисы доклада на международной конференции. Они также нашли отражение в монографии [69] и докладывались на IV и V Петрозаводских международных конференциях "Вероятностные методы в дискретной математике" (1996, 2000), 2-ой Международной школе по теории графов (Новосибирск, 1997), 7-ой Вильнюсской конференции по теории вероятностей и математической статистике (1998), семинаре Института прикладных математических исследований Карельского научного центра РАН (2000). В 1997 — 98 г.г. автор диссертации была руководителем гранта РФФИ 97 — 01—00065 " Исследование случайных лесов". В 2000 г. автор является одним из исполнителей гранта РФФИ 00 — 01 —00233 "Вероятности на деревьях и лесах" и победителем конкурса персональных грантов для аспирантов, проведенного Администрацией Санкт-Петербурга, Министерством образования РФ и РАН при участии Федеральной целевой программы "Государственная поддержка интеграции высшей школы и фундаментальной науки на 1997 — 2000 годы" (ФЦП "Интеграция").

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

В диссертации принята следующая нумерация теорем, лемм и формул. В каждом параграфе каждой главы используется своя нумерация этих объектов, выражаемая одним числом. При ссылках внутри одного параграфа используется только такая нумерация. При ссылке внутри главы на объект другого параграфа перед основным номером указывается номер параграфа, а при ссылке на объект другой главы добавляется номер главы. Например, на теорему 1 из параграфа 3 главы 2 в других параграфах этой главы ссылаются как на теорему 3.1, а в других главах — как на теорему 1.3.1.

Для обозначения произвольных положительных постоянных в формулировках и доказательствах теорем и лемм второй и третьей глав диссертации ИСПОЛЬЗуЮТСЯ СИМВОЛЫ C,Ci,C2,.

1. Борисов Г. А. Методы автоматизированного проектирования лесо-транспорта. Петрозаводск, КФ АН СССР, 1978.

2. Бритиков В.Е. Предельные теоремы для максимального объема дерева в случайном лесе из некорневых деревьев. — Вероятностные задачи дискретной математики. М.,МИЭМ, 1987,с. 84 — 91.

3. Бритиков В.Е. Асимптотика числа лесов из некорневых деревьев. — Математические заметки, 1988, т.43, вып.5, с.672 — 684.

4. Бритиков В.Е. Предельное поведение числа деревьев заданного объема в случайном лесе из некорневых деревьев. — Вероятностные задачи дискретной математики. М., МИЭМ, 1988, с.7— 12.

5. Бритиков В.Е. О структуре случайного графа вблизи критической точки. — Дискретная математика, 1989, т.1, вып.З, с. 121 — 126.

6. Ватутин В.А. Распределение расстояния до корня минимального поддерева, содержащего все вершины данной высоты. — Теория вероятностей и ее применения, 1993, т.38, вып.2, с.273 —287.

7. Висков О.В. Несколько замечаний о ветвящихся процессах. — Математические заметки, 1970, т.8, вып.4, с.409 —418.

8. Гончаров В.Л. О распределение циклов в перестановках. Докл. АН СССР. 1942, т.35, вып.9, с.299-301.

9. Гончаров В.Л. Из области комбинаторики. Изв. АН СССР. Сер. матем. 1944, т.8, вып.1, с.3 — 48.

10. Дрмота М. Распределение высоты листьев корневых деревьев. — Дискретная математика, 1994, т.6, вып.1, с.67 —82.

11. Земляченко В.Н., Павлов ЮЛ. Леса из плоских посаженых деревьев и ветвящиеся процессы. — Труды Петрозаводского ун-та. Сер. прикладная математика и информатика. 1992, вып.1, с. 130 — 135.

12. Ибрагимов ИЛ., Линник Ю.В. Независимые и стационарно связанные величины. М., Наука, 1965.

13. Иванов В.А., Ивченко Г.И., Медведев Ю.И. Дискретные задачи в теории вероятностей. — Итоги науки и техники. Сер. теория вероятн., матем. стат., теор. кибернетика. 1984, вып.22, с.З — 60.

14. Казимиров Н.И., Павлов ЮЛ. Одно замечание о лесах Гальтона-Ватсона. — Дискретная математика, 2000, т. 12, вып.1, с.47 —59.

15. Калинина Н.Б., Павлов ЮЛ. Распределение кратностей вершин в случайном лесе. — Ветвящиеся процессы. Петрозаводск, КФ АН СССР. 1981, с.10— 16.

16. Калугин И.Б. Предельные теоремы для некоторых классов случайных отображений : Дисс. на соискание уч. степени канд. физ.-мат. наук. М., МИЭМ, 1984.

17. Калугин И.Б. Один класс случайных отображений. — Вероятностные задачи дискретной математики (Труды МИАН СССР), 1986, т. 177, с.75—104.

18. Колчин В.Ф. Ветвящиеся процессы, случайные деревья и обобщенная схема размещения. — Математические заметки, 1977, т.21, вып.5, с.691-705.

19. Колчин В.Ф. Момент вырождения ветвящегося процесса и высота случайного дерева. — Математические заметки, 1978, т.24, вып.6, с.859 —870.

20. Колчин В.Ф. Ветвящиеся процессы и случайные деревья. — Вопр. кибернетики. Комбинаторный анализ и теория графов. М., 1980, с.85 — 97.

21. Колчин В.Ф. Случайные отображения. М., Наука, 1984.

22. Колчин В.Ф. О поведении случайного графа вблизи критической точки. — Теория вероятностей и ее применения, 1986, т.31, вып.З, с.503 — 515.

23. Колчин В.Ф. Системы случайных уравнений. М., МИЭМ, 1988.

24. Колчин В.Ф., Севастьянов Б.А., Чистяков В.П. Случайные размещения. М., Наука, 1976.

25. Маркушевич А.И. Теория аналитических функций. М., Гостехиз-дат,1950.

26. Матула Д.В. Методы теории графов в алгоритмах кластерного анализа. В кн.: Классификация и кластер. М., Мир, 1980, с.83— 111.

27. Мухин A.B. Локальные предельные теоремы для решетчатых случайных величин. — Теория вероятностей и ее применения, 1991, т.36, вып.4, с.660 —674.

28. Павлов Ю.А. Предельные теоремы для числа деревьев заданного объема в случайном лесе. — Математический сборник. 1977, т. 103, вып.З, с.392 —403.

29. Павлов Ю.А. Асимптотическое распределение максимального объема дерева в случайном лесе. — Теория вероятностей и ее применения, 1977, т.22, вып.З, с.523-533.

30. Павлов ЮЛ. Предельные теоремы для некоторых случайных графов. Дисс. на соискание уч. степени канд. физ.-мат. наук. М.МИАН СССР, 1978.

31. Павлов ЮЛ. Один случай предельного распределения максимального объема дерева в случайном лесе. — Математические заметки, 1979, т.25, вып.5, с.751-760.

32. Павлов ЮЛ. Случайный лес и одна задача о ветвящихся процессах.- Математические вопросы моделирования сложных объектов. Петрозаводск, КФ АН СССР, 1979, с.41 -48.

33. Павлов ЮЛ. Предельные распределения высоты случайного леса. — Теория вероятностей и ее применения, 1983, т.28, вып.З, с.449 —457.

34. Павлов ЮЛ. О распределениях числа вершин в соях случайного леса.Теория вероятностей и ее применения, 1988, т.ЗЗ, вып.1, с.105 — 114.

35. Павлов ЮЛ. Некоторые свойства плоских деревьев с висячим корнем. — Тез. докл. Всесоюз. школы "Дискретная математика и ее применения при моделировании сложных систем". Иркутск, 1991, с. 14.

36. Павлов ЮЛ. Некоторые свойства плоских деревьев с висячим корнем. — Дискретная математика, 1992, т.4, вып.2, с.61—65.

37. Павлов ЮЛ. О случайных деревьях. — Труды Петрозаводского ун-та. Сер. математика. 1993, вып.1, с.47 —53.

38. Павлов ЮЛ. Предельные распределения высоты случайного леса из плоских корневых деревьев. — Дискретная математика, 1994, т.6, вып.1, с.137 —154.

39. Павлов ЮЛ. Асимптотическое поведение высоты случайного леса. — Сборник трудов Отдела математики и анализа данных КарНЦ РАН. 1994, вып. 1, с.4-17.

40. Павлов ЮЛ. Предельные распределения максимального объема дерева в случайном лесе. — Дискретная математика, 1995, т.7, вып.З, с.19 —32.

41. Павлов ЮЛ. Предельные распределения числа деревьев заданного объема в случайном лесе. — Дискретная математика, 1996, т.8, вып.2, с.31-47.

42. Павлов ЮЛ. Случайные леса. Петрозаводск, КарНЦ РАН, 1996.

43. Павлов ЮЛ., Чеплюкова ИЛ. Предельные распределения числа вершин в слоях просто генерируемого леса. — Дискретная математика, 1999, т. 11, вып. 1, с.97— 112.

44. Петров В.В. Сумма независимых случайных величин. М., Наука, 1972.

45. Пойа Д. Комбинаторные вычисления для групп, графов и химических соединений. — Перечислительные задачи комбинаторного анализа. М., Мир, 1979, с.36— 138.

46. Сачков В.Н. Комбинаторные методы дискретной математики. М., Наука, 1977.

47. Сачков В.Н. Вероятностные методы в комбинаторном анализе. М., Наука, 1978.

48. Севастьянов Б.А. Ветвящиеся процессы. М., Наука, 1971.

49. Степанов В.Е. О распределении числа вершин в слоях случайного дерева. — Теория вероятностей и ее применения, 1969, т. 14, вып.1, с.64-77.

50. Степанов В.Е. Предельные распределения некоторых характеристик случайных отображений. — Теория вероятностей и ее применения, 1969, т. 14, вып.4, с.639 —653.

51. Степанов В.Е. О некоторых особенностях строения случайного графа вблизи критической точки. — Теория вероятностей и ее применения, 1987, т.32, вып.4, с.633-657.

52. Чеплюкова ИЛ. О распределении числа деревьев заданного объема в случайном плоском лесе. — Статистический анализ нелинейных систем. ПетрГУ. 1996, с.48-55.

53. Чеплюкова ИЛ. Предельные распределения наибольших деревьев в случайном лесе. — Труды Петрозаводского ун-та. Сер. математика. 1997, вып.4, с.130—138.

54. Чеплюкова ИЛ. Предельные распределения числа вершин в слоях случайного леса. — Дискретная математика, 1997, т.9, вып.4, с. 150 — 157.

55. Чеплюкова ИЛ. Возникновение гигантского дерева в случайном лесе. — Дискретная математика, 1998, т.10, вып.1, с.111 — 126.

56. Athreya К.В., Ney P.Е. Branching Processes. Springer, Berlin, 1972.

57. Bollobas В. Random graphs. London, Academic Press, 1985.

58. Cheplykova I.A., Pavlov Yu.L. Random simply generated forests. 7th Vilnius Conf. on Probab. Theory. 1998, p. 177.

59. Egorova I.A. The distribution of vertices in strata of plane planted forest. In: Probabilitic Methods in Discrete Mathematics : Proc. 4th Inter. Petrozavodsk Conf. VSP, Utrecht, 1997, pp.179-188.

60. Kennedy D.P. The Galton-Watson process conditioned on the total progeny. J.Appl, Prob.1975, vol.12, issue 4, pp.800-806.

61. Le Gall. Branching Processes, Random Trees and Superprocesses. Proc. Math. J. PMV, Extra Volume ICM, 1998. Ill, pp.279-289.

62. Luczak Т., Pittel B. Components of Random Forests. Combinatorics, Probability and Computing. 1992, vol.1, pp.35 —52.

63. Lyons R., Peres Y. Probability on the trees and networks. Book in prera-ration, available at http : // php. indiana. edu/' rd/yons/prbtree/prbtree. html.

64. Mahmoud H.M. Evolution of Random Search Trees. New York, Wiley, 1992.

65. Meir A., Moon J. W. On the altitude of nodes in random trees. Canad. J. Math. 1978, vol.30, issue 5, pp.997-1015.

66. Palmer E.M. Graphical evolution : An introduction to the theory of random graphs. New York, Wiley. 1985.

67. Pavlov Yu. L. On the distribution of the number of vertices in strata of a random forest. — Тезисы первого всемирного конгр. общ — ва математической статистики и теории вероятностей им.Бернулли. Ташкент, 1986, т.II, с.496.

68. Pavlov Yu.L. On the distribution of the number of vertices in strata of a random forest. In : Proc. 1st World Congress Bernoulli Soc., v.l : Probability and Applications. Utrecht, VNU Science Press, 1987, pp.239-241.

69. Pavlov Yu.L Random Forests. Utrecht, VSP, 2000.