Случайные леса тема автореферата и диссертации по математике, 01.01.05 ВАК РФ

од

РОССИЙСКАЯ АКАДЕМИЯ ПАУК КАРЕЛЬСКИЙ НАУЧНЫЙ ЦЕНТР ОТДЕЛ МАТЕМАТИКИ И АНАЛИЗА ДЛИМЫХ

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

ПАВЛОВ Юрий Леонидович

СЛУЧАЙНЫЕ ЛЕСА

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора физико-математических наук

Петрозаводск 1996

Работа выполнена к Отделе математики и анализа данных Карельского научного центра РАН

Офнцл ал ы Iые оппоненты:

чл.-корр. РАН, д.ф.-м.н., профессор СЕВАСТЬЯНОВ Б.А.

Ведущая организация: Московский государственный институт

ауд. 685 второго учебного корпуса МГУ на заседании Специализированного совета Д 053.05.38 при МГУ пм. М. В. Ломоносова (119899, ГСП-3, Москва, В-234, Воробьевы горы, МГУ, факультет ВМиК).

С диссертацией можно ознакомиться в библиотеке факультета вычислительной математики п кибернетики МГУ.

Автореферат разослан /Он > 1996 г.

д.ф.-м.н., п рофессор д.ф.-м.н., профессор

ГРУШО А.А. САЧКОВ В.Н.

ллекгроники и математики

Защита состоится

1996 г. в И часов в

Ученый секретарь Специализированного совета, профессор

Трифонов Н.П.

ОБЩАЯ ХАРАКТЕРИСТИКА ДИССЕРТАЦИОННОЙ РАБОТЫ

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

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

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

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

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

- з -

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

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

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

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

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

Публикация и апробация работы. По теме диссертации опубликована 31 работа, в том числе монография "Случайные леса". Результаты докладывались на Международном конгрессе математиков (Варшава, 1983), на Петрозаводских конференциях "Вероятностные методы дискретной математики" (1983, 1988, 1992), на Международных Вильнюсских конференциях по теории вероятностей и математической статистике (1985, 1989), на Первом Всемирном конгрессе общества математической статистики и теории вероятностей им.Бернулли (Ташкент, 1986), на Международных семинарах по случайным графам (Познань, 1987, 1989), на Шестой летней школе по теории вероятностей и математической статистике (Варна, 1988), на Всесоюзной школе "Дискретная математика и ее применение при моделировании сложных систем" (Иркутск, 1991), на семинаре "Вероятностные методы в дискретной математике" в Математическом институте РАН им.В.А.Стеклова.

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

Диссертация имеет 286 стр. машинописного текста и состоит из введения, пяти глав и списка литературы, содержащего 105 названий.

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

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

В §1.1 определены используемые в диссертации понятия теории графов. Лесом называется граф без циклов. Деревом называется связный граф без циклов. Корневым деревом называется дерево с выделенной вершиной, называемой корнем-. В диссертации рассматриваются леса, состоящие из N корневых ориентированных деревьев, дуги которых направлены от корней. Кратностью вершины дерева называется число выходящих из нее дуг. Вершила леса имеет высоту если путь от корня в эту вершину содержит £ дуг. Множество вершин леса, имеющих высоту Ь, называется £-м слоем леса. Высотой дерева называется максимальная высота входящих в это дерево вершин. Высотой леса называется максимальная высота составляющих лес деревьев. Объемом дерева называется число содержащихся в нем вершин. Корневое дерево называется деревом с висячим■ корнем, если кратность корня равна единице. Непомеченным «-вершинным

- б -

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

Пример 1.1. Пусть п — множество всех различных лесов с N корневыми и п некорневыми вершинами, в которых корни занумерованы числами от 1 до N, а некорневые вершины — — числами от 1 до п.

Пример 1.2. Множество состоящее из тех

элементов множества у которых кратности вершин леса

принимают значения только из множества И, где К — некоторое непустое множество целых неотрицательных чисел, содержащее нуль.

Пример 1.3. Множество ,!?у п всех различных лесов, состоящих из /V посаженных деревьев и содержащих п некорневых вершин, корни занумерованы числами от 1 до N.

