Предельные теоремы для лесов Гальтона — Ватсона

Вероятностные методы широко применяются для решения комбинаторных задач (см., например, [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—65 «Исследование случайных лесов». В 2000 г. автор является одним из исполнителей гранта РФФИ 00 — 01 —233 «Вероятности на деревьях и лесах» и победителем конкурса персональных грантов для аспирантов, проведенного Администрацией Санкт-Петербурга, Министерством образования РФ и РАН при участии Федеральной целевой программы «Государственная поддержка интеграции высшей школы и фундаментальной науки на 1997 — 2000 годы» (ФЦП «Интеграция»).

Результаты диссертации были получены в ходе проработки темы «Вероятностные и алгебраические методы исследования дискретных объектов», входящих в план научно — исследовательских работ Института прикладных математических исследований Карельского научного центра РАН (№ гос. регистрации 01.9.60 0 12 636) и выполняющейся совместно с кафедрой алгебры и теории вероятностей математического факультета Петрозаводского университета в рамках проекта «Интеграция высшего образования и фундаментальной науки Республики Карелия» ФЦП «Интеграция» (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.