Леса Гальтона-Ватсона и случайные подстановки тема автореферата и диссертации по математике, 01.01.09 ВАК РФ
|
Казимиров, Николай Игоревич
АВТОР
|
||||
|
кандидата физико-математических наук
УЧЕНАЯ СТЕПЕНЬ
|
||||
|
Петрозаводск
МЕСТО ЗАЩИТЫ
|
||||
|
2003
ГОД ЗАЩИТЫ
|
|
01.01.09
КОД ВАК РФ
|
||
|
|
||||
На правах рукописи
Казимиров Николай Игоревич
ЛЕСА ГАЛЬТОНА-ВАТСОНА И СЛУЧАЙНЫЕ ПОДСТАНОВКИ
01.01.09 — дискретная математика и математическая кибернетика
АВТОРЕФЕРАТ
диссертации на соискание ученой степени кандидата физико-математических наук
Петрозаводск 2003
Работа выполнена в Институте прикладных математических исследований Карельского научного центра РАН.
Научный руководитель: доктор физико-математических наук, профессор Ю. Л. Павлов.
Официальные оппоненты: доктор физико-математических наук, профессор В. Ф. Колчин, доктор физико-математических наук, профессор Е. В. Морозов.
Ведущая организация: Петрозаводский государственный университет.
Защита состоится 19 декабря 2003 г. в 14 часов 15 мин. на заседании диссертационного совета К 002.142.01 в Институте прикладных математических исследований Карельского научного центра РАН по адресу: 185610, Петрозаводск, ул. Пушкинская, 11.
С диссертацией можно ознакомиться в библиотеке Карельского научного центра РАН.
Автореферат разослан
2003 г.
Ученый секретарь диссертационного совета К 002.142.01 к.ф.-м.н., доцент
В. Т. Вдовицын.
\
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы. В настоящее время широкое распространение в комбинаторном анализе получил теоретико-вероятностный подход. Хорошо развитые в теории вероятностей методы асимптотического анализа успешно используются при решении сложных комбинаторных задач. Применение вероятностных методов в решении перечислительных задач комбинаторики связано с заданием вероятностей на множестве изучаемых комбинаторных объектов таким образом, чтобы эти вероятности определяли долю объектов с интересующими нас свойствами. Тогда, используя теоретико-вероятностный аналитический аппарат, можно получить точные или приближенные формулы для числа объектов, обладающих изучаемыми свойствами. Одним из важнейших направлений исследований является изучение предельных свойств комбинаторных объектов, проявляющихся при неограниченном возрастании числа элементов, образующих такие объекты. Значительное внимание в работах по дискретной математике в настоящее время уделяется изучению случайных графов. С помощью обобщенной схемы размещения в этой области математики удается решать множество сложных и полезных в других областях науки задач.
В диссертации рассматриваются собственно обобщенная схема размещения, леса Гальтона—Ватсона и случайные подстановки. Так как к обобщенной схеме размещения сводится большое число задач комбинаторики, она представляет интерес как самостоятельный объект исследования. Случайные деревья, леса и подстановки находят применение в анализе вычислительных алгоритмов, статистических методах, моделировании транспортных и информационных систем, генетике, химии полимеров, криптографии, а также при решении собственно математических задач, например, в теории случайных уравнений и проблеме эволюции случайных графов.
Цель исследования. Целью диссертации является получение новых результатов о предельном поведении важнейших харак-
|>ОС. НАЦИОНАЛЬНАЯ
виммотекл
теристик лесов Гальтона—Ватсона и случайных подстановок с известным числом циклов. В частности, предполагалось, во-первых, снятие ограничения конечности третьего момента распределения числа прямых потомков каждой частицы в ветвящемся ' процессе, генерирующем лес Гальтона—Ватсона, для изучения всех известных характеристик леса, во-вторых, получение пол- < ного спектра теорем, описывающих предельное поведение наибольших длин циклов случайной подстановки с известным числом циклов, в-третьих, выявление условий возникновения гигантского цикла в случайной подстановке.
Для достижения этой цели предполагалось получение общих теорем об обобщенной схеме размещения, охватывающих широкий класс комбинаторных задач, описываемых этой схемой.
Объекты исследования. Объектами изучения в диссертации являются: собственно обобщенная схема размещения, леса Гальтона—Ватсона и случайные подстановки. Обобщенная схема размещения как метод комбинаторного анализа была введена и изучена В. Ф. Колчиным как обобщение задачи о случайном равновероятном размещении п частиц в N ячеек, получившей название классическая схема размещения. Введение обобщенной схемы не только расширяет область использования удобного языка для описания комбинаторных структур, но также дает возможность применять те методы, которые были развиты при анализе классической схемы. В работе изучается предельное поведение объемов компонент обобщенной схемы при достаточно общих ограничениях, позволяющих охватить ряд известных конкретных примеров применения этой схемы размещения.
Леса Гальтона—Ватсона представляют собой случайные леса, соответствующие траекториям ветвящегося процесса Гальтона— '
Ватсона, откуда и происходит это название. Понятие лес Гальтона—Ватсона было введено J. Pitman в 1998 г. В диссертации » рассматривается предельное поведение объемов деревьев, числа деревьев заданного объема и высоты леса Гальтона—Ватсона, состоящего ^з N деревьев и п некорневых вершин.
, ¿¿M-it.M&Lst^f,
1 ' " ' 1 • л f i * / .1
1 Л-.-л.Ч.
<<•> VI.
Случайные подстановки могут быть представлены в виде случайных графов, компонентами связности которых являются ориентированные циклы. Случайный вектор, составленный из длин занумерованных произвольным образом циклов таких случайных графов, можно изучать с помощью обобщенной схемы размещения. Этой же обобщенной схеме размещения соответствует случайный рекурсивный лес. Таким образом результаты о длинах циклов случайной подстановки эквивалентны соответствующим результатам об объемах деревьев случайного рекурсивного леса. В диссертации рассматривается предельное поведение длин циклов случайной подстановки с известным числом циклов.
Методы исследования. Основными методами исследования в диссертации являются обобщенная схема размещения, теория ветвящихся процессов Гальтона—Ватсона и методы получения предельных теорем для сумм независимых решетчатых случайных величин, включая локальную сходимость в схеме серий. Главной трудностью при получении результатов явилось доказательство локальных предельных теорем для таких сумм в схеме серий, а также нахождение асимптотики моментов производящих функций этих сумм.
Научная новизна. В диссертации впервые рассматривается частный случай обобщенной схемы размещения, к которому сводится большое число перечислительных задач комбинаторики. С помощью результатов об обобщенной схеме доказывается ряд теорем о лесах Гальтона—Ватсона и случайных подстановках для не рассматривавшихся ранее характеристик и зон изменения параметров. Все полученные результаты являются новыми.
Основные положения диссертации, выносимые на защиту. На защиту выносятся:
1. Предельные распределения при N оо: а) всех компонент обобщенной схемы размещения п частиц по N ячейкам при п = const; б) р-ых по величине компонент {р = 0 соответствует максимальной компоненте) при N,n оо, р3 =
= o(n), n = 0(N), где p принимает значения из множества {0,1,..., iV-1}; в) р-ых по величине компонент при р const и n/N -> оо, с ограничением на скорость роста дроби n/N.
2. Доказательство того, что в известных ранее теоремах о предельном поведении наибольших объемов деревьев леса Гальтона—Ватсона, числа деревьев заданного объема и высоты леса, условие конечности третьего момента распределения числа прямых потомков каждой частицы в процессе, генерирующем лес Гальтона—Ватсона, может быть заменено на условие конечности второго момента.
3. Предельные распределения объемов всех деревьев леса Гальтона—Ватсона при постоянном числе п некорневых вершин.
4. Предельные распределения р-ых по величине объемов деревьев леса Гальтона—Ватсона при N, п, р оо так, что р3 = = o(n), n = 0(N).
5. Полное описание предельного поведения р-ых по величине длин циклов случайной подстановки степени п с N циклами при п оо, включая случай р оо при ограничениях п — N = 0(N), р3 = о(п - N).
6. Доказательство того, что в случайной подстановке степени п с N циклами гигантский цикл (т.е. цикл, число вершин которого имеет порядок п, в то время как каждый из остальных циклов содержит меньшее по порядку число вершин) возникает только при N,n -v oo так, что iV/ Inn -у 0. Ранее было известно, что гигантский цикл возникает при N/lnn -»• 0 и не возникает при N/Inn -> оо, а случай N х In п не был изучен (символ ж означает, что связанные им величины имеют одинаковый порядок).
Связь работы с крупными научными программами, темами. Результаты диссертации были получены в ходе проработ-
ки темы "Вероятностные и алгебраические методы исследования дискретных объектов", входившей в 1997-2000 гг. в план научно-исследовательских работ Института прикладных математических исследований Карельского научного центра РАН (№ гос. регистрации 01.9.60 0 12636) и выполнявшейся в рамках проекта "Интеграция высшего образования и фундаментальной науки Республики Карелия" ФЦП "Интеграция"(рег. №634). В 2001-2003 гг. исследования проводились в рамках темы плана научно-исследовательских работ этого же института "Вероятности на деревьях и лесах", № гос. регистрации 01.2.00 1 03997. В 2003 г. работа проводилась также по государственному контракту "Исследование случайных комбинаторных структур" по программе фундаментальных исследований РАН "Современные проблемы теоретической математики" (госконтракт № 100002-251/ОМН-01/018-026/090703-1029). В 2000-2002 гг. автор являлся одним из исполнителей гранта РФФИ 00-01-00233 "Вероятности на деревьях и лесах".
Апробация результатов диссертации. Основные результаты докладывались на IV Санкт-Петербургской ассамблее молодых ученых и специалистов (1999 г.), V Петрозаводской международной конференции "Вероятностные методы в дискретной математике" (2000 г.), Kalashnikov Memorial Seminar (Петрозаводск, 2002 г.), научной конференции "Карелия и РФФИ" (Петрозаводск, 2002 г.), IV Всероссийском симпозиуме по прикладной и промышленной математике (Петрозаводск, 2003 г.), международной конференции "Колмогоров и современная математика" (Москва, 2003 г.).
Публикация результатов. Основные результаты диссертации опубликованы в 15 научных работах, из них 3 статьи в журнале "Дискретная математика", 1 статья в трудах международной конференции, 5 статей в сборниках трудов, 6 тезисов докладов на международных, всероссийских и региональных конференциях.
Структура и объем диссертации. Диссертация состоит из вве-
дения, четырех глав и списка литературы. Общий объем диссертации составляет 127 страниц. Список литературы содержит 87 наименований.
СОДЕРЖАНИЕ РАБОТЫ
Во введении обосновывается актуальность темы диссертации, проводится анализ литературы по рассматриваемой тематике, формулируется цель работы и описываются основные методы исследования. Даются основные научные положения, выносимые на защиту. Приводятся описание структуры диссертации и краткая характеристика полученных результатов.
Первая глава носит вводный характер. В этой главе даются все основные определения и обозначения, приводится ряд примеров применения обобщенной схемы размещения. В четвертом параграфе этой главы приводится описание изучаемых в дальнейшем в общем виде схем размещения. Пусть имеется последовательность неотрицательных чисел Ь — (Ьо,Ьг,...), определяющая распределение случайного вектора г) = (г/1,..., т]м) с суммой компонент 771 Н-----Ь гщ — п по формуле
р {т=п1г...,т = пы} = — ьп1...ъп„ {1)
Ъ • ■ ■
ЛН-----к7'лг=п
для всех целых неотрицательных щ,... сумма которых равна п. Ясно, что значения вектора т) можно интерпретировать как размещения (вообще говоря, неравновероятные) п частиц в N занумерованных ячеек. Если £1,..., независимы и одинаково распределены так, что
Р{£х = к} = Ькхк/В(х), (2)
где В(х) — хкЬк (х > 0), то имеет место равенство
' Р{»71 = пм} = = Р{6 = пь..., £лг = плг| £1 +----Ь £лг = п}.
Это значит, что случайные величины обра-
зуют обобщенную схему размещения. Пусть Я — радиус сходимости В(х), причем 0 < Я < оо. В диссертации показано, что все схемы, заданные по формуле (1), могут быть сведены к аналогичным схемам со следующими ограничениями: Л = 1, Ьо > 0 и §сс1(зирр(Ь)) = 1, где эирр означает носитель последовательности Ъ (т.е. множество все таких к, что Ь*. ф 0), а §сс! — наибольший общий делитель. Последнее требование, таким образом, означает, что максимальный шаг & равен 1. Схемы, удовлетворяющие таким условиям, для удобства изложения в диссертации названы каноническими. В 4-м параграфе первой главы показано, что не все схемы размещения могут быть сведены к такому виду, но приведенные примеры являются скорее исключением, подтверждающим правило, т. к. большинство известных в литературе примеров обобщенной схемы размещения все же сводятся к каноническим.
В 5-м параграфе дается описание рассматриваемых случайных подстановок степени п с N циклами. Пусть Хп = {1,... ,п} и 5лг,п — множество всех подстановок Хп с N циклами. Задав на 5дг,„ равномерное распределение, получим случайную подстановку, обозначаемую далее Пусть 771,..., г/лг — длины циклов случайной подстановки тгдг.пт занумерованных в произвольном порядке. Тогда
(щ)-1... (плг)-1
= Щ,. .. , Т)1Ч = Пи} =
£ (л)-1 •••о»-1
ЛН-----Нлг=п
Формула (1) выполнена, если Ь* = 1 /к при к = 1,2,... Таким образом, длины циклов случайной подстановки могут изучаться с помощью канонической схемы. В этом же параграфе приводится ряд известных ранее результатов о цикле максимальной длины.
Вторая глава посвящена исследованию канонической схемы. В параграфе 2.1 вводятся все необходимые обозначения и дается сводка результатов, полученных в этой главе. Пусть щх) ^
... ^ т/(дг) — вариационный ряд случайных величин щ, - ■ ■, г?дг, распределение которых задано формулой (1), пусть независимые одинаково распределенные случайные величины &,..., имеют распределение (2), кроме того, пусть заданы независимые случайные величины ,...,,,..., $$ с распределениями
Р{е!г) = к} = = ЛКх ^ г}, к = г = Р{ЦГ) = к} = Р{6 = *| 6 > г}, А; = г + 1,г + 2,...,
обозначим^=6+-&Г) = &г)=£г)+-+
+и Рг = Р{&. > г}. Хорошо известно, что для обобщенной схемы размещения справедливо следующее утверждение.
Лемма 1.1.1. Для любого р = 0,.М - 1
рг < - V Р'Н Р + ^ = П> Р{^-р) < г} - ^ ^ ^Рг (1 - Рг) ----•
Отсюда видно, что для получения предельных распределений порядковых компонент Щя-р) достаточно найти асимптотику полинома (1-Рг)ы и распределений сумм Сл^+С/^- Слг. Легко видеть, что распределение вектора т) не зависит от параметра х, который задает распределение указанных сумм. Поэтому выбор этого параметра осуществляется наиболее удобным для получения предельных теорем способом. Во второй главе этот выбор производится с помощью равенства Е&. = п/Ы. Там же доказывается, что данное уравнение имеет не более одного решения, а в том случае, если ряд кЬк сходится, результаты этой главы могут быть применены только в случае п = О(М).
Для того, чтобы сформулировать некоторые результаты главы 2, введем ряд обозначений. Пусть V = {ух,... — такое максимальное множество элементов носителя 6, что ух — первый положительный элемент носителя Ь, и для любого з = 2, ш элемент yj является наименьшим элементом носителя Ь, не предста-
вимым в виде комбинации рхух Ч-----(-pj-iyj-i с целыми неотрицательными коэффициентами pi. Множество Y назовем образующим множеством носителя Ь. Если число п представимо в виде
комбинации piyi -----h pwyw, то оно называется разложимым по
Y. Максимум суммы коэффициентов pi Ч-----h pw по всем разложениям обозначим f(n), а через fiy(n) обозначим множество всех векторов р = (pi,. ■ ■ ,pw) с целочисленными неотрицательными координатами таких, что n = piyi H-----1- pwyw и pi H-----1-
+ Pw — Kn)- Имеет место
Теорема 2.1.2. Пусть N -4 оо, n = const и выполнено условие Ьк = 0(h) равномерно по I, к € supp(b) таким, что I < к;
(3)
bk х bk+i и существует К такое, что bk > 0 при к^ К. Тогда для любого yi G Y
£ (b%/pi\)...(%z/pj)
£ (bfc/pj) '
/sefiy(n)
где множество Qy(n,p, in) состоит из таких векторов р е Пу(п), что pi H-----1- Pi ^ f(n) - p, pi +----!- Pu, > p 4- 1. Кроме того, если
P > f(n), ЯЮ
(N-p) = 0} 1. Для случая n оо так, что n х JV, справедлива
Теорема 2.1.6. Пусть х выбран как корень уравнения n = N Е&, TV х n оо и выполнено условие (3). Пусть параметр г выбран так, что NPr оо u (NPr)3 = о(п). Тогда для p х iVPr и любого целого фиксированного h справедливы соотношения:
(p-NPr+h)/y/NPr+h
p{»?(JV-P) ^ Г + Л} ~
—оо
/
-t2/2
Если n/N —> оо, то доказательство локальных теорем для сумм + Сг(г) и Слг значительно усложняется. В диссертации удалось получить такой результат. <
Теорема 2.1.7. Пусть bk ~ fc""*5, где постоянная S € (1;2]. Пусть n/N оо так, что N(1 - ж)"5-1 -> оо, где ж выбрано как корень уравнения N Е = п. Кроме того, пусть параметр г удовлетворяет соотношению NPr 7, где 7 — положительная постоянная. Тогда при любом фиксированном р
' J
p{i7(N-p) jp
г=о '
Все теоремы с 2.1.1 no 2.1.7 описывают предельное поведение компонент причем для п = const получены предельные
распределения для всех р, при п 00, » = 0(N) — только для таких р, что р3 = о(п), а для n/iV 00 в общем виде удалось получить только результат, описанный теоремой 2.1.7.
С помощью теорем 2.1.1-2.1.7 для рассматриваемых в них зон изменения параметров JV, п в диссертации найдены достаточные условия отсутствия гигантской компоненты в канонической схеме. Эти результаты содержатся в теоремах 2.1.8 и 2.1.9.
В параграфах 2.2-2.5 доказываются теоремы 2.1.1-2.1.7 отдельно по зонам изменения параметров N,n, а в параграфе 2.6 доказаны теоремы 2.1.8 и 2.1.9.
В третьей главе рассматриваются леса Гальтона—Ватсона. В параграфе 3.1 дается их определение по схеме, предложенной В. А. Ватутиным. В диссертации рассматриваются леса Гальтона— |
Ватсона, состоящие из N корневых деревьев с п некорневыми вершинами, сгенерированные ветвящимся процессом Гальтона— ^
Ватсона G, начинающимся с N частиц, в котором число прямых потомков каждой частицы имеет распределение
Pk{X) = \kPk/F{\), k = 0,1,..., О< Л < 1,
где (ра,р1,...) — распределение числа прямых потомков частиц в критическом процессе, а ^(А) = рк\к ий- соответственно, производящая функция и максимальный шаг данного распределения. Пусть щ(Х) -1 — число всех потомков начальной частицы г в рассматриваемом процессе Гальтона—Ватсона, а щ-1 — число всех потомков начальной частицы i в соответствующем критическом процессе, I = 1, N. Понятно, что в каждом из этих двух наборов случайные величины независимы и одинаково распределены. Пусть щ,..., 77лг — объемы деревьев рассматриваемого леса Гальтона—Ватсона с N корнями и п некорневыми вершинами, тогда
р{»?1 = кх,...,г)п = км} = = Р{^(А) = *!,... ,им{\) = ки\ VI(А) + • ■ ■ + ЫА) = -¡V + п).
Из равенства
РМА) = к} = ^РЬ=А}
легко получить, что (щ — - 1 )/с1 образуют канони-
ческую схему размещения, если положить Ьк — = к<1 + 1}, х = (А/1г(А))<г. Используя эту связь параметров а; и А, а также результаты главы 2, в диссертации получен весь спектр известных ранее теорем о предельном поведении объемов деревьев леса Гальтона-Ватсона, числа деревьев заданного объема и высоты леса при условии ^"(1) < оо и, кроме того, получены новые теоремы, две из которых приведены ниже.
Теорема 3.2.2. Пусть У — образующее множество носителя распределения (и\ - 1)/с1, Пу(п) — множество всех векторов (п,..., гт) с целыми неотрицательными координатами таких, что п/с? = = ПУ\ + • • • + гшуш и п +----Ь гю — Пусть N оо, п
фиксировано. Тогда для любого ^ 6 У
Е (ЪЦ/ггЦ.-.^/гЛ)
!»Г ,7111 РбОу (п,р,{к)
где множество Пу (п,р, у;) состоит из таких векторов г 6 Пу(п),
чаю п Н-----1- п ^ Яп/с?) - р, г< -I-----1- гш ^ р +1. Кроме того, если
р > Кп/й), то
Р{»?(*-р) = 1} -»■ 1.
Теорема 3.2.6. Пусть И, п оо так, что п принимает значения, кратные (1, п х ЛГ, Л удовлетворяет соотношению
А^'(А) _ п F(A) ~ N + п'
параметр г выбран так, что 7 = ЛГР{1/1(А) > гс? + 1} оо и 73 = о(п). Тогда для р х 7 и любого целого фиксированного к справедливы соотношения:
Р{^-Р) < (г + Н)й + 1} ~ I е-1*'2,
— 00
где 7л = N Р{ух(А) > (г + Ь)<1 + 1}.
Заметим, что теоремы 3.2.2 и 3.2.6, непосредственно следующие из теорем 2.1.2 и 2.1.6, описывают предельное поведение объемов деревьев леса Гальтона—Ватсона для таких зон изменения параметров ЛГ, п, р, которые ранее не были рассмотрены.
Доказательство теорем об объемах деревьев приведено в параграфе 3.3, а для числа деревьев заданного объема и высоты леса — в параграфе 3.4.
Четвертая глава посвящена случайным подстановкам тг^.п степени п с N циклами. Ранее, Ю. Л. Павловым и Е. А. Лосевой
при исследовании случайных рекурсивных лесов были получены предельные распределения длины наибольшего цикла такой подстановки. В частности, имеет место
Теорема 1.5.6. Пусть п оо так, что N/\nn -»• 0. Тогда для любого положительного z
P{-N(ln(l - i?w/n))/lnn ^ z} 1 - e~z.
Из этого результата следует, что при N/Inn 0 возникает гигантский цикл, а из других результатов следует, что при N/lnn оо он не возникает. Вопрос о существовании гигантского цикла при N х In п оставался открытым.
В диссертации рассматриваются компоненты ?7(лг-р). Предельное поведение этих компонент изучается отдельно в каждой из следующих зон изменения параметров N, п:
1. N оо, п — N = const,
2. jV-юо, п- N оо, п- N = o(N),
3. N оо, п - N х N,
4. N оо, n/N оо, N/lnn оо,
5. N оо, N/lnn а, постоянная а > О,
6. N/lnn 0.
Для первых трех зон с использованием теорем главы 2 были получены следующие результаты.
Теорема 4.1.1. Пусть N,n оо и п — N = const. Тогда для р = = 0,... ,n — JV — 1 • - ■ ,
РЦлг-р) = 2} -»• 1.
Теорема 4.1.2. Пусть Ы,п оо так, что п—И оо, п—И — о{И), параметр х выбран как корень уравнения
а-^Ь^-аг)"1 N,
аг^З удовлетворяет соотношениям Мхг~1/г оо, Nxr/(r + +1) 7, где 7 — некоторая неотрицательная постоянная. Тогда для р = 0,1,2,...
А V ' V
Р{Ч(лг-„) =»•>-+ е~7 2 р{г?(лг-р) = г + 1} —1 — е-7 23 ¡7-1=0 ' 1=0 '
Теорема 4.1.3. Пусть И,п оо так, что п-Ы -»■ оо, п-Ы = о(Ы), параметр х выбран как корень уравнения (4), а параметр г ^ 3 удовлетворяет соотношениям: 7 = Nxг/(г +1) оо, 73 = о(п — — ДО). Тогда для р х 7
р{^_р)=г-1}~--== i '41,
—оо 00
р{*7(*-р) = г} ~ У е"<2/2,Й.
Теорема 4.1.4. Пусть N,11-1 оо так, что п - N х ТУ, параметр х выбран как корень уравнения (4), а г удовлетворяет соотношению пхг/г 7, где 7 — положительная постоянная. Тогда для р = 0,1,2,... и любого целого фиксированного Ь
г=о
Теорема 4.1.5. Пусть N,71 оо так, что п — N N, параметр х выбран как корень уравнения (4), а г выбран так, что 7 = = пжГ/г -4 оо и 73 = о(п - ЛГ). Тогда для р ж у и любого целого
фиксированного h справедливы соотношения:
(p—Vh)/y/Th
D-t2/ 2
7л = nxr+h/r.
Для случая n/TV oo найденные в главе 2 результаты неприменимы, поэтому следующие теоремы были доказаны с помощью локальной предельной теоремы, а в 6 зоне изменения параметров — непосредственным вычислением требуемых по лемме 1.1.1 вероятностей.
Теорема 4.1.6. Пусть N, п оо так, что n/N 00 и N/ In п ->■ оо, х выбран как корень уравнения (4), г удовлетворяет соотношению пхг/г 7, где 7 — положительная постоянная. Тогда для р = 0,1,2,...
р у
P{V(N-P) ^r}-s>e 7Х,7Г'
г=о '
Обозначим h{y,z) = уа~1
■\ot-l
Xi . . .Xs
Is(y,z)= I ———-—-dxi...dxs,
s(y,z) = /
J X(s,y,z
где Х{з,у,г) = {(ц,... ,ха) : хк ^ г, у > »1 + • • •+ в = 1,2,..., а — параметр, определяющий зону 5.
Теорема 4.1.7. Пусть Ы,п -¥ оо так, что Ы/ 1пп а, где а — некоторая положительная постоянная. Тогда для р = 0,1,2,... и любого фиксированного х > О
Теорема 4.1.8. Пусть п оо так, что И/Ып 0, г удовлетворяет соотношению 1п (п/г) ~ 7(1п где 7 — положительная постоянная. Тогда для р= 1,2,...
р-1 1
р{*?(лг-р) ^ Г} е-7 £ г=о
если N оо, и
г=о 4 7 если N фиксировано и у < N.
Все эти результаты приводятся в первом параграфе 4-ой главы, а далее, в параграфах 4.2-4.5 проводится их доказательство. В параграфе 4.6 с помощью теорем 4.1.1-4.1.8 и 1.5.6 показано, что гигантский цикл в рассматриваемой случайной подстановке возникает только в шестой зоне изменения параметров N, п, т. е. при N11пп -4 0.
СПИСОК ОПУБЛИКОВАННЫХ РАБОТ ПО ТЕМЕ ДИССЕРТАЦИИ
Статьи
1. Казимиров Н. И. Локальная сходимость в схеме серий и ветвящиеся процессы // Тр. Петрозаводского ГУ, сер. математика, 1997, 4, с.85-96.
2. Казимиров Н. И. О предельных распределениях для числа потомков процесса Гальтона—Ватсона // Тр. Института прикл. матем. исслед. Карельского НЦ РАН, 1999, 1, с.7-20.
3. Казимиров Н. И., Павлов Ю. Л. Одно замечание о лесах Гальтона—Ватсона // Дискретная математика, 2000, 12, №1, с.47-59.
4. Казимиров Н. И. О некоторых условиях отсутствия гигантской компоненты в обобщенной схеме размещения // Дискретная математика, 2002, 14, №2, с.107-118.
5. Казимиров Н. И. Один случай локальной предельной теоремы // Тр. Института прикл. матем. исслед. Карельского НЦ РАН, 2002, 3, с.58-66.
6. Kazimirov N. I. Local limit theorems for an array scheme and Galton—Watson forests // In: Probabilistic Methods in Discrete Math. Proc. of the Fifth Intern. Petrozavodsk Conf., Utrecht, VSP, 2002, pp.189-196.
7. Казимиров H. И, Возникновение гигантской компоненты в случайной подстановке с известным числом циклов // Дискретная математика, 2003, 15, №3.
8. Казимиров Н. И. Об асимптотике больших компонент обобщенной схемы размещения // Тр. Института прикл. матем. исслед. Карельского НЦ РАН, 2003, 4, с.61-76.
9. Казимиров Н. И. Предельные распределения наибольших длин циклов случайной подстановки // Тр. Института прикл. матем. исслед. Карельского НЦ РАН, 2003, 4, с.77-82.
Тезисы докладов
10. Казимиров Н. И. Предельные теоремы для лесов Гальтона— Ватсона // IV С.-Пб. ассамблея молодых ученых и специалистов, СПб, 1999, с.37.
11. Казимиров Н. И. Об асимптотике распределений числа потомков процесса Гальтона—Ватсона // Обозрение прикл. и пром. математики, 2000, 7, №1, с.105-106.
12. Казимиров Н. И. Об асимптотике больших компонент в обобщенной схеме размещения // Тез. докл. науч. конф. "Карелия и РФФИ", Петрозаводск, 2002, с.88-89.
13. Kazimirov N. I. On the asymptotics of big components in a generalized allocation scheme // Information Processes, 2002, 2, №2, pp.209-210.
14. Казимиров H. И. Предельные распределения больших компонент в случайной подстановке с известным числом циклов // Обозрение прикладной и промышленной математики, 2003, 4, №1, с. 166-167.
15. Kazimirov N. I., Pavlov Yu. L. On a giant component in random permutation with a known number of cycles. // Abstracts of Conf. Kolmogorov and Contemporary Math., MSU, 2003, pp. 461-462.
!
/
Изд. лиц. № 00041 от 03.11.99. Подписано в печать 27.10.03. Формат 60х84'/16. Бумага офсетная UNION PRINT S. Гарнитура «Times». Печать офсетная. Уч.-изд. л. 1,3. Уел печ. л. 1,2. Тираж 100 экз. Изд. № 59. Заказ № 372
Карельский научный центр РАН 185003, Петрозаводск, пр. А. Невского, 50 Редакционно-издательский отдел
2оот-А I g о £ о * 1802 0
Введение
1 Обобщенная схема размещения
1.1 Основные определения и обозначения.
1.2 Графы.
1.3 Примеры применения обобщенной схемы размещения
1.4 Описание класса рассматриваемых схем размещения.
1.5 Случайные подстановки и случайные рекурсивные леса.
2 Некоторые свойства обобщенной схемы размещения
2.1 Обозначения и сводка результатов.
2.2 Случай N оо, п = const.
2.3 Случай n/N О, N, п оо.
2.4 Случай пх N, N,n-t оо.
2.5 Случай n/N оо при некоторых ограничениях.
2.6 Некоторые условия отсутствия гигантской компоненты
3 Леса Гальтона—Ватсона
3.1 Определение леса Гальтона—Ватсона.
3.2 Сводка результатов.
3.3 Доказательство теорем об объемах деревьев.
3.4 Доказательство теорем о/^ит.
4 Случайные подстановки с известным числом циклов
4.1 Сводка результатов.
4.2 Предельные распределения длин циклов при п = O(N)
4.3 Предельные распределения длин циклов в зоне 4.
4.4 Предельное распределение длин циклов в зоне 5.
4.5 Предельное распределение длин циклов в зоне 6.
4.6 Условия возникновения гигантского цикла.
В настоящее время широкое распространение в комбинаторном анализе получил теоретико-вероятностный подход. Хорошо развитые в теории вероятностей методы асимптотического анализа успешно используются при решении сложных комбинаторных задач. Впервые такой подход был использован В. Л. Гончаровым в статьях [6,7], применившим его к изучению случайных подстановок и (0, ^-последовательностей.
Применение вероятностных методов в решении перечислительных задач комбинаторики (см., например, [26,30,56,83]) связано с заданием вероятностей на множестве изучаемых комбинаторных объектов таким образом, чтобы эти вероятности определяли долю объектов с интересующими нас свойствами. Тогда, используя теоретико-вероятностный аналитический аппарат, можно получить точные или приближенные формулы для числа объектов, обладающих изучаемыми свойствами.
Одним из важнейших направлений исследований является изучение предельных свойств комбинаторных объектов, проявляющихся при неограниченном возрастании числа элементов, образующих такие объекты. Поэтому при анализе случайных структур использовались такие известные методы, как пуассоновская и гауссовская аппроксимации, производящие функции и их анализ методом перевала. В последние три десятилетия широкое распространение получил подход, основанный на применении обобщенной схемы размещения, введенной В. Ф. Колчи-ным [26,30,34]. Такой подход позволяет свести целый ряд комбинаторных задач к задачам о нахождении предельных распределений серий сумм независимых случайных величин.
Значительное внимание в работах по дискретной математике в настоящее время уделяется изучению случайных графов [30,31,34,50,56,58-60, 69,74-77,83]. С помощью обобщенной схемы размещения в этой области математики удается решать множество сложных и полезных в других областях науки задач. Так, случайные деревья, леса и подстановки находят применение в анализе вычислительных алгоритмов [77], статистических методах [11,38], моделировании транспортных [1,76] и информационных систем [76,86], генетике [81], криптографии [54,79], а также при решении собственно математических задач, например, в теории случайных уравнений [32,34] и проблеме эволюции случайных графов [3,31,60,69,82].
Объектами изучения в диссертации являются: собственно обобщенная схема размещения, леса Гальтона—Ватсона и случайные подстановки.
Так как к обобщенной схеме размещения сводится большое число задач комбинаторики, она представляет интерес как самостоятельный объект исследования. Свое название эта схема получила в связи с тем, что она является обобщением задачи о случайном равновероятном размещении п частиц в N ячеек, за которой утвердилось название классическая схема размещения. Терминология классической схемы размещения оказалась удобной для описания многих задач, в которых появляется полиномиальное распределение случайного вектора из N компонент. Классическая схема позволяет перейти от полиномиального распределения к распределению сумм независимых слагаемых с распределением Пуассона и усеченным распределением Пуассона. Введение обобщенной схемы размещения частиц не только расширяет область использования удобного языка для описания комбинаторных структур, но также дает возможность применять те методы, которые были развиты при анализе классической схемы [26]. Отметим, что все результаты, связанные с обобщенной схемой размещения, доказывались для каждого класса комбинаторных объектов отдельно. Однако некоторое сходство предельных теорем, получаемых в различных задачах с помощью обобщенной схемы размещения, позволяет надеяться на получение достаточно общих предельных теорем для обобщенной схемы размещения. В диссертации сделана попытка реализовать этот замысел, и доказан ряд достаточно общих теорем, не охватывающих однако тех зон изменения параметров Nun, интерес к которым в последнее время особенно велик в связи с понятием гигантской компоненты [35].
Леса Гальтона—Ватсона представляют собой случайные леса, соответствующие траекториям ветвящегося процесса Гальтона—Ватсона, откуда и происходит это название. Термин лес Гальтона—Ватсона впервые, по-видимому, встречается в работе [84]. Применению методов теории ветвящихся процессов для изучения случайных лесов предшествовало рассмотрение случайных деревьев с занумерованными вершинами и соответствующих им процессов Гальтона—Ватсона с пуассоновским распределением числа прямых потомков каждой частицы. Впервые на эту возможность указано в статье В. Е. Степанова [59], а систематически такое исследование проведено в работах В. Ф. Колчина [27-29]. В [4,43,44] была установлена связь между начинающимися с одной частицы процессами Гальтона—Ватсона с геометрическим распределением числа прямых потомков каждой частицы и посаженными деревьями [53] (т. е. плоскими деревьями с висячими корнями и непомеченными вершинами). Связь между лесами, состоящими из N посаженных деревьев, и начинающимися с N частиц ветвящимися процессами Гальтона-Ватсона с геометрическим распределением числа прямых потомков одной частицы, впервые рассматривается в работах [10,47]. В [45,46,48-51] рассматривались случайные леса, для которых предполагалась связь с условными ветвящимися процессами Гальтона—Ватсона, распределение вероятностей на множестве лесов при этом не было обязательно равномерным. Однако ограничения на вероятностную меру не позволяли использовать полученные результаты для многих классов случайных лесов. В работах [67,83] эти ограничения были сняты, однако осталось одно существенное ограничение на распределение числа прямых потомков каждой частицы в процессах Гальтона—Ватсона, соответствующих рассматриваемым лесам: ограниченность третьего момента этого распределения. В статье [16] удалось снять это ограничение для распределений максимального объема дерева, числа деревьев заданного объема и высоты леса Гальтона—Ватсона, показав, что оно может быть заменено более слабым, а именно, ограниченностью второго момента распределения числа прямых потомков каждой частицы. В статье [68] удалось обобщить эти результаты для распределений объемов наибольших деревьев. Кроме того, в диссертации с помощью общих результатов об обобщенной схеме размещения удалось получить также некоторые дополнительные результаты о предельном поведении объемов деревьев леса Гальтона—Ватсона.
Случайные подстановки занимают особое место в ряду комбинаторных задач, связанных с обобщенной схемой размещения. Как показано в статье [52], случайные подстановки с известным числом циклов соответствуют той же обобщенной схеме размещения, что и рекурсивные леса [87]. Как показано в [78], такие леса не могут быть изучены с помощью ветвящегося процесса Гальтона—Ватсона. Наиболее подробно результаты исследований случайных подстановок и история этих исследований изложены в [30,33,34]. Там же приведены теоремы о предельном распределении числа циклов случайной подстановки степени п при п —» оо с ограничениями на длины циклов и без ограничений. В статье [52] получено полное описание предельного поведения максимальной длины цикла случайной подстановки с известным числом циклов при п оо, а в работе [61] получены некоторые результаты о распределении числа циклов заданной длины для таких подстановок. В диссертации получено полное описание предельного поведения р-то по величине цикла при фиксированном р и в некоторых зонах изменения параметров — для р —> оо.
В последнее время в работах по случайным графам повышенный интерес проявляется к возникновению гигантской компоненты, т. е. такой компоненты, которая с вероятностью, стремящейся к единице, имеет порядок п, где п — число вершин графа, а следующая по величине компонента имеет порядок о(п) [35]. В работе [66] были найдены условия возникновения гигантского дерева в лесе Гальтона—Ватсона, а из результатов статьи [52] следует, что гигантский цикл в случайной подстановке степени п с N циклами при п оо возникает при условии N/ In п 0 и не возникает при условии N/\nn оо. В диссертации доказано, что при N/ In п -» а > 0, где а — константа, гигантский цикл также не возникает.
Целью диссертации является получение новых результатов о предельном поведении важнейших характеристик лесов Гальтона—Ватсона и случайных подстановок с известным числом циклов. В частности, предполагалось, во-первых, снятие ограничения конечности третьего момента распределения числа прямых потомков каждой частицы в ветвящемся процессе, генерирующем лес Гальтона—Ватсона, для изучения всех известных характеристик леса, во-вторых, получение полного спектра теорем, описывающих предельное поведение наибольших длин циклов случайной подстановки с известным числом циклов, в-третьих, выявление условий возникновения гигантского цикла в случайной подстановке. Для достижения этой цели предполагалось получение новых результатов об обобщенной схеме размещения и использование этих результатов для получения предельных распределений числовых характеристик различных комбинаторных объектов.
Основными методами исследования в диссертации являются обобщенная схема размещения, теория ветвящихся процессов Гальтона—Ватсона и методы получения предельных теорем для сумм независимых решетчатых случайных величин, включая локальную сходимость в схеме серий. В настоящее время известные достаточные условия такой сходимости не покрывают все зоны изменения параметров многих комбинаторных объектов (по этому поводу см. параграф 1.4 книги [30]). И хотя в последних работах (см., например, [39]) имеются определенные достижения в этом направлении, эта проблема по-прежнему остается актуальной, а проверка известных условий часто оказывается весьма трудной задачей. В диссертации удалось для некоторых случаев применить результаты статьи [39] и получить несколько общих теорем для обобщенной схемы размещения. Эти теоремы были использованы для достижения целей диссертации. Однако, возникающие здесь технические трудности, к сожалению, не позволили получить весь спектр предельных теорем для обобщенной схемы размещения. Кроме того, удалось получить несколько дополнительных результатов, а именно: а) предельные распределения всех компонент леса Гальтона—Ватсона с N корнями и п некорневыми вершинами при N оо и п = const, б) предельные распределения р-ой по величине компоненты леса Гальтона—Ватсона с N корнями и п некорневыми вершинами и случайной подстановки степени п с N циклами при N,n,p оо так, что п = O(N), с некоторыми ограничениями на скорость роста р.
Диссертация состоит из четырех глав. Первая глава носит вводный характер. В этой главе даются все основные определения и обозначения (параграфы 1.1 и 1.2), приводится ряд примеров применения обобщенной схемы размещения (параграф 1.3). В четвертом параграфе этой главы приводится описание изучаемых в дальнейшем в общем виде схем размещения. Такие схемы (названные для краткости каноническими) охватывают широкий спектр задач, сводимых к обобщенной схеме размещения. В этом же параграфе показано, что не все схемы размещения могут быть сведены к такому виду, но приведенные примеры являются скорее исключением, подтверждающим правило, т. к. большинство известных в литературе примеров обобщенной схемы размещения все же сводятся к такому виду, который рассмотрен в диссертации. В параграфе 1.5 дается описание рассматриваемых случайных подстановок степени п с N циклами и приводится ряд известных ранее результатов о цикле максимальной длины.
Вторая глава целиком посвящена исследованию обобщенной схемы размещения. Здесь для схем, определенных в параграфе 1.4, с N компонентами, сумма которых равна п, найдены предельные распределения всех компонент в случае п = const, а при N, п —> оо так, что п = O(N), найдены предельные распределения р-х по величине компонент, причем как для фиксированного р, так и для р —> оо так, что р3 = о(п). Кроме того, при усилении ограничений на рассматриваемые схемы размещения получены предельные распределения для р-х компонент при фиксированном р и n/N -» оо, причем на скорость роста дроби n/N также накладываются определенные ограничения. Эти результаты используются в последующих главах для получения теорем о лесах Гальтона—Ватсона и случайных подстановках. В первом параграфе главы 2 указывается также граница применимости полученных теорем: они не могут быть использованы, например, для получения предельных распределений объемов деревьев случайного леса из некорневых деревьев. В конце главы 2 (параграф 2.6) приводятся теоремы, дающие достаточные условия невозникновения гигантской компоненты в обобщенной схеме размещения. Эти теоремы получены из предыдущих результатов главы 2 и не охватывают всех зон изменения параметров.
В третьей главе рассматриваются леса Гальтона—Ватсона. Сначала (параграф 3.1) приводится определение леса Гальтона—Ватсона по схеме, предложенной В. А. Ватутиным [4]. Затем (параграф 3.2) перечислены все результаты о лесах Гальтона—Ватсона, для которых в дальнейшем (параграфы 3.3 и 3.4) будет установлена избыточность условия конечности третьего момента распределения числа прямых потомков каждой частицы в соответствующем процессе Гальтона—Ватсона. Здесь же (параграф 3.2) перечислены теоремы, доказанные на основе результатов главы 2 и дающие предельные распределения объемов деревьев леса Гальтона— Ватсона в тех зонах изменения параметров N, п,р, которые ранее не были изучены.
Четвертая глава посвящена случайным подстановкам с известным числом циклов. В параграфе 4.1 приводится список всех полученных в диссертации результатов об асимптотике наибольших длин циклов случайной подстановки, а в последующих параграфах 4.2-4.5 приводится их доказательство. В параграфе 4.6 доказывается, что только в последней зоне изменения параметров (N/ In п -» 0) возникает гигантский цикл.
Основными результатами диссертации являются:
1. Предельные распределения при N оо: а) всех компонент обобщенной схемы размещения п частиц по N ячейкам при п = const; б) р-ых по величине компонент (р = 0 соответствует максимальной компоненте) при N, п оо, р3 = о(п), п = O(N), где р принимает значения из множества {0,1,., N — 1}; в) р-ых по величине компонент при р = const и n/N оо, с ограничением на скорость роста n/N.
2. Доказательство того, что в известных ранее теоремах о предельном поведении наибольших объемов деревьев леса Гальтона—Ватсона, числа деревьев заданного объема и высоты леса, условие конечности третьего момента распределения числа прямых потомков каждой частицы в процессе, генерирующем лес Гальтона—Ватсона, может быть заменено на условие конечности второго момента.
3. Предельные распределения объемов всех деревьев леса Гальтона— Ватсона при постоянном числе п некорневых вершин.
4. Предельные распределения р-ых по величине объемов деревьев леса Гальтона—Ватсона при N,n,p оо так, что р3 = о(п), п = O(N).
5. Полное описание предельного поведения длин р-ых по величине длин циклов случайной подстановки степени п с N циклами при п -» оо, включая случай р -> оо при ограничениях п — N = O(N), р3 — о{п — N).
6. Доказательство того, что в случайной подстановке степени п с N циклами гигантский цикл возникает только при N,n оо так, что N/\nn 0.
Основные результаты диссертации опубликованы автором в пятнадцати работах [13-24,71-73], из них 3 статьи в журнале "Дискретная математика" [16,18,22], 1 статья в трудах международной конференции [72], 5 статей в сборниках трудов [13, 14, 19,23,24], 6 тезисов докладов на международных, всероссийских и региональных конференциях [15, 17,20,21,71,73]. Результаты также докладывались на IV Санкт-Петербургской ассамблее молодых ученых и специалистов (1999 г.), V Петрозаводской международной конференции "Вероятностные методы в дискретной математике" (2000 г.), Kalashnikov Memorial Seminar (Петрозаводск, 2002 г.), научной конференции "Карелия и РФФИ" (Петрозаводск, 2002 г.), IV Всероссийском симпозиуме по прикладной и промышленной математике (Петрозаводск, 2003 г.), международной конференции "Колмогоров и современная математика" (Москва, 2003 г.). В 2000-2002 гг. автор являлся одним из исполнителей гранта РФФИ 0001-00233 "Вероятности на деревьях и лесах". В рамках этого проекта создан интернет-ресурс "Случайные леса" [85].
Результаты диссертации были получены в ходе проработки темы "Вероятностные и алгебраические методы исследования дискретных объектов", входившей в 1997-2000 гг. в план научно-исследовательских работ Института прикладных математических исследований Карельского научного центра РАН (№ гос. регистрации 01.9.60 0 12636) и выполнявшейся в рамках проекта "Интеграция высшего образования и фундаментальной науки Республики Карелия" ФЦП "Интеграция" (per. №634). В 2001-2003 гг. исследования проводились в рамках темы плана научно-исследовательских работ этого же института "Вероятности на деревьях и лесах", № гос. регистрации 01.2.00 1 03997. В 2003 г. работа проводилась также по государственному контракту "Исследование случайных комбинаторных структур" по программе фундаментальных исследований РАН "Современные проблемы теоретической математики" (госконтракт № 100002-251/ОМН-01/018-026/090703-1029).
В диссертации принята двойная нумерация параграфов и тройная нумерация теорем, лемм, формул и замечаний. Это значит, что параграф 3.4 является четвертым по порядку в главе 3, а теорема 2.1.2 является второй по порядку в параграфе 2.1.
1. Борисов Г. А. Методы автоматизированного проектирования лесо-транспорта. Петрозаводск, КФ АН СССР, 1978.
2. Боровков А. А. Курс теории вероятностей. М., Наука, 1972.
3. Бритиков В. Е. О структуре случайного графа вблизи критической точки. // Дискретная математика, 1989, 1, №3, с. 121-126.
4. Ватутин В. А. Распределение расстояния до корня минимального поддерева, содержащего все вершины данной высоты // Теория вероятностей и ее применения, 1993, 38, №2, с.273-287.
5. Гнеденко Б. В., Колмогоров А. Н. Предельные распределения для сумм независимых случайных величин. М., Наука, 1949.
6. Гончаров В. Л. О распределение циклов в перестановках. Докл. АН СССР. 1942, 35, вып.9( с.299-301.
7. Гончаров В. Л. Из области комбинаторики. Изв. АН СССР. Сер. ма-тем., 1944, 8, вып.1, с.3-48.
8. Грэхем Р., Кнут Д., Паташник О. Конкретная математика. М., Мир, 1998.
9. Дрмота М. Распределение высоты листьев корневых деревьев // Дискретная математика, 1994, 6, №1, с.67-82.
10. Земляченко В. Н., Павлов Ю. Л. Леса из плоских посаженых деревьев, и ветвящиеся процессы. // Труды Петрозаводского ун-та. Сер. прикладная математика и информатика, 1992, 1, с.130-135.
11. Иванов В. А., Ивченко Г. И., Медведев Ю. И. Дискретные задачи в теории вероятностей. // Итоги науки и техники. Сер. теория вероятн., матем. стат., теор. кибернетика, 1984, 22, с.3-60.
12. Ибрагимов И. А., Линник Ю. В. Независимые и стационарно связанные величины. М., Наука, 1965.
13. Казимиров Н. И. Локальная сходимость в схеме серий и ветвящиеся процессы // Тр. Петрозаводского ГУ, сер.математика, 1997, 4, с.85-96.
14. Казимиров Н. И. О предельных распределениях для числа потомков процесса Гальтона—Ватсона // Тр. Института прикл. матем. исслед. Карельского НЦ РАН, 1999, 1, с.7-20.
15. Казимиров Н. И. Предельные теоремы для лесов Гальтона—Ватсона // IV С.-Пб. ассамблея молодых ученых и специалистов, СПб, 1999, с.37.
16. Казимиров Н. И., Павлов Ю. Л. Одно замечание о лесах Гальтона— Ватсона // Дискретная математика, 2000, 12, №1, с.47-59.
17. Казимиров Н. И. Об асимптотике распределений числа потомков процесса Гальтона—Ватсона // Обозрение прикл. и пром. математики, 2000, 7, №1, с. 105-106.
18. Казимиров Н. И. О некоторых условиях отсутствия гигантской компоненты в обобщенной схеме размещения // Дискретная математика, 2002, 14, №2, с. 107-118.
19. Казимиров Н. И. Один случай локальной предельной теоремы // Тр. Института прикл. матем. исслед. Карельского НЦ РАН, 2002, 3, с.58-66.
20. Казимиров Н. И. Об асимптотике больших компонент в обобщенной схеме размещения // Тез. докл. науч. конф. "Карелия и РФФИ", Петрозаводск, 2002, с.88-89.
21. Казимиров Н. И. Предельные распределения больших компонент в случайной подстановке с известным числом циклов // Обозрение прикладной и промышленной математики, 2003, 4, №1, с. 166-167.
22. Казимиров Н. И. Возникновение гигантской компоненты в случайной подстановке с известным числом циклов // Дискретная математика, 2003, 15, №3.
23. Казимиров Н. И. Об асимптотике больших компонент обобщенной схемы размещения // Тр. Института прикл. матем. исслед. Карельского НЦ РАН, 2003, 4, с.61-76.
24. Казимиров Н. И. Предельные распределения наибольших длин циклов случайной подстановки //Тр. Института прикл. матем. исслед. Карельского НЦ РАН, 2003, 4, с.77-82.
25. Калинина Н. Б., Павлов Ю. Л. Распределение кратностей вершин в случайном лесе. // Ветвящиеся процессы. Петрозаводск, КФ АН СССР, 1981, с.10-16.
26. Колчин В. Ф., Севастьянов Б. А., Чистяков В. П. Случайные размещения. М., Наука, 1976.
27. Колчин В. Ф. Ветвящиеся процессы, случайные деревья и обобщенная схема размещения. // Математические заметки, 1977, 21, №5, с.691-705.
28. Колчин В. Ф. Момент вырождения ветвящегося процесса и высота случайного дерева. // Математические заметки, 1978, 24, №6, с.859-870.
29. Колчин В. Ф. Ветвящиеся процессы и случайные деревья. // Вопр. кибернетики. Комбинаторный анализ и теория графов. М., 1980, с.85-97.
30. Колчин В. Ф. Случайные отображения. М., Наука, 1984.
31. Колчин В. Ф. О поведении случайного графа вблизи критической точки. // Теория вероятностей и ее применения, 1986, 31, №3, с.503-515.
32. Колчин В. Ф. Системы случайных уравнений. М., МИЭМ, 1988.
33. Колчин В. Ф. О числе подстановок с ограничениями на длины циклов. // Дискретная математика, 1989, 1, №2, с.97-109.
34. Колчин В. Ф. Случайные графы. М., Физматлит, 2000.
35. Колчин В. Ф. О существовании гигантской компоненты в схемах размещения частиц. // Обозрение прикладной и промышленной математики, 2000, 7, в. 1, с. 112-ИЗ.
36. Лукач Е. Характеристические функции. М., Наука, 1979.
37. Маркушевич А. И. Теория аналитических функций. М., Гостехиздат, 1950.
38. Матула Д. В. Методы теории графов в алгоритмах кластерного анализа. В кн.: Классификация и кластер. М., Мир, 1980, с.83-111.
39. Мухин А. Б. Локальные предельные теоремы для решетчатых случайных величин. // Теория вероятностей и ее применения, 1991, 36, №4, с.660-674.
40. Павлов Ю. Л. Предельные теоремы для числа деревьев заданного объема в случайном лесе. // Математический сборник, 1977, 103, в.З, с.392-403.
41. Павлов Ю. Л. Асимптотическое распределение максимального объема дерева в случайном лесе. // Теория вероятностей и ее применения, 1977, 22, №3, с.523-533.
42. Павлов Ю. Л. Один случай предельного распределения максимального объема дерева в случайном лесе. // Математические заметки, 1979, 25, №5, с.751-760.
43. Павлов Ю. Л. Некоторые свойства плоских деревьев с висячим корнем. // Тез. докл. Всесоюз. школы "Дискретная математика и ее применения при моделировании сложных систем". Иркутск, 1991, с. 14.
44. Павлов Ю. Л. Некоторые свойства плоских деревьев с висячим корнем. // Дискретная математика, 1992, 4, №2, с.61-65.
45. Павлов Ю. Л. О случайных деревьях. // Тр. Петрозаводского ГУ, сер. математика, 1993, 1, с.47-53.
46. Павлов Ю. Л. Асимптотическое поведение высоты случайного леса. // Сборник трудов Отдела математики и анализа данных КарНЦ РАН, 1994, 1, с.4-17.
47. Павлов Ю. Л. Предельные распределения высоты случайного леса из плоских корневых деревьев. // Дискретная математика, 1994, 6, №1, с. 137-154.
48. Павлов Ю. Л. Предельные распределения максимального объема дерева в случайном лесе. // Дискретная математика, 1995, 7, №3, с. 1932.
49. Павлов Ю. Л. Предельные распределения числа деревьев заданного объема в случайном лесе. // Дискретная математика, 1996, 8, №2, с.31-47.
50. Павлов Ю. А. Случайные леса. Петрозаводск, КарНЦ РАН, 1996.
51. Павлов Ю. Л., Чеплюкова И. А. Предельные распределения числа вершин в слоях просто генерируемого леса. // Дискретная математика, 1999, И, №1, с.97-112.
52. Павлов Ю. Л., Лосева Е. А. Предельные распределения максимального объема дерева в случайном рекурсивном лесе. // Дискретная математика, 2002, 14, №1, с.60-74.
53. Пойа Д. Комбинаторные вычисления для групп, графов и химических соединений. // Перечислительные задачи комбинаторного анализа. М., Мир, 1979, с.36-138.
54. Ростовцев А. Г. О времени жизни общего и персонального открытого ключа. // Проблемы информационной безопасности. Компьютерные системы. СПб., №4, 1999, с.57-61.
55. Сачков В. Н. Комбинаторные методы дискретной математики. М., Наука, 1977.
56. Сачков В. Н. Вероятностные методы в комбинаторном анализе. М., Наука, 1978.
57. Севастьянов Б. А. Ветвящиеся процессы. М., Наука, 1971.
58. Степанов В. Е. О распределении числа вершин в слоях случайного дерева. // Теория вероятностей и ее применения, 1969, 14, №1, с.64-77.
59. Степанов В. Е. Предельные распределения некоторых характеристик случайных отображений. // Теория вероятностей и ее применения, 1969, 14, №4, с.639-653.
60. Степанов В. Е. О некоторых особенностях строения случайного графа вблизи критической точки. // Теория вероятностей и ее применения, 1987, 32, №4, с.633-657.
61. Тимашев А. Н. О распределении числа циклов заданной длины в классе подстановок с известным числом циклов. // Дискретная математика, 2001, 13, №4, с.60-72.
62. Феллер В. Введение в теорию вероятностей и ее приложения. М., Мир, 1967.
63. Харари Ф. Теория графов. М., Мир, 1973.
64. Харари Ф., Палмер Э. Перечисление графов. М., Мир, 1977.
65. Харрис Т. Теория ветвящихся случайных процессов. М., Мир, 1966.
66. Чеплюкова И. А. Возникновение гигантского дерева в случайном лесе. // Дискретная математика, 1998, 10, №1, с.111-126.
67. Чеплюкова И. А. Предельные теоремы для лесов Гальтона—Ватсона. Дисс. на соискание уч. степени канд. физ.-мат. наук, Петрозаводск, Кар НЦ РАН, 2000.
68. Чеплюкова И. А. К вопросу о возникновении гигантской компоненты. // Тр. Института прикл. матем. исслед. Карельского НЦ РАН, 2002, 3, с.114-123.
69. Bollobas В. Random graphs. London, Academic Press, 1985.
70. Eric Weisstein's World of Mathematics (http://mathworld.wolfram.com/ CoinProblem.html).
71. Kazimirov N. I. On the asymptotics of big components in a generalized allocation scheme // Information Processes, 2002, 2, №2, pp.209-210.
72. Kazimirov N. I. Local limit theorems for an array scheme and Galton— Watson forests // In: Probabilistic Methods in Discrete Math. Proc. of the Fifth Intern. Petrozavodsk Conf., Utrecht, VSP, 2002, pp. 189-196.
73. Kazimirov N. I., Pavlov Yu. L. On a giant component in random permutation with a known number of cycles. // Abstracts of Conf. Kolmogorov and Contemporary Math., MSU, 2003, pp.461-462.
74. Le Gall. Branching Processes, Random Trees and Superprocesses // Proc. Math. J. PMV, Extra Volume ICM, 1998, III, pp.279-289.
75. Luczak Т., Pittel B. Components of random forests // Combinatorics, Probability and Computing, 1992, 1, 35-52.
76. Lyons R., Peres Yu. Probability on trees and networks. Book in preparation, available at http://php.indiana.edu/~rdlyons/prbtree/prbtree.html
77. Mahmoud H. M. Evalution of random search trees. Wiley, New York, 1992.
78. Meir A., Moon J. W. On the altitude of nodes in random trees // Can. J. Math., 1978, 30, №5, pp.997-1015.
79. Menezes A., P. van Oorschot, S. Vanstone. Handbook of applied cryptography. CRC Press, 1996, electronic version is available at http://www.cacr.math.uwaterloo.ca/hac
80. Myllari T. Limit distributions for the number of leaves on a random forest. // Adv. Appl. Probab., 34, 2002, pp. 1-19.
81. O'Connel N. Branching and Inference in Population Genetics. // Proceedings of the IMA Workshop of Population Genetics. Dublin, 1994.
82. Palmer E. M. Graphical evolution: An introduction to the theory of random graphs. New York, 1985.
83. Pavlov Yu. L. Random Forests. Utrecht, VSP, 2000.
84. Random Forests, web-page at http://www.krc.karelia.ru/structure/math/ forests/index.html
85. Reittu H., Norros I. On large random graphs of the "Internet type" // Information Processes, 2002, 2, №2, pp.244-245.
86. Shapiro A. A generalized distribution model for random recursive trees // Acta Informatica, 1997, 34, pp.211-216.