Пример 1.4. Множество 5дгп(Ю, состоящее, по аналогии с примером 1.2, из элементов множества <?дг п, у которых кратности вершин леса принимают значения только из множества Я.

Доказано, что число различных лесов в

п равно

N гп ТППг 2и+ЛМ'

В §1.2 вводится понятие случайного леса как частного случая случайного элемента. Пусть 3 — множество лесов некоторого класса, на котором задана вероятностная мера Р. Случайный лес Р есть тождественное преобразование множества

■У в себя такое, что Р{Г = [) = Р{0 для любого /Ч.У. Приводится описание введенной В.Ф.Колчиным обобщенной схемы размещения частиц по ячейкам и показывается, что задачи о случайных лесах, определенных на множествах Ук,п< З^к^Ю-•Т'ы 72. ,);(/?) могут рассматриваться в рамках этой схемы.

Основное содержание §1.3 состоит в установлении связи между классами случайных лесов, определенных на множествах •¥'к,п> с заданным на них равномерным

распределением вероятностей и ветвящимися процессами Гальто-на— Ватсона, начинающимися с N частиц.

Пусть означает случайную величину, равную числу

вершин кратности у из ¿-го слоя леса ( Классу лесов

ставится в соответствии ветвящийся процесс С, в котором число прямых потомков одной частицы имеет распределение Пуассона. Обозначим цг{Ь,С) число частиц ¿-го поколения процесса С, имевших ровно г потомков и пусть v(G') означает число частиц, существовавших за все время эволюции процесса С/. Введем также матрицы И/гД^.С')!!, £, г = 0,

1 ,...,п и матрицу М= П^/ДОИ такого же размера, составленную из целых неотрицательных чисел.

Лемма 1.3.1. Справедливо равенство

Эта лемма является обобщением на случай Л^>1 соответствующего результата В.Ф.Колчина для случайных деревьев. Аналогичный результат для был получен И.Б.Калугиным, при этом распределение числа потомков одной частицы ветвящегося процесса получается пз распределения Пуассона, если оно сосредоточено на множестве Л. Утверждения, подобные лемме 1.3.1, доказаны в §1.3 и для множеств и ПРИ этом число потомков одной частицы соответствующих ветвящихся процессов имеет геометрическое распределение или получающее-

ся из него переносом на множество

Рассмотрим класс лесов п с N корневыми деревьями и п некорневыми вершинами и ветвящийся процесс Гальтона — Ватсона, начинающийся с N частиц и предположим, что выполняется соотношение

Р{11/40(/)И=М} = Щ\\цгШ\\=М\у = Ы + п), (1.3.1)

где — число вершин кратности г в слое t леса ^ €

6 '?К',п> Iчг(0 — число частиц ¿-го поколения процесса С, имевших г прямых потомков, V — число частиц, существовавших в С до его вырождения. Из леммы 1.3.1 и аналогичных ей следует, что для классов лесов п> с равномерным распределением вероятностей условие (1.3.1) выполняется. Соотношение (1.3.1) покалывает, что изучение характеристик случайного леса, являющихся функциями случайных величин можно свести к изучению условных распределений соответствующих характеристик ветвящегося процесса в при условии v = ^V + ?г.

Рассмотрим, например, высоту леса т. Пусть /¿(О означает число частиц £-го поколения процесса С.

Л е м м а 1.3.2. Справедливо равенство

Р{т<£} = 1 - Р{р(О>0}Р{у=М + и | /и(О>0} /Р{у = Ы + п).

Для доказательства некоторых результатов о высоте случайного леса иногда удобнее представить вероятность Р{г < () иначе. Ветвящийся процесс С естественным образом разбивается на N процессов \,.,, начинающихся с одной частицы.

Обозначим г/1 .....г^^ случайные величины, равные числу

(1)

частиц, существовавших, соответственно, в процессах в4 ,

..., О*-^ до их вырождения. Обозначим также .....

независимые одинаково распределенные случайные вели-

чины такие, что

+ !/<">( О.

где к = 1,2,.,

Р{у{1)Ц) = к) = = ц{ОШ = 0},

.,.; г' = 1.....N. Пусть = ^(1)(0 + ... +

Лемма 1.3.3. Справедливо равенство

Р{т<0 = Р{/г(£) = 0} Р{£ д,^ = Ы + «}/Р{г = Ы + п}.

Целью §1.4 является описание класса рассматриваемых в диссертации случайных лесов. Пусть С — ветвящийся процесс Гальтона —Ватсона, начинающийся с N частиц, у которого распределение числа потомков одной частицы имеет производящую функцию

Установлено взаимно однозначное соответствие (5 между множеством траекторий процесса в и множеством лесов, состоящих из N посаженных деревьев, это соответствие является обобщением на случай N> 1 исследованной В.А.Ватутиным связи между начинающимся с одной частицы ветвящимся процессом и множеством всех плоских деревьев с висячим корнем. Если конкретной реализации процесса в отображение <5 ставит в соответствие лес (, то это обстоятельство будем записывать так: С = /. Пусть Р — вероятностная мера на множестве всех подмножеств траекторий процесса б, порождаемая распределением с производящей функцией (1.4.1). Пусть {Од/ п) — множество всех реализаций процесса С, содержащих N + п частиц, а V ~ число частиц, существовавших в процессе в до его вырождения. Если число потомков одной частицы имеет геометрическое распреде-

оо

(1.4.1)

к=О

ление. то процесс С при помощи соответствия д порождает равномерное распределение на и справедливо равенство

где |<ХСдг и)| = 1 — число лесов из .Удг,«' соответствующих Сдг)Н при отображении <3, а £,(<5({Сдг м})) — число образов всех лесов при этом отображении.

Рассмотрим множество лесов Если число потомков од-

ной частицы процесса С имеет распределение Пуассона, то на множестве .Уд' м индуцируется равномерное распределение и

Р<0=Сл,,м| * = * + = ГШ^^П, (1-4.3)

где |Д(Од/>н)| — число лесов из .Удг ^, соответствующих Од- „ при отображении ¿У. {Одг>п}—1- а £(А({Сдг;г})) — общее чис-

ло лесов в Соотношения, аналогичные (1.4.2) и (1.4.3),

нетрудно установить также и для множеств <УдгпО?), «(/?)• Опишем класс лесов, рассматриваемых в диссертации. Пусть ~ множество лесов, состоящих из /*/ корневых деревьев (корни занумерованы) с п некорневыми вершинами, помеченными некоторым способом, то есть ^ п е Обозначим через

Л.уСОд/ ,г) класс лесов, образованный из Д(Одг путем удаления лесов, не принадлежащих .Удг)П, и вместо отображения А будем рассматривать отображение А^: {Сд/ ,,} .Уд',»- В следующих главах изучается такое множество лесов 5дг я, для которого выполняется соотношение

Р{С=Сд,,г^ = Л^} = , (1.4.4)

где I А^ССдги) | — число лесов в множестве Л_у(Одгм), а

¿(А_у({Сдг,]})) — общее число лесов в

Для изучения различных числовых характеристик лесов из используется следующая лемма. Пусть р = (р(Одги) — некоторая числовая характеристика леса Одг)?г- Если лес /е.?дг1П1 содерлштся в множестве Д9г(Сдгп), то положим

= = <р(Ом<п).

Таким образом, случайная величина принимает одно и то же значение на всех элементах класса Лу^дт и). Наиболее известными примерами так определяемых случайных величин являются максимальный объем дерева в лесе, число деревьев заданного объема, высота леса, число вершин заданной кратности, число вершин заданной высоты.

Лемма 1.4.1. Справедливо равенство

Р{у?д = д:} = Р{у>-х | V = Ы + п).

Ясно, что (1.4.2) и (1.4.3) являются частными случаями (1.4.4). Кроме того, из (1.4.4) вытекает справедливость соотношения (1.3.1), поэтому для справедливы леммы 1.3.2 и 1.3.3.

Кроме соотношения (1.4.4) мы введем также некоторые ограничения на распределения числа прямых потомков одной частицы процесса С. Пусть £ — вспомогательная случайная величина имеющая распределение, задаваемое производящей функцией (1.4.1). Предположим, что это распределение имеет максимальный шаг (I, а множество значений имеющих ненулевую вероятность, содержит нуль и не совпадает с {0, 1}. Для положительных X таких, для которых определены F(/D, введем начинающийся с N частиц ветвящийся процесс Гальюна — Ватсона, в котором число потомков одной частицы имеет распределение

рка) = Д^/ЯА), к = 0,1,2,

(1.4.5)

В следующих главах диссертации рассматривается класс лесов п, связанный соотношением (1.4.4) с ветвящимся процессом С, в котором число прямых потомков одной частицы имеет распределение (1.4.5), при этом ^"'(1) <

В главах 2-4 доказаны предельные теоремы для важнейших числовых характеристик случайных лесов: максимального объема дерева, числа деревьев заданного объема, высоты. В первых параграфах этих глав описывается постановка задач и формулируются полученные результаты. В следующих параграфах доказываются вспомогательные утверждения, необходимые для получения основных теорем. Как правило, это локальные предельные теоремы для схем серий независимых решетчатых слагаемых (§§2.3, 2.4, 2.5, 3.2, 3.3, 4.2), в том числе для случая сколь угодно больших уклонений (§§2.5, 3.3). В последних параграфах приводятся доказательства основных теорем, а также некоторые результаты, дополняющие содержание глав.

Во второй главе получены предельные распределения максимального объема дерева в случайном лесе при различном характере стремления N и и к бесконечности. В §2.1 введены вспомогательные независимые одинаково распределенные случайные величины у^.....для которых

= = = 1}, к = 0,1, 2.....

где случайные величины ¿=1.....Ы, как и в §1.3,

равны числу частиц, существовавших в процессах С^. Обозначим также V = /^-К .. + гг = . . +

+ Рг = г +1}. Пусть 1} означает максимальный

объем дерева в лесе из п.

Лемма 2.1.1. При п таких, что Р{г> = N + п}> 0

рь,<и - (1 -р Р{г>=ЛГ+/'}

С помощью леммы 2.1.1 но второй главе доказаны следующие результаты.

Обозначим j наименьшее целое положительное число такое, что pj > 0, а /—наименьшее натуральное, не кратное / и удовлетворяющее условию pj+i> 0; если такого / не существует, положим 1 = 0.

Теорема 2.1.1. Пусть N, п —» °о так, что п пробегает значения, кратные d, n/N —* 0, а параметр X = X(N,n) определяется соотношением

А/\Ш _ п о 1 1 ч

Я А) ~~ ЪГ+Тг- U.l.U

Пусть jVP{v(i) = /-+1} —► оо, /VP{v(1) = r+s+ 1} — у, где у — некоторая неотрицательная постоянная, а натуральные г и .s кратны cl и удовлетворяют одному из условии:

1) г■ — оо, л = d;

2) /' фиксировано, rzj+l, = г+ .v+1} > 0,

= + = 0, где 0<i<s.

Тогда

Р{г/=г+1} — е'у, V{q = r + s + \) — 1-<?"г.

Теорема 2.1.2. Пусть N, п — ос так, что и пробегает значения, кратные d и n/JV —* Ь, где b — некоторая положительная постоянная. Пусть l = X(N.n) определяется соотношением (2.1.1), а = / FiA^))^, где А/, — решение уравнения AF'{A)/F(X) = b/(b+l). Если r-r(N, п) пробегает значения, кратные d и такие, что

N TU7

Л

то

где у — положительная постоянная, то для к = 0, ±1, ±2,...

Р{?/«г + Ы+1} — ехр{~уакп (1-я)"1}.

Теорема 2.1.3. Пусть N, п — оо так, что п пробегает значения, кратные d, n/N —- оо, я/N2 —*• 0. Пусть А = = А(Л/, и) определяется соотношением (2.1.1). Тогда

Р{fitj-u^z} — е~''\

где

fi = jSCA) = -1п(Я/ЯЯ)), (2.1.2)

а м = и(А) выбрано так, что

Np\;2u-3/2e-u = ^2жВ

Т е о р е м а 2.1.4. Пусть N, п -бегает значения, кратные d, В n/N2 положительная постоянная. Тогда

оо

Р{tj/ntz} - у3/2ехр{1/(2у)} £ <~l)fe (И )"*/*(}*, у),

k=Q

где

/0(и, f) = (а3ехр{1/и})"|/2,

/ (îî g) Г ' /(2(и~л'1 -..xfc))}dx\.. .dxfc

'' U'V ~ XkL,v) (2n)k/2(xi...xk(v-xl-...-xk))3/2 '

Xkiu, v) = {x{ïii, i = 1,., ., k, x\ +.. , + Xk^v}, /¡ = 1,2,... T e о p e m a 2.1.5. Пусть н — оо так, что п пробегает

(2.1.3)

оо так, что п про-— у, где у — некоторая

значения, кратные d, n/N ного положительного z

оо. Тогда для любого фиксирован-

^В

N*

* z

{2я о

Jy3/2 ехр{— 1/ (2г/)} dy.

В §2.2 рассматривается предельное поведение выражения NPr. Полученные результаты полностью характеризуют асимптотику бинома (1 содержащегося в правой части утверждения леммы 2.1.1.

В § 2.3 получены предельные выражения для вероятности = Обозначим через т и В\ соответственно матема-

тическое ожидание и дисперсию распределения (1.4.5). Справедливы равенства

а = Mv(l) = 1/(1 -т),

'1 _

Dv(0 = 5^/(1-яг)3,

а если Я = A(N,n) определяется соотношением (2.1.1), то т = = n/{N + n).

2

JI е м м а 2.3.1. Пусть N, п — оо так, что n/N —► О, Nti+l —>■ оо, где Я = Я(N, п) определяется соотношением (2.1.1). Тогда для целых неотрицательных h, кратных d, равномерно относительно (h-rd/io^ в любом конечном интер-

вале

V{v = N + h) = dÜ + oil)) ехр а 2лЫ

_(h-nY

2 o2N

Лемма 2.3.2. Пусть N-—00, Я =1. Тогда для натуральных к, кратных й, равномерно относительно г= (Ы + ЮВ* xN^2 в любом конечном интервале

Вл N2P{Bv/N2 = z) = d(2nz3y]/2exp{- 1/(2г)}(1 +o(l».

Лемма 2.3.3. Пусть N— оо, А=1. Тогда для натуральных к, кратных d, при z=B{N + А)

Вл N2P{Bv/N2=z) = d(27tz3Yl/2 (1 + 0(1)).

В §2.4 получено предельное распределение вероятности

P{vr = N + и}, стоящей в правой части утверждения леммы

2

2.1.1 при N,n—*oc> так, что n/N -»0.

Лемма 2.4.1. Пусть N,n-~°o, н/ЛГ2 — 0, А = Л(Л/» определяется соотношением (2.1.1), а r = r(N,n) пробегает значения, кратные d, так, что МРГ —* у, где у — некоторая положительная постоянная. Пусть, кроме того, —* 00.

Тогда для целых неотрицательных /2, кратных d. равномерно относительно (h~ 11)/{(r\N) в любом конечном интервале

P{vr = N + A} = ехр

fffÜbrA/

(А-н)2|

2(7",V

В §2.5 изучено предельное поведение в области п/Ы2 » > С > 0 в случае А = 1.

Лемма 2.5.1. Пусть Ы,п—*оо так, что Вп/Ы^-^-у, где у —- некоторая положительная постоянная. Пусть и=(М + к)х хВ/Ыгде к — натуральное число, кратное (/. Если г кратно г/ и г = 2«+О(0, где г — фиксированное положительное число, то равномерно относительно а, 0<ид«о =?£»!, для любых конечных

где

E(u,z) = (2хУ,/2 ¡y3/2eiuiJdy, yz

а интегралы I kin, v), k =0,1,... определены в формулировке теоремы 2.1.4.

Лемма 2.5.2. Пусть я —► оо так, что n/N^ —•■<», г 1 *)

кратно d и r = n~zB~ N , где г — фиксированное положительное число. Тогда для п таких, что Р{гг = Л/ + я}>0

со

P{vr = JV + «} = -Г(/еХр{\/y}ri/2dy(\+o(\)).

2xnJ/2iB J2

В §2.6 с помощью леммы 2.1.1 и результатов §§2.2-2.5 доказаны теоремы 2.1.1-2.1.5. Установлены также некоторые достаточные условия существования последовательности значений r~r(N,n), удовлетворяющие условиям теоремы 2.1.1.

Третья глава посвящена изучению предельного поведения числа деревьев заданного объема в случайном лесе при всех

соотношениях между стремящимися к бесконечности ЛГ, п. В §3.1

(1)

введены вспомогательные независимые случайные величины ... , Т(^), имеющие распределение

p{v(r> = ^ = p{v(0 = /i | v(i)*r+1}, k = \,2.....

где i = \,... , N, г = 0, \п. Обозначим число де-

ревьев леса из содержащих г некорневых вершин.

Лемма 3.1.1. Для любого X, 0 < X ^ 1, и п таких, что P{v = N + п) > 0, справедливо равенство

где г/,(А) = P{^>=,+ t}, = v{l]+... + v{»f.

Пусть параметр Л = Л(Л', н) определяется соотношением (2.1.1). Справедливы следующие результаты.

Т е о р е м а 3.1.1. Пусть N,ti — <х> так, что n/N —* О, — оо и п кратны d. Тогда при г > 2 и >' * j для целых неотрицательных к

РUh=k} = ^ (Nqra))kexp{-NqrW} (1+о(1)) равномерно относительно

в любом конечном интервале.

'Г е о р е м а 3.1.2. Пусть А/, н — оо так, что n/N?C> >0, и кратны d,

Orr = qM)(\-qr{X)~U'r:{)2qr(X)).

а

Тогда для целых неотрицательных к равномерно относительно иг

в любом конечном интервале

Р{fir = k) = {on{2lNrX си2'/2 (1+о(1)>.

При величины qr{А) и ajr можно заменить соот-

ветственно на <7Г(1) и qr(0 (1 - qr(l)).

Обозначим через s наименьшее натуральное такое, что Pj+S > 0, если такого л" нет, то полоясим s=0. Таким образом, .V отличается от I тем, что может быть кратным /.

Теорема 3.1.3. Пусть N, п —- оо так, что n/N —■ —► 0, п пробегает значения, кратные d и min —»оо, где

ю{ 0) = 2j + l;

<w(l) = 3 при j- 1;

<w(l) = max (2/,7+/) при j> 1;

<w(r) = /+/ при гъ 2, r* J;

w(r) = max{min(2},j+s),j + l) при 2.

Тогда справедливо утверждение теоремы 3.1.2.

Теорема 3.1.4. Пусть N,n,r —■ °° так, что NA? — —* оо. Тогда для целых неотрицательных k равномерно относительно (к- Nqr(X))Nqr{X) в любом конечном интервале

Рifir=k) = £г (Nqr(k))^ ехр{~ Nqr(X)} (1 +о(1)).

При ti/N2zC>0 величины qr(Ä) можно заменить на qr(l).

( г)

В §3.2 получено предельное распределение суммы Сдг-fe ПРИ

2 (1)2 N, п —► оо так, что n/N — 0. Обозначим ar = Mv^, аг =

О)

Лемма 3.2.1. Пусть N, п —* оо так, что n/N —► О, я/W > С > 0. Тогда при 5 = ЛГ(1 -qr{X)) (1 + о(1)> для целых неотрицательных h, кратных d, равномерно относительно иг =

в любом конечном интервале

Р{4г) = ЛГ+/г} = (/((гг{2^7)"1ехр{-г^/2}(1 + о(1)>.

Это утверждение остается в силе и при г—* оо.

Лемма 3.2.2. Пусть N, п оа так, что n/N —» О, —►«>, где fti(r) определено в формулировке теоремы 3.1.3. Тогда при 5 = N{\-qr(X)) (1 +о(1)) справедливо ут-верлсдение леммы 3.2.1.

В §3.3 рассматривается сумма в критическом случае,

возникающем при А=1.

Лемма 3.3.1. Пусть N — оо, 5 = N (I - i/r(l» (1 + + о(1)), z = (N + n)BN'2, где п — натуральное число, крат-

ное d. Тогда равномерно относительно г, 0<го«г$г1<с»

ВлЫ2ЩВ^/Ы2 = г) = й(2л:г3е1/2)",/2(1+о(1)).

Это равенство справедливо и при у—»со.

Лемма 3.3.2. Пусть N — оо, 5" = ЛГ(1 -c?r(l)> (1 + + о( 1)), z = B {N + ii)N~^ — оо, где к — натуральное число, кратное d. Тогда

ВЛ JV2P{ß^r)/Nl = z) = </(2лг3)",/2(1 + о(1)).

Это равенство справедливо и при г—► оо.

Доказательства теорем 3.1.1-3.1.4 приведены в §3.4, при этом используются лемма 3.1.1 и результаты §§2.3, 3.2, 3.3. Далее, в §3.4, приведены некоторые дополнения о предельном поведении случайной величины /ir(,T'), равной числу деревьев объема г в случайном лесе, определенном на множестве .?дг,«-

В четвертой главе получены предельные распределения высоты случайного леса т, соответствующие теоремы сформулированы в §4.1.

Теорема 4.1.1. Пусть N, п — оэ так, что n/N — — О, и /Л/ —► оо, -—а t = t{N,7i) выбрано так, что

NrrS —» оо, Nmt+1 ограничено. Тогда

Р{т = £} = exp{-W+1} + o(l>,

P{r = i+1} = 1-exp{-Nwi+1}+o(l).

Обозначим [-¿(z) производящую функцию распределения (1.4.5). Пусть для целых положительных г выражение F)r(z) означает г — кратную итерацию функции F^(z), следовательно Р^(г) =FA(2), F^2(z) = Fa(F^)), Fp(2) = FA(FA(F2(z))), ... Теорема 4.1.2. Пусть N, п — <х> так, что п пробегает значения, кратные d, n/N — b, а t = t(N,n) выбрано так,

что Ип/ —» /б, где Ь, (5 — некоторые положительные постоянные. Тогда

Р{г <£+£} — ехр{-К/3 (6/(1-ьЬ))*}, где & = 0,±1, ±2.....

Х-Пш1-^;«». (4.1.1)

г—°о т

Теорема 4.1.3. Пусть N. п —■ °° так, что п пробегает значения, кратные (/, п/Ы—»оо, 0. Тогда для любого фиксированного .г

Р{т1п(1+ЛГ/и)-1П(2ЛГ2/Ш«))<Х} —

Теорема 4.1.4. Пусть N,п °° так, что и пробегает значения, кратные с1, М/\Вп —- г. Тогда равномерно относительно г в области 0 <оо для любого фиксированного х>0

2

Р{(б/и)1/2г«л} — ег/2(2|2л)"1 | ехр{-г'и-г/(х, «)/*}</«,

где

/"(.*,«) = -Н~2гц(1 +ехр{-^'|-2пг)) (4 1 2)

1 -ехр{~.хт)- 2ш)

Теорема 4.1.5. Пусть п — оо и пробегает значения, кратные (1, п/Ы2 —-оо. Тогда для любого фиксированного х> О

Р{(В/пУ/2х*х] — ][ (1-к2х2)ехр{~к2х2/2\.

В §4.2 рассматривается предельное поведение вероятностей Р{/г(О = 0} и -Ы + п), входящих в правую часть ут-

верждения леммы 1.3.3, в докритическом случае Я<1.

Л е м м а 4.2.1. При N ^ °° справедливы следующие утверждения.

1. Если 0<ш<С<1, а Ь = £(А) выбрано так, что — —где /3 — некоторая неотрицательная постоянная, то

Р{МО=0} = +

где постоянная К определена равенством (4.1.1), причем К= 1 при т—> 0.

2. Если /и — 1, А/( 1 -д?/) -> оо,

£ = (-*-Нп(Вя/(2Л/-(1-»г))))/1п/и+0(1), где х — произвольная постоянная, то

Р{/г(0 = 0} = бГр +о(1).

2

Л с м м а 4.2.2. Пусть N, исю так, что h/N —О, —* оо, а t= t{M, п) выбрано так, что

> 0} ^C'i <°°. Тогда для целых неотрицательных А, кратных d, равномерно относительно (h - п)/(ff {77) в любом конечном интервале

= cid+ 0(1)) СХР1

(Гi 2ж\>

.(А-и)2

2а2 N

В §4.3 получена асимптотика вероятностей Р{;*(£) > 0} и

Р{т = N + п | /¡(£) >0}, содержащихся и утверждении леммы 1.3.2 в критическом случае Л=1.

Л е м м а 4.3.1. При £ -^оо равномерно относительно целых М таких, что ЛГ/г«С<оо

Р{/*(О>0} = 1-ехр{-2 Ы/Ш)} + о(Н/0.

Лемм а 4.3.2. Пусть п, £ —♦ оо так, что н/Л/2 — со, £(5/н)1//2 —► х, где х — положительная постоянная. Тогда для целых неотрицательных /г, кратных г/, равномерно относительно у = (Л/ + /г)/п в любом конечном интервале

пР{у/п=у | у(О>0} = (1д(у) (1 + о(1)),

где

№ =

* I

к2х2

У

ехр<

,2 2 к х

2 у

у> С.

Л е м м а 4.3.3. Пусть п, ■ оо так, что /V \Вп — г, /п)^"2 — :г, где г, х — положительные постоянные. Тогда для целых неотрицательных /г, кратных (I, равномерно относительно г п у = (Ы + к)/п в любой области вида 0<г/о«//§ «г/1 <оо

х J* <?"ш^(ехр{-г^-2гм} -ехр{- zf(x, u)/x})du,

где функция fix, и) определена равенством (4.1.2).

В §4.4 приведены доказательства теорем 4.1.1-4.1.5, при этом используются леммы 1.3.2, 1.3.3 и результаты §§4.2,

4.3. Установлены некоторые достаточные условия существования указанной в теореме 4.1.1 последовательности значений ¿(/V, п). Кроме того, §4.4 содержит некоторые результаты о случайных лесах, равновероятно определенных на множествах и

<Удг п. В частности, получены предельные распределения высоты

' 2 таких лесов в случае п /И ^ С < оо, а также предельные распределения числа вершин в ¿-м слое леса из при и—-оо и ограниченных значениях Ы/{п, ¿/{и.

В пятой главе результаты о случайных лесах используются для исследования предельного поведения некоторых характеристик случайных отображений при равномерном распределении вероятностей на множестве всех рассматриваемых однозначных отображений «-элементного множества в себя. В §5.1 обсуждается соответствующий метод, основанный на представлении графа отображения как совокупности компонент связности, содержащих ровно один цикл. Такой граф после удаления циклических дуг становится лесом, поэтому для изучения числовых характеристик лесов, входящих в граф отображения, достаточно усреднить результаты, полученные в предыдущих главах, по распределению числа циклических точек. В §5.2 рассматривалась величина /гг(я), равная числу деревьев случайного отображения, содержащих г некорневых вершин. Обозначим = (г + 1 )гх х((г+1)1ег+1)"1, г = 0,1,2,...

Теорема 5.2.1. Пусть п —г=о(?21/3), г = к/{р'г\п), где к — целое положительное число. Тогда

= 2ег1/2{\+о{\)).

В §5.3 рассматриваются однозначные отображения множества из п элементов в себя, граф которых содержит ровно т компонент связности. На множестве всех таких отображений вводится равномерное распределение вероятностей. Пусть и

рг{п,т) равны, соотлетственно, числу циклических вериши и числу деревьев, содержащих г некорневых вершин в графе отображения. Получены предельные распределения А^11'"^ и /.1г(п, т) при п —сю, т/\пп 52}/<оо и всех возможных значениях г. Для доказательства этих результатов было изучено предельное поведение вероятности Р{эега = Л^}, где гп — число циклов в случайной подстановке из множества всех подстановок степени п с равномерным распределением вероятностей. Получена асимптотика этой вероятности (в том числе с оценкой скорости сходимости) при ограниченных значениях Л^/Ьги. Получены также некоторые результаты о графах случайных отображений с ограничениями на кратности вершин.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

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

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

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

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

5. Павлов Ю. Л. Предельные распределения некоторых характеристик случайных отображений с одним циклом. В сб.: Математические вопросы моделирования сложных объектов. Петрозаводск, Карельский филиал АН СССР, 1979, с.48-55.

6. Павлов Ю. Л. Локальная предельная теорема с переменной решеткой для одной характеристики случайного леса. В сб.: Ветвящиеся процессы. Петрозаводск, Карельский филиал АН СССР, 1981, с. 24-29.

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

8. Павлов Ю.Л. Предельные распределения одной ха-

рактеристики случайного отображения. Теория вероятностей и ее применения, 1981, г. 26, вып. 4, с.841--847.

9. Павлов Ю. Л. Предельные теоремы о случайных лесах Тезисы докладов Всесоюзной конференции "Вероятностные методы в дискретной математике". Петрозаводск, Карельский филиал АН СССР, 1983, с. 62-64.

10. Павлов IO. Л. Случайные леса. Short communications (Abstracts). V.8, section 10: Probability and mathematical statistics. International Congress of mathematicians ISM, Warszawa, 1983, p. 56.

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

12. П а в л о в Ю. Л., Сергеева И. IO. Сходимость к предельным распределениям одной характеристики случайного леса. В сб.: Вероятностные задачи прикладной математики. Петрозаводск, ПГУ, 1984, с.48-53.

13. Вероятностные и алгоритмические методы теории графов (заключительный отчет). Петрозаводск, Карельский филиал АН СССР, 1984, N гос. регистрации 81004319.

14. Павлов Ю. Я. О случайных отображениях с ограничениями на число циклов. Труды математического института им. В.А.Стеклова АН СССР, т. 177, 1986, с. 122- 132.

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

16. Pavlov Y. L. On the distribution of the number of vertices in strata of a random forest. Proceedings

of the 1 st. World Congress of the Bernulli Society, v.l. Probability and applications. VNU Science Press. Utrecht, The Netherlands, 1987, p. 239-241.

17. Павлов Ю.Л.О случайных отображениях и лесах. Тезисы докладов II Всесоюзной конференции " Вероятностные методы в дискретной математике". Петрозаводск, 1988, с.77-78.

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

19. Павлов Ю. Л. Случайные отображения с ограничениями на кратности вершин и число компонент. Вероятностные задачи дискретной математики. Межвузовский сборник. М., МИЭМ, 1988, с.63~68.

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

21. Павлов Ю. Л. О плоских деревьях с висячим корнем. В сб.: Вероятностные процессы и их приложения. М., МИЭМ, 1991, с.45-48.

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

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

24. Алгоритмические и вероятностные задачи математического моделирования (заключительный отчет). Петрозаводск, Карельский научный центр РАН, 1992, N гос. рагистрации 01870005360.

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

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

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

28. 3 е м л я ч е н к о В. Н., Павлов Ю. Л. К вопросу о связи ветвящихся процессов и случайных деревьев. Труды Петрозаводского университета. Сер. математика, 1995, вып.2, с.31-43.

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

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

31. Павлов Ю. Л. Предельные распределения максимального объема дерева в случайном лесе. Дискретная математика (в печати).