Математический сборник
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Скоро в журнале
Архив
Импакт-фактор
Правила для авторов
Лицензионный договор
Загрузить рукопись
Историческая справка

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Матем. сб.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Математический сборник, 2021, том 212, номер 9, страницы 146–163
DOI: https://doi.org/10.4213/sm9481
(Mi sm9481)
 

Эта публикация цитируется в 9 научных статьях (всего в 9 статьях)

Максимальное дерево случайного леса в конфигурационном графе

Ю. Л. Павлов

Институт прикладных математических исследований Карельского научного центра Российской академии наук, г. Петрозаводск
Список литературы:
Аннотация: Рассматриваются случайные леса Гальтона–Ватсона с заданным числом корневых деревьев и известным числом некорневых вершин. Предполагается, что в генерирующем лес процессе распределение числа прямых потомков каждой частицы имеет бесконечную дисперсию. Такие ветвящиеся процессы успешно используются в исследованиях конфигурационных графов, предназначенных для моделирования структуры и динамики развития сложных сетей коммуникаций, в частности сети Интернет. Известная связь между конфигурационными графами и случайными лесами отражает локальную древовидность моделируемых сетей. В статье доказаны предельные теоремы для максимального объема дерева случайного леса во всех основных зонах стремления числа деревьев и числа вершин к бесконечности.
Библиография: 14 названий.
Ключевые слова: случайный лес, конфигурационный граф, объем дерева, предельные теоремы.
Финансовая поддержка Номер гранта
Министерство науки и высшего образования Российской Федерации 075-03-2020-522
Работа подготовлена в рамках выполнения государственного задания Министерства науки и высшего образования (соглашение № 075-03-2020-522).
Поступила в редакцию: 21.07.2020 и 28.09.2020
Англоязычная версия:
Sbornik: Mathematics, 2021, Volume 212, Issue 9, Pages 1329–1346
DOI: https://doi.org/10.1070/SM9481
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.179.4
PACS: 02.10.Ox
MSC: 60C05

§ 1. Введение

В настоящей работе рассматривается один класс лесов Гальтона–Ватсона, состоящих из $N$ корневых деревьев и содержащих $n$ некорневых вершин в каждом лесе. Для этих лесов получены предельные распределения максимального объема дерева при $N,n\to \infty$. Постановка задачи возникла в связи с последними исследованиями структуры конфигурационных графов (см. [1]). Такие графы, впервые введенные в статье [2], широко используются для моделирования современных сложных сетей коммуникаций таких, как Интернет, социальные, телефонные, транспортные сети. По этой тематике опубликованы сотни статей и ряд монографий. Наиболее полный обзор результатов исследований можно найти в книгах [3], [4].

Многочисленные наблюдения за реальными сетями показали, что большинство сетей обладает фундаментальным свойством, состоящим в том, что число узлов, степень которых не меньше $k$, при больших $k$ пропорционально $k^{-\tau}$, где $\tau$ – положительный параметр. Оказалось также, что если общее число узлов в сети достаточно велико, то в моделях степени вершин можно считать независимыми одинаково распределенными случайными величинами. На основании анализа эмпирических данных было предложено в качестве таких моделей использовать случайные графы, степени вершин которых независимы и имеют общее распределение такое, что

$$ \begin{equation*} \mathbf P\{\eta =k\}=\frac{h(k)}{k^{\tau}}, \qquad k=1,2,\dots, \end{equation*} \notag $$
где $\eta$ – случайная величина, равная степени любой вершины графа, а $h(x)$ – медленно меняющаяся функция.

Для моделирования сетей в последние годы часто применяются конфигурационные графы со случайными степенями вершин. В таких графах степень каждой вершины равна числу выходящих из нее полуребер, т.е. ребер, инцидентных этой вершине, но для которых смежные вершины еще не определены. Все полуребра различимы (занумерованы в произвольном порядке). Граф строится путем равновероятного попарного соединения полуребер друг с другом для образования ребер. Поскольку сумма степеней вершин любого графа должна быть четной, в случае нечетной суммы в граф вводится вспомогательная вершина единичной степени. В [3; ч. III, п. 7.6] и в [5] отмечается, что эта вспомогательная вершина вместе с инцидентным ей ребром не влияет на асимптотические свойства графа при стремлении числа вершин к бесконечности. Понятно, что такая конструкция графа допускает появление петель и кратных ребер.

В процессе исследования структуры и предельного поведения конфигурационных графов успешно применяются методы теории ветвящихся процессов (см. [4; ч. II, гл. 4, ч. III, гл. 7]). Каждой вершине графа можно поставить в соответствие начинающийся с одной частицы ветвящийся процесс Гальтона–Ватсона, в котором распределение числа прямых потомков начальной частицы совпадает с распределением $\eta$. Предположим, что случайная величина $\eta$ имеет конечное математическое ожидание $\mathbf E \eta$. Обозначим $\xi$ случайную величину, равную числу прямых потомков всех остальных частиц ветвящегося процесса, и пусть

$$ \begin{equation*} \mathbf P\{\xi =k\}=\frac{(k+1)\mathbf P\{\eta =k+1\}}{\mathbf E\eta}, \qquad k=0,1,2,\dots\,. \end{equation*} \notag $$

Связь между такими ветвящимися процессами и конфигурационными графами подробно изучается в [4; ч. II, гл. 4, ч. III, гл. 7]. С помощью этой связи при стремящемся к бесконечности числе вершин графа найдены условия возникновения гигантской компоненты связности, получены оценки объемов гигантской и второй по величине компонент связности, а также оценка диаметра графа. Установленное соответствие процесса конфигурационному графу позволило выявить локальную древовидность структуры графа. Она состоит в том, что содержащий произвольно выбранную вершину связный подграф даже при достаточно большом числе вершин этого подграфа асимптотически достоверно сближается с ограниченной общим числом частиц частью траектории начинающегося с одной частицы ветвящегося процесса. Эта часть траектории представляет собой дерево, корнем которого служит выбранная вершина.

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

Пусть однородный ветвящийся процесс Гальтона–Ватсона $G$ начинается с $N$ частиц и распределение случайной величины $\xi$, равной числу прямых потомков каждой частицы, имеет вид

$$ \begin{equation} p_k=\mathbf P\{\xi =k\}=\frac{h(k+1)}{(k+1)^{\tau +1}}, \qquad k=0,1,2, \dots, \quad \tau \in (1, 2), \end{equation} \tag{1.1} $$
где медленно меняющаяся функция $h(x)$ при $x\geqslant 1$ принимает только положительные значения. В распределении (1.1) выбор возможных значений параметра $\tau$ связан с тем, что, как показали наблюдения за разнообразными сетями, именно такие значения параметра характерны для многих сетей (см., например, [3; гл. 1]).

Ниже будет использоваться хорошо известное свойство медленно меняющейся функции, состоящее в том, что при любом $\delta >0$ и достаточно больших $x$

$$ \begin{equation} x^{-\delta}<h(x)<x^\delta. \end{equation} \tag{1.2} $$
Из (1.1), (1.2) и условия $\tau >1$ следует, что если $\delta$ в (1.2) мало, то случайная величина $\xi$ имеет конечное математическое ожидание. Будем далее считать, что $\mathbf E \xi=1$, т.е. процесс $G$ является критическим.

Очевидно, что $G$ распадается на $N$ начинающихся с одной частицы независимых ветвящихся процессов $G_1, \dots, G_N$. Рассмотрим подмножество траекторий процесса $G$, в которых кроме $N$ начальных существовало еще $n$ остальных частиц за все время эволюции процесса. Распределение вероятностей на таком подмножестве траекторий естественным образом индуцируется ветвящимся процессом. В результате получаем случайный лес $\mathcal F_{N,n}$, состоящий из $N$ корневых деревьев, корни которых имеют номера $1, \dots, N$ и соответствуют начальным частицам процесса, а общее число некорневых вершин равно $n$. Таким образом, любая реализация $F_{N,n}\in \mathcal F_{N,n}$ содержит $N+n$ вершин. Различные примеры таких случайных лесов Гальтона–Ватсона, их структура и предельное поведение важнейших числовых характеристик при $N, n\to \infty$ были изучены в монографии [6]. Однако эти результаты были получены при условии, что распределение числа прямых потомков каждой частицы генерирующего лес ветвящегося процесса имеет конечный третий момент. Позднее, в [7], было показано, что результаты из [6] остаются справедливыми и при существовании только конечной дисперсии. Из (1.1), (1.2) видно, что при $\tau \in (1, 2)$ распределение (1.1) не имеет дисперсии, следовательно, результаты из [6], [7] к случайному лесу $\mathcal F_{N,n}$ неприменимы.

Обозначим $\nu_1(\mathcal F), \dots, \nu_N(\mathcal F)$ случайные величины, равные объемам деревьев леса из $\mathcal F_{N,n}$, имеющих корни с номерами $1, \dots, N$ соответственно. Под объемом дерева понимается число его вершин. Обозначим $\nu_{\max}$ максимальный объем дерева в таком случайном лесе:

$$ \begin{equation} \nu_{\max}=\max_{1\leqslant i \leqslant N} \nu_i(\mathcal F). \end{equation} \tag{1.3} $$
Ниже будут доказаны предельные теоремы для $\nu_{\max}$ в трех зонах стремления $N$ и $n$ к бесконечности: $n/N\to 0$, $0<C_1\leqslant n/N \leqslant C_2<\infty$, $n/N\to \infty$; здесь и далее символы $C_1, C_2, \dots$ обозначают некоторые положительные постоянные. Полученные в статье результаты не охватывают все возможные варианты поведения $N, n$. В некоторых случаях найти предельные распределения $\nu_{\max}$ не удалось, и автор надеется сделать это в следующих работах.

Статья организована следующим образом. В § 2 приводятся формулировки основных результатов (теоремы 13). В § 3 обсуждается связь между случайными лесами и обобщенной схемой размещения частиц по ячейкам. На использовании этой связи в значительной степени базируется идея доказательства теорем. Результаты из § 4 позволяют оценить асимптотическое поведение бинома, возникающего в обобщенной схеме размещения в рамках рассматриваемой модели (см. лемму 1). В § 5 и § 6 доказываются леммы о локальной сходимости к предельным законам распределений серий сумм вспомогательных независимых случайных величин. Результаты из §§ 46 применяются в § 7 для доказательства теорем 13.

§ 2. Основные результаты

Введем необходимые обозначения. Пусть случайная величина $\xi(\lambda)$ имеет распределение

$$ \begin{equation} p_k(\lambda)=\mathbf P\{\xi(\lambda)=k\}=\frac{\lambda^kp_k}{F(\lambda)}, \qquad k=0,1,2, \dots, \end{equation} \tag{2.1} $$
где $0<\lambda <1$, вероятности $p_k$ определены в (1.1) и
$$ \begin{equation} F(\lambda)=\sum_{k=0}^\infty p_k\lambda^k. \end{equation} \tag{2.2} $$

Наряду с процессом $G$ рассмотрим также ветвящийся процесс $G(\lambda)$, отличающийся от $G$ только тем, что случайная величина, равная числу прямых потомков каждой частицы, имеет распределение (2.1). Пусть $m(\lambda)=\mathbf E\xi(\lambda)$. Нетрудно видеть, что

$$ \begin{equation} m(\lambda)=\frac{\lambda F'(\lambda)}{F(\lambda)}. \end{equation} \tag{2.3} $$
Далее в качестве значения параметра $\lambda$ распределения (2.1) будем выбирать решение уравнения
$$ \begin{equation} m(\lambda)=\frac{n}{N+n}. \end{equation} \tag{2.4} $$
Используя (2.2) и (2.3), легко установить, что при $0<\lambda <1$ уравнение (2.4) имеет единственное решение.

Обозначим

$$ \begin{equation} \alpha =\frac{\lambda}{F(\lambda)}, \qquad \beta =-\ln \alpha . \end{equation} \tag{2.5} $$
Введем стремящуюся к бесконечности последовательность $B_r$, $r=1,2,\dots$, которая при $r\to \infty$ удовлетворяет условию
$$ \begin{equation} B_r \sim (rh(B_r))^{1/\tau}. \end{equation} \tag{2.6} $$

Пусть $g(x)$ означает плотность устойчивого закона с показателем $\tau$ и характеристической функцией

$$ \begin{equation} f(t)=\exp \biggl\{-c|t|^\tau\biggl(1-i\frac{t}{|t|} \operatorname{tg} \frac{\pi \tau}{2}\biggr)\biggr\}, \end{equation} \tag{2.7} $$
где
$$ \begin{equation} c=-\frac{\Gamma(2-\tau)}{\tau(\tau-1)}\cos \frac{\pi \tau}{2}, \end{equation} \tag{2.8} $$
$\Gamma(x)$ – гамма-функция. Заметим, что $0<g(0)<\infty$ при $\tau\in (1, 2)$ в силу одновершинности устойчивых распределений (см. [8; гл. 2, п. 2.7]).

Основными результатами статьи являются следующие теоремы.

Теорема 1. Пусть $N,n\to \infty$, так что $n/N \to 0$, $\gamma$ – некоторая неотрицательная постоянная. Пусть натуральные числа $r=r(N,n)$ выбраны так, что выполнено одно из следующих условий:

  • 1) $r$ фиксировано,
    $$ \begin{equation} N\alpha ^{r-1}R(r-1)\to \infty, \qquad \frac{N\alpha^r}{(r+1)p_0}R(r)\to \gamma, \end{equation} \tag{2.9} $$
    где
    $$ \begin{equation} \begin{gathered} \, R(r)=\sum_S p_{s_1}p_{s_2} \dotsb p_{s_{r+1}}, \\ \notag S=\{s_1,s_2, \dots, s_{r+1}\colon s_1+\dots +s_{r+1}=r\}; \end{gathered} \end{equation} \tag{2.10} $$
  • 2) $r\to \infty$,
    $$ \begin{equation} \frac{N\alpha^{r-1}}{rB_r}\to \infty, \qquad \frac{N\alpha^rg(0)}{rp_0B_r}\to \gamma. \end{equation} \tag{2.11} $$

Тогда

$$ \begin{equation*} \mathbf P\{\nu_{\max}=r\}\to e^{-\gamma},\qquad \mathbf P\{\nu_{\max}=r+1\}\to 1-e^{-\gamma}. \end{equation*} \notag $$

Теорема 2. Пусть $N,n\to \infty$, так что $0<C_1 \leqslant n/N \leqslant C_2<\infty$, а $r=r(N,n)$ пробегают натуральные значения такие, что

$$ \begin{equation} \frac{N\alpha^rg(0)}{rB_rF(\lambda)}\to \gamma, \end{equation} \tag{2.12} $$
где $\gamma$ – некоторая положительная постоянная. Тогда для $k=0,\pm 1,\pm 2,\dots$
$$ \begin{equation*} \mathbf P\{\nu_{\max}\leqslant r+k\}\sim \exp\{-\gamma \alpha^k(1-\alpha)^{-1}\}. \end{equation*} \notag $$

Теорема 3. Пусть $N,n\to \infty$, так что $n/N\to \infty$ и существуют такие положительные постоянные $\Delta$, $\omega$, $\upsilon$, где $\upsilon <1/2$, что

$$ \begin{equation} \biggl(\frac{n}{N}\biggr)^2=o(N^\upsilon (1-\lambda)^{1+\Delta}), \end{equation} \tag{2.13} $$
$$ \begin{equation} \beta >(\ln N)^{-\omega}. \end{equation} \tag{2.14} $$
Пусть $r=r(N,n)$ выбраны так, что
$$ \begin{equation} \frac{Ng(0)}{r\beta e^{r\beta} B_r}\to z, \end{equation} \tag{2.15} $$
где $z$ – фиксированное положительное число. Тогда
$$ \begin{equation*} \mathbf P\{\nu_{\max}\leqslant r\}\to e^{-z}. \end{equation*} \notag $$

§ 3. Связь с обобщенной схемой размещения

Процесс $G(\lambda)$, как и $G$, распадается на $N$ независимых начинающихся с одной частицы процессов $G_1(\lambda), \dots, G_N(\lambda)$. Обозначим $\nu^{(1)}(\lambda), \dots, \nu^{(N)}(\lambda)$ случайные величины, равные числу частиц, существовавших соответственно в процессах $G_1(\lambda), \dots, G_N(\lambda)$ до их вырождения. Пусть $\nu(\lambda)\,{=}\,\nu^{(1)}(\lambda)\,{+}\,{\cdots}\,{+}\,\nu^{(N)}(\lambda)$. В [6; гл. 2, п. 1] (см. также [9]) показано, что для натуральных $k_1, \dots, k_N$ таких, что $k_1+ \dots +k_N=N+n$, справедливо равенство

$$ \begin{equation} \begin{aligned} \, \notag &\mathbf P\{\nu_1(\mathcal F)=k_1, \dots, \nu_N(\mathcal F)=k_N\} \\ &\qquad =\mathbf P\{\nu^{(1)}(\lambda)=k_1, \dots, \nu^{(N)}(\lambda)=k_N\mid \nu(\lambda)=N+n\}. \end{aligned} \end{equation} \tag{3.1} $$
Равенство (3.1) означает, что для двух наборов случайных величин $\nu_1(\mathcal F), \dots, \nu_N(\mathcal F)$ и $\nu^{(1)}(\lambda), \dots, \nu^{(N)}(\lambda)$ выполнены условия обобщенной схемы размещения частиц по ячейкам, предложенной и подробно исследованной В. Ф. Колчиным (см. [10; гл. I, § 2]).

Введем вспомогательные независимые случайные величины $\nu_r^{(1)}(\lambda),\dots, \nu_r^{(N)}(\lambda)$ такие, что для целых $r>1$

$$ \begin{equation} \mathbf P\{\nu_r^{(i)}(\lambda)=k\}=\mathbf P\{\nu^{(i)}(\lambda)=k\mid \nu^{(i)}(\lambda)\leqslant r\}, \end{equation} \tag{3.2} $$
где $i=1, \dots, N$, $k=1,2, \dots, r$. Обозначим также
$$ \begin{equation} P_r=\mathbf P\{\nu^{(1)}(\lambda)>r\}=\sum_{i=0}^\infty \mathbf P\{\nu^{(1)}(\lambda)=r+i+1\}, \end{equation} \tag{3.3} $$
и пусть $\nu_r(\lambda)=\nu_r^{(1)}(\lambda)+ \dots +\nu_r^{(N)}(\lambda)$. В [10; гл. I, § 8, лемма 2] показано, что в условиях обобщенной схемы размещения из (1.3) и (3.1) следует такое утверждение.

Лемма 1. При $n$ таких, что $\mathbf P\{\nu(\lambda)=N+n\}>0$,

$$ \begin{equation} \mathbf P\{\nu_{\max}\leqslant r\}=(1-P_r)^N\frac{\mathbf P\{\nu_r(\lambda)=N+n\}}{\mathbf P\{\nu(\lambda)=N+n\}}. \end{equation} \tag{3.4} $$

Идея доказательства теорем 13 основана на использовании леммы 1. Равенство (3.4) показывает, что для получения утверждений теорем достаточно изучить предельное поведение бинома $(1-P_r)^N$ и сумм $\nu_r(\lambda), \nu(\lambda)$. Для этого полезно знать характер изменения решения уравнения (2.4) в зависимости от $N$ и $n$. Дифференцируя (2.3) и проводя элементарные вычисления, нетрудно получить следующий результат, доказанный в [6; гл. 2, п. 2, лемма 1].

Лемма 2. Пусть $N,n\to \infty$. Справедливы следующие утверждения.

§ 4. Асимптотика $NP_r$

Для оценки предельного поведения величины $(1-P_r)^N$ (см. (3.4)) рассмотрим произведение $NP_r$.

Лемма 3. Пусть выполнены условия теоремы 1. Тогда

$$ \begin{equation*} NP_{r-1}\to \infty, \qquad NP_r\to \gamma, \qquad NP_{r+1}\to 0. \end{equation*} \notag $$

Доказательство. Пусть случайные величины $\xi_1, \dots, \xi_N$ независимы и одинаково распределены по закону (1.1). Обозначим $\zeta_N=\xi_1+\dots+\xi_N$. Аналогично, пусть $\xi_1(\lambda), \dots, \xi_N(\lambda)$ – независимые копии случайной величины $\xi(\lambda)$ с распределением (2.1) и $\zeta_N(\lambda)=\xi_1(\lambda)+\dots+\xi_N(\lambda)$. В [10; гл. II, § 1, лемма 3] утверждается, что при $i=0,1,2,\dots$
$$ \begin{equation} \mathbf P\{\nu^{(1)}(\lambda)=r+i+1\}=\frac{1}{r+i+1}\mathbf P\{\zeta_{r+i+1}(\lambda)=r+i\}. \end{equation} \tag{4.1} $$
Отсюда и из (2.1), (2.5) вытекает равенство
$$ \begin{equation} \mathbf P\{\nu^{(1)}(\lambda)=r+i+1\}=\frac{\alpha^{r+i}}{(r+i+1)F(\lambda)}\mathbf P\{\zeta_{r+i+1}=r+i\}. \end{equation} \tag{4.2} $$
Применив к (3.3) соотношения (2.2), (2.5), (4.1), (4.2) и утверждение 1 леммы 2, приходим к выводу, что
$$ \begin{equation} P_r\sim \frac{\alpha^r}{(r+1)p_0}\mathbf P\{\zeta_{r+1}=r\}. \end{equation} \tag{4.3} $$

Пусть $r$ фиксировано. Из (1.1), (2.2), (2.10) и (4.3) получаем

$$ \begin{equation*} \begin{gathered} \, NP_{r-1}\sim \frac{N\alpha^{r-1}}{rp_0}R(r-1), \qquad NP_r\sim \frac{N\alpha^r}{(r+1)p_0}R(r), \\ NP_{r+1}\sim \frac{N\alpha^{r+1}}{(r+2)p_0}R(r+1), \end{gathered} \end{equation*} \notag $$
и из (2.5), (2.9) следует утверждение леммы 3 для этого случая.

Пусть $r\to \infty$. Обозначим $F_\xi(x)$ функцию распределения случайной величины $\xi$. Из (1.1) видим, что при $x<0$

$$ \begin{equation} F_\xi(x)=0, \end{equation} \tag{4.4} $$
а если $x>0$, то
$$ \begin{equation*} F_\xi(x)=1-\sum_{k\geqslant x}p_k. \end{equation*} \notag $$
Из условия (1.1) и [11; гл. VIII, § 9, теорема 1, а] следует, что при $x\to \infty$
$$ \begin{equation} F_\xi(x)=1-\frac{h(x)}{\tau x^\tau} (1+o(1)). \end{equation} \tag{4.5} $$
Соотношения (4.4) и (4.5) означают, что функция $F_\xi(x)$ удовлетворяет условиям теоремы 2.6.1 из [12; гл. II, § 6], следовательно, она принадлежит области притяжения устойчивого закона $H(x)$ с показателем $\tau$. Поскольку максимальный шаг распределения (1.1) равен единице, из теоремы 4.2.1 в [12; гл. IV, § 2] следует, что при $r\to \infty$ и любом фиксированном $k=0, \pm 1, \pm 2, \dots$ имеет место локальная сходимость
$$ \begin{equation*} \sup_k|B_r\mathbf P\{\zeta_{r+k+1}=r+k\}-g(-B_r^{-1})|\to 0. \end{equation*} \notag $$
Поскольку $B_r\to \infty$, отсюда получаем
$$ \begin{equation} \mathbf P\{\zeta_{r+k+1}=r+k\}\sim \frac{g(0)}{B_r}, \end{equation} \tag{4.6} $$
и из (2.2), (2.5), (3.3), (4.2), (4.3) заключаем, учитывая лемму 2, что при $k=0,\pm 1, \pm 2, \dots$
$$ \begin{equation*} NP_{r+k}=\frac{N\alpha^{r+k}g(0)}{rp_0B_r}(1+o(1)). \end{equation*} \notag $$
Из этого равенства, (2.5), (2.11), (3.3), условия $n/N\to 0$ и леммы 2 очевидным образом вытекают доказываемые утверждения.

Лемма 3 доказана.

Лемма 4. Пусть выполнены условия теоремы 2. Тогда для $k\,{=}\,0,\pm 1, \pm 2, \dots$

$$ \begin{equation*} NP_{r+k}\sim \gamma \alpha^k(1-\alpha)^{-1}. \end{equation*} \notag $$

Доказательство. Пусть $k>0$. Из (3.3) следует, что
$$ \begin{equation} NP_{r+k}=NP_r-N\sum_{i=0}^{k-1} \mathbf P\{\nu^{(1)}(\lambda)=r+i+1\}. \end{equation} \tag{4.7} $$
В условиях теоремы 2 $r\to \infty$, поэтому из (4.2) и (4.6) находим, что для любого фиксированного $i$
$$ \begin{equation} \mathbf P\{\nu^{(1)}(\lambda)=r+i+1\}\sim \frac{\alpha^{r+i}}{(r+1)F(\lambda)}\mathbf P\{\zeta_{r+1}=r\}=\alpha^i\mathbf P\{\nu^{(1)}(\lambda)=r+1\}. \end{equation} \tag{4.8} $$
Из (2.3)(2.5) и утверждения 2 леммы 2 получаем, что $\alpha\leqslant C_5<1$, поэтому из (4.8) следует
$$ \begin{equation} \sum_{i=0}^{k-1}\mathbf P\{\nu^{(1)}(\lambda)=r+i+1\}\sim \frac{1-\alpha^k}{1-\alpha} \mathbf P\{\nu^{(1)}(\lambda)=r+1\}, \end{equation} \tag{4.9} $$
при этом
$$ \begin{equation*} P_r\sim \frac{1}{1-\alpha}\mathbf P\{\nu^{(1)}(\lambda)=r+1\}. \end{equation*} \notag $$
Отсюда и из (2.12), (4.2), (4.6), (4.7), (4.9) вытекает утверждение леммы 4 при $k> 0$. Доказательство для $k\leqslant 0$ проводится аналогично.

Лемма доказана.

Осталось рассмотреть случай $n/N\to \infty$.

Лемма 5. Пусть выполнены условия теоремы 3. Тогда $NP_r\to z$.

Доказательство. Из (2.2), (2.5), (3.3), (4.2), (4.6) и утверждения 3 леммы 2 следует, что
$$ \begin{equation} \begin{aligned} \, \notag P_r &=\frac{1}{F(\lambda)}\sum_{i=0}^\infty \frac{\alpha^{r+i}}{r+i+1}\mathbf P\{\zeta_{r+i+1}=r+i\} \\ &=\frac{g(0)+o(1)}{F(\lambda)}\sum_{i=0}^\infty \frac{e^{-(r+i)\beta}}{(r+i+1)B_{r+i+1}} \notag \\ \notag &=(g(0)+o(1))\sum_{k=r}^\infty \frac{1}{kB_k}e^{-k\beta}\sim g(0)\int_r^\infty \frac{1}{xB_{[x]}}e^{-x\beta}\,dx \\ &\sim g(0)\int_1^\infty \frac{1}{yB_{[yr]}}e^{-yr\beta}\,dy =\frac{g(0)}{B_r}\int_1^\infty \frac{B_r}{yB_{[ry]}}e^{-yr\beta}\,dy. \end{aligned} \end{equation} \tag{4.10} $$
В силу условия (2.6) при $r\to \infty$
$$ \begin{equation*} \frac{B_r}{B{[yr]}}\to \frac{1}{y^{1/\tau}} \end{equation*} \notag $$
равномерно внутри любого конечного интервала $[1,K]$. Поэтому
$$ \begin{equation*} \int_1^K \frac{B_r}{yB_{[yr]}}e^{-yr\beta}\,dy \sim \int_1^K \frac{1}{y^{1+1/\tau}}e^{-yr\beta}\,dy =(r\beta)^{1/\tau}\int_{r\beta}^{Kr\beta} \frac{1}{u^{1+1/\tau}}e^{-u}\,du. \end{equation*} \notag $$
Используя соотношение $r\beta \to \infty$ (оно следует из (2.6), (2.14), (2.15)) и асимптотические свойства неполной гамма-функции (см., например, [13; гл. 9, п. 9.5, равенство (4)]), отсюда получаем, что
$$ \begin{equation} \int_1^K \frac{B_r}{yB_{[ry]}}e^{-yr\beta}\,dy \sim \frac{1}{r\beta}e^{-r\beta}. \end{equation} \tag{4.11} $$
Легко видеть также, что
$$ \begin{equation} \int_K^\infty \frac{B_r}{yB_{[ry]}}e^{-yr\beta}\,dy \leqslant \frac{C_6}{K}\int_K^\infty e^{-yr\beta}\,dy =\frac{C_6}{Kr\beta}e^{-Kr\beta}. \end{equation} \tag{4.12} $$
Поскольку число $K$ можно выбрать сколь угодно большим, из (4.10)(4.12) находим, что
$$ \begin{equation} P_r\sim \frac{g(0)}{r\beta e^{r\beta}B_r}. \end{equation} \tag{4.13} $$
Отсюда и из условия (2.15) следует утверждение леммы.

Лемма доказана.

§ 5. Предельное поведение $\nu(\lambda)$

В § 3 было введено обозначение $\nu(\lambda)$ для общего числа частиц, существовавших в процессе $G(\lambda)$ до его вырождения. Рассмотрим предельное поведение этой случайной величины в условиях теорем 13. Нетрудно видеть, что производящая функция распределения (2.1) имеет вид

$$ \begin{equation} \sum_{k=0}^\infty p_k(\lambda)x^k=\frac{F(\lambda x)}{F(\lambda)}. \end{equation} \tag{5.1} $$
Пусть $\varphi_\nu^{(1)}(t)$ обозначает характеристическую функцию случайной величины $\nu^{(1)}(\lambda)$. Из [10; гл. 2, § 4, лемма 1] и (5.1) следует, что
$$ \begin{equation} \varphi_\nu^{(1)}(t)=e^{it}\frac{F(\lambda \varphi_\nu^{(1)}(t))}{F(\lambda)}. \end{equation} \tag{5.2} $$

Обозначим $a(\lambda)=\mathbf E \nu^{(1)}(\lambda), \ b^2(\lambda)=\mathbf D \nu^{(1)}(\lambda)$. Дифференцируя (5.2) и используя простейшие свойства характеристических функций, нетрудно получить равенства

$$ \begin{equation} a(\lambda)=\frac{1}{1-m(\lambda)}, \qquad b^2(\lambda)=\frac{\sigma^2(\lambda)}{(1-m(\lambda))^3}, \end{equation} \tag{5.3} $$
где $m(\lambda)$ определено в (2.4), а $\sigma^2(\lambda)=\mathbf D \xi(\lambda)$. Пусть $\psi_\nu(t)$ обозначает характеристическую функцию случайной величины $(\nu(\lambda)-Na(\lambda))/(b(\lambda)\sqrt{N})$. В следующей лемме показано, что распределение этой случайной величины слабо сходится к нормальному закону.

Лемма 6. При выполнении условий любой из теорем 13 $\psi_\nu(t)\to e^{-t^2/2}$.

Доказательство. Если выполнены условия теорем 1 или 2, то доказательство утверждения леммы 6 повторяет доказательство леммы 1 из [6; гл. 2, п. 3] (см. также лемму 3 в статье [7]), при этом учитываются лемма 2, (2.4) и (5.3).

Пусть выполнены условия теоремы 3. Нетрудно видеть, что при достаточно малых $t$ справедливо разложение

$$ \begin{equation*} \ln \varphi_\nu^{(1)}(t)=ita(\lambda)-\frac{b^2(\lambda)t^2}{2}+\frac{t^3}{6}Q(t), \end{equation*} \notag $$
где
$$ \begin{equation} |Q(t)|\leqslant 2\max_{|v|\leqslant |t|} |(\ln \varphi_\nu^{(1)}(v))_v^{'''}|. \end{equation} \tag{5.4} $$
Отсюда следует, что при достаточно больших $N,n$ и любом фиксированном $t$
$$ \begin{equation} \ln \psi_\nu(t)=-\frac{t^2}{2}+\frac{t^3}{6b^3(\lambda)\sqrt{N}}\,Q\biggl (\frac{t}{b(\lambda)\sqrt{N}}\biggr ). \end{equation} \tag{5.5} $$

Разумеется, лемма будет доказана, если последнее слагаемое в (5.5) стремится к нулю. Из (1.1), (2.1) находим, что при достаточно больших $k$

$$ \begin{equation*} \mathbf E \xi^2(\lambda)>\sum_{i\geqslant k} \frac{i^2p_i\lambda^i}{F(\lambda)}\geqslant C_7\sum_{i\geqslant k} \frac{\lambda^ih(i+1)}{(i+1)^{\tau-1}}. \end{equation*} \notag $$
Отсюда и из (1.2) получаем, что для любого $\delta >0$
$$ \begin{equation} \mathbf E \xi^2(\lambda)>C_8\sum_{i\geqslant k}\frac{\lambda^i}{(i+1)^{\tau+\delta-1}}. \end{equation} \tag{5.6} $$
Из [11; гл. III, § 5, теорема 5] следует, что при $\lambda\to 1$ и $0\leqslant \rho <\infty$
$$ \begin{equation} \sum_{k=0}^\infty k^{\rho-1}\lambda^k \sim \frac{\Gamma(\rho)}{(1-\lambda)^\rho}. \end{equation} \tag{5.7} $$
Полагая $\rho=2-\tau -\delta$, отсюда с учетом (2.4), (5.3), (5.6) и леммы 2 выводим, что при достаточно малых $\delta$
$$ \begin{equation} b^2(\lambda)\geqslant \frac{C_9}{(1-\lambda)^{2-\tau-\delta}}\biggl (\frac{n}{N}\biggr )^3 \geqslant C_9\biggl(\frac{n}{N}\biggr)^3. \end{equation} \tag{5.8} $$
Дифференцируя (5.2), легко получить, что
$$ \begin{equation*} (\varphi_\nu^{(1)}(t))_t'=\frac{ie^{it}F^{-1}(\lambda)F(\lambda \varphi_\nu^{(1)}(t))}{1-e^{it}\lambda F^{-1}(\lambda) F_\varphi'(\lambda \varphi_\nu^{(1)}(t))}, \end{equation*} \notag $$
при этом, очевидно, производная производящей функции $F(\lambda \varphi_\nu ^{(1)}(t))$ берется по аргументу $\lambda \varphi_\nu^{(1)}(t)$. Это равенство было использовано в [6; гл. 2, п. 3, лемма 1], где путем логарифмирования (5.2) и последующего дифференцирования был найден явный вид $(\ln \varphi_\nu^{(1)}(t))_t^{'''}$ и было показано, что из (2.4), (5.3) и (5.4) при достаточно малых $t$ вытекает оценка
$$ \begin{equation} |Q(t)|\leqslant C_{10}\biggl (\frac{n}{N}\biggr )^5|F_\varphi ^{'''}(\lambda \varphi_\nu^{(1)}(t))|. \end{equation} \tag{5.9} $$
Учитывая (1.1), (1.2), (2.1) и (5.1), нетрудно обнаружить, что
$$ \begin{equation*} |F_\varphi ^{'''}(\lambda \varphi_\nu^{(1)}(t))|\leqslant C_{11} \sum_{k=1}^\infty k^3p_k|\lambda \varphi_\nu^{(1)}(t)|^{k-3}\leqslant C_{11}\sum_{k=1}^\infty \lambda^k(k+1)^{2-\tau+\delta}. \end{equation*} \notag $$
Опять применяя (5.7) в случае $\rho \,{=}\,3\,{-}\,\tau \,{+}\,\delta$, как и при нахождении (5.8), из (5.9) получаем
$$ \begin{equation} |Q(t)|\leqslant \frac{C_{12}}{(1-\lambda)^{3-\tau+\delta}}\biggl (\frac{n}{N}\biggr )^5. \end{equation} \tag{5.10} $$
Эта оценка и (5.8) показывают, что при любом фиксированном $t$
$$ \begin{equation} \frac{1}{b^3(\lambda)\sqrt{N}}\biggl |Q\biggl (\frac{t}{b(\lambda)\sqrt{N}}\biggr )\biggr |\leqslant \frac{C_{13}}{(1-\lambda)^{(\tau+5\delta)/2}}\frac{\sqrt{n}}{N}. \end{equation} \tag{5.11} $$
Из условий $\tau<2$, $\upsilon<1/2$ и (2.13) вытекает, как нетрудно проверить, что при достаточно малом $\delta$
$$ \begin{equation} \frac{n}{N^2(1-\lambda)^{\tau+5\delta}} =o\biggl(\frac{1}{N^{3/4}(1-\lambda)^{(3-\Delta+10\delta)/2}}\biggr ). \end{equation} \tag{5.12} $$
Из (2.13) следует, что $N^{\upsilon}(1-\lambda)^{1+\Delta}\to \infty$, поэтому $N^{3/4}(1-\lambda)^{3(1+\Delta)/(4\upsilon)}\to \infty$. Нетрудно видеть, что при $\lambda \to 1$, $\upsilon <1/2$ и достаточно малых $\delta$
$$ \begin{equation*} N^{3/4}(1-\lambda)^{(3-\Delta+10\delta)/2} > N^{3/4}(1-\lambda)^{3(1+\Delta)/(4\upsilon)}\to \infty, \end{equation*} \notag $$
поэтому из (5.12) находим, что оценка (5.11) стремится к нулю. что и завершает доказательство.

Лемма 6 доказана.

Из установленной в лемме 6 слабой сходимости следует локальная, что показано ниже.

Лемма 7. Пусть выполнены условия любой из теорем 13. Тогда для натуральных $k$ равномерно относительно $(k-N-n)/(b(\lambda)\sqrt{N})$ в любом фиксированном конечном интервале

$$ \begin{equation*} \mathbf P\{\nu(\lambda)=k\}=\frac{1+o(1)}{b(\lambda)\sqrt{2\pi N}}\exp \biggl \{-\frac{(k-N-n)^2}{2b^2(\lambda)N}\biggr \}. \end{equation*} \notag $$

Доказательство. При выполнении условий теорем 1 и 2 утверждение леммы доказано в [6; гл. 2, п. 3, лемма 2] (см. также [9; лемма 4]). Для доказательства в условиях теоремы 3 заметим, что в силу выбора параметра $\lambda$ как решения уравнения (2.4) суммы вида $\nu(\lambda)$ образуют схемы серий. В теореме 1 статьи [14] показано, в каких случаях из слабой сходимости распределений серий сумм независимых решетчатых случайных величин к предельному закону следует локальная сходимость. Учитывая лемму 6, (2.4) и (5.3), докажем лемму 7, проверив выполнение условия III теоремы 1 из [14], поскольку более простые условия I и II этой теоремы в нашем случае не выполняются.

Введем необходимые обозначения. Пусть

$$ \begin{equation*} M(\nu^{(i)}(\lambda),d)=\mathbf E \langle (\nu^{(i)}(\lambda))^*d\rangle^2, \qquad i=1, \dots, N, \end{equation*} \notag $$
где $(\nu^{(i)}(\lambda))^*$ обозначает симметризованную случайную величину $\nu^{(i)}(\lambda)$, $\langle x \rangle$ – расстояние от $x$ до ближайшего целого числа, $d$ – вещественное число. Положим
$$ \begin{equation} M_N(d)=\sum_{i=1}^N M(\nu^{(i)}(\lambda),d), \qquad M_N=\inf_{1/4\leqslant d\leqslant 1/2}M_N(d). \end{equation} \tag{5.13} $$
Обозначим также
$$ \begin{equation} W^2(\nu^{(i)}(\lambda),\vartheta)=\sum_{0\leqslant k\leqslant \vartheta} k^2\mathbf P\{(\nu^{(i)}(\lambda))^*=k\}, \qquad i=1, \dots, N, \end{equation} \tag{5.14} $$
$$ \begin{equation} W_N^2(\vartheta)=\sum_{i=1}^N W^2(\nu^{(i)}(\lambda),\vartheta). \end{equation} \tag{5.15} $$

Проверяемое условие состоит в том, что $M_N\to \infty$ и существует положительное число $\upsilon<1/2$ такое, что

$$ \begin{equation} b(\lambda)\sqrt{N}=O(W_N(M_N^\upsilon)). \end{equation} \tag{5.16} $$

Согласно [14; лемма 1] при $i=1, \dots, N$

$$ \begin{equation} D(\nu^{(i)}(\lambda),d)\leqslant M(\nu^{(i)}(\lambda),d)\leqslant 4D(\nu^{(i)}(\lambda),d), \end{equation} \tag{5.17} $$
где
$$ \begin{equation*} D(\nu^{(i)}(\lambda),d)=\inf_{a\in R}\mathbf E \langle (\nu^{(i)}(\lambda)-a)d\rangle^2. \end{equation*} \notag $$

Случайная величина $\nu^{(i)}(\lambda)$ равна числу частиц, существовавших в начинающемся с одной частицы ветвящемся процессе $G_i(\lambda)$ до его вырождения. Поэтому все значения $\nu^{(i)}(\lambda)$ с положительными вероятностями являются натуральными числами. Расстояние от $(\nu^i(\lambda)-a)d$ при любых $a$ и $d$ до ближайшего целого не превосходит единицы, следовательно,

$$ \begin{equation} D(\nu^{(i)}(\lambda),d)\leqslant 1. \end{equation} \tag{5.18} $$
С другой стороны, в [14; лемма 2] доказано, что при $1/4\leqslant d\leqslant 1/2$
$$ \begin{equation*} D(\nu^{(i)}(\lambda),d)\geqslant \frac{1}{4}|d|^2\sum_{k=1}^\infty \min \bigl(\mathbf P\{\nu^{(i)}(\lambda)=k\},\, \mathbf P\{\nu^{(i)}(\lambda)=k+1\}\bigr). \end{equation*} \notag $$
Таким образом, при $\lambda \to 1$
$$ \begin{equation*} D(\nu^{(i)}(\lambda),d) > \frac{1}{64}p_1(\lambda)p_0(\lambda)\to \frac{1}{64}p_0p_1>0. \end{equation*} \notag $$
Отсюда и из (5.18) получаем
$$ \begin{equation*} 0<C_{14}\leqslant D(\nu^{(i)}(\lambda),d)\leqslant 1. \end{equation*} \notag $$
Из этих неравенств и из (5.13), (5.17) вытекают оценки
$$ \begin{equation} C_{14}N\leqslant M_N\leqslant 4N. \end{equation} \tag{5.19} $$
Это значит, что $M_N\to \infty$, и осталось проверить (5.16).

Из (5.14) получаем, что

$$ \begin{equation} \begin{aligned} \, \notag W^2(\nu^{(1)}(\lambda),M_N^\upsilon) &=2\sum_{0\leqslant k\leqslant M_N^\upsilon} k^2\mathbf P\{\nu^{(1)}(\lambda)-\nu^{(2)}(\lambda)=k\} \\ \notag &=\mathbf D\bigl(\nu^{(1)}(\lambda)-\nu^{(2)}(\lambda)\bigr)-2\sum_{k>M_N^\upsilon} k^2\mathbf P\{\nu^{(1)}(\lambda)-\nu^{(2)}(\lambda)=k\} \\ \notag &\geqslant 2\biggl(\mathbf D \nu^{(1)}(\lambda)-M_N^{-2\upsilon}\sum_{k=0}^\infty k^4\mathbf P\{\nu^{(1)}(\lambda)-\nu^{(2)}(\lambda)=k\}\biggr) \\ & =2\bigl(b^2(\lambda)-M_N^{-2\upsilon}\mathbf E (\nu^{(1)}(\lambda)-\nu^{(2)}(\lambda))^4\bigr). \end{aligned} \end{equation} \tag{5.20} $$
По неравенству Гёльдера
$$ \begin{equation} \mathbf E \bigl((\nu^{(1)}(\lambda))^2(\nu^{(2)}(\lambda))^2\bigr)\leqslant \bigl(\mathbf E (\nu^{(1)}(\lambda))^4\bigr)^{1/2}\bigl(\mathbf E (\nu^{(2)}(\lambda))^4\bigr)^{1/2}. \end{equation} \tag{5.21} $$
Используя (5.21), нетрудно получить, что
$$ \begin{equation*} \mathbf E (\nu^{(1)}(\lambda)-\nu^{(2)}(\lambda))^4<8\mathbf E (\nu^{(1)}(\lambda))^4, \end{equation*} \notag $$
поэтому из (5.20) вытекает
$$ \begin{equation} W^2(\nu^{(1)}(\lambda),M_N^\upsilon)\geqslant 2(b^2(\lambda)-8M_N^{-2\upsilon}\mathbf E (\nu^{(1)}(\lambda))^4). \end{equation} \tag{5.22} $$
Полагая $\rho =4-\tau+\delta$ в (5.7) и проводя прямые вычисления, подобные тому, как были найдены соотношения (5.3), (5.9), (5.10), находим, что
$$ \begin{equation} \mathbf E (\nu^{(1)}(\lambda))^4=O\biggl (\frac{1}{(1-\lambda)^{4-\tau+\delta}}\biggl (\frac{n}{N}\biggr )^7\biggr ). \end{equation} \tag{5.23} $$
Объединяя (5.8), (5.19), (5.22), (5.23) и учитывая (2.13), видим, что при достаточно малом $\delta>0$
$$ \begin{equation} W^2(\nu^{(1)}(\lambda),M_N^\upsilon)\geqslant C_{15}b^2(\lambda), \end{equation} \tag{5.24} $$
поэтому из (5.15) вытекает (5.16).

Лемма 7 доказана.

§ 6. Предельное поведение $\nu_r(\lambda)$

Асимптотику $\nu_r(\lambda)$ рассмотрим, следуя схеме рассуждений из § 5. Пусть $\Psi_\nu^{(r)}(t)$ обозначает характеристическую функцию случайной величины $(\nu_r(\lambda)-Na(\lambda))/(b(\lambda)\sqrt{N})$.

Лемма 8. При выполнении условий любой из теорем 13 $\Psi_\nu^{(r)}(t)\to e^{-t^2/2}$. Это утверждение остается справедливым в условиях теоремы 1, если $r$ заменить на $r-1$ или $r+1$.

Доказательство. При выполнении условий теорем 1 и 2 лемма 8 доказывается так же, как лемма 1 в [6; гл. 2, п. 4], при этом учитываются леммы 24.

Пусть выполнены условия теоремы 3. Обозначим $\varphi_r^{(1)}(t)$ характеристическую функцию случайной величины $\nu_r^{(1)}(\lambda)$. Из (3.2) следует, что

$$ \begin{equation*} \varphi_r^{(1)}(t)=\frac{\varphi_\nu^{(1)}(t)-\sum_{k=0}^\infty \mathbf P\{\nu^{(1)}(\lambda)=r+k+1\}\exp \{it(r+k+1)\}}{1-P_r}. \end{equation*} \notag $$
Поэтому, используя (2.4), (5.3) и лемму 6, находим, что для любого фиксированного $t$
$$ \begin{equation} \begin{aligned} \, \notag \Psi_\nu^{(r)}(t) &=\exp \biggl \{-\frac{it(N+n)}{b(\lambda)\sqrt{N}}\biggr \}(1-P_r)^{-N} \biggl (\varphi_\nu^{(1)}\biggl (\frac{t}{b(\lambda)\sqrt{N}}\biggr ) \\ \notag &\qquad -\sum_{k=0}^\infty \mathbf P\{\nu^{(1)}(\lambda)=r+k+1\}\exp \biggl \{\frac{it(r+k+1)}{b(\lambda)\sqrt{N}}\biggr \}\biggr )^N \\ &=e^{-t^2/2}\biggl (\frac{1-(1+o(1))\Sigma (\nu^{(1)}(\lambda),t)}{1-P_r}\biggr )^N (1+o(1)), \end{aligned} \end{equation} \tag{6.1} $$
где
$$ \begin{equation} \Sigma (\nu^{(1)}(\lambda),t)=\sum_{k=0}^\infty \mathbf P\{\nu^{(1)}(\lambda)=r\,{+}\,k\,{+}\,1\}\exp \biggl \{\frac{it(r+k+1)}{b(\lambda)\sqrt{N}}\biggr \}=P_r\,{+}\,S(t,r) \end{equation} \tag{6.2} $$
и, поскольку $|e^{ix}-1|\leqslant |x|$,
$$ \begin{equation} |S(t,r)|\leqslant \frac{|t|}{b(\lambda)\sqrt{N}}\sum_{k=0}^\infty (r+k+1)\mathbf P\{\nu^{(1)}(\lambda)=r+k+1\}. \end{equation} \tag{6.3} $$
Из (6.1) и (6.2) ясно, что для доказательства леммы 8 достаточно проверить соотношение
$$ \begin{equation} S(t,r)=o(N^{-1}). \end{equation} \tag{6.4} $$

Аналогично тому, как было найдено (4.13), выводим

$$ \begin{equation} \sum_{k=0}^\infty (r+k+1)\mathbf P\{\nu^{(1)}(\lambda)=r+k+1\} \sim \frac{g(0)}{B_r}\int_r^\infty e^{-y\beta}\,dy=\frac{g(0)}{\beta B_r}e^{-r\beta}. \end{equation} \tag{6.5} $$
Из (5.8), (6.3) и (6.5) мы видим, что если
$$ \begin{equation} \frac{N^2}{n\sqrt{n}\beta B_r}e^{-r\beta}\to 0, \end{equation} \tag{6.6} $$
то справедливо (6.4). Согласно (2.15) $N\,{\leqslant}\, C_{16}r\beta e^{r\beta}B_r$, поэтому, учитывая (2.6), условие $N/n\to 0$, а также (2.14) и соотношение $r/\sqrt{n}\to 0$ (иначе (2.15) было бы невозможно), легко установить справедливость (6.6) и вместе с ним (6.4).

Лемма 8 доказана.

Лемма 9. Пусть выполнены условия любой из теорем 13. Тогда для натуральных $k$ равномерно относительно $(k-N-n)/(b(\lambda)\sqrt{N})$ в любом фиксированном конечном интервале

$$ \begin{equation*} \mathbf P\{\nu_r(\lambda)=k\}=\frac{1+o(1)}{b(\lambda)\sqrt{2\pi N}}\exp \biggl \{-\frac{(k-N-n)^2}{2b^2(\lambda)N}\biggr \}. \end{equation*} \notag $$
Это утверждение остается справедливым в условиях теоремы 1, если $r$ заменить на $r-1$ или $r+1$.

Доказательство. Если $n/N\leqslant C_2<\infty$, то доказательство леммы 9 повторяет доказательство леммы 2 из [6; гл. 2, п. 4]. При выполнении условий теоремы 3 будем следовать доказательству леммы 7, в котором $\nu^{(i)}(\lambda)$ заменим на $\nu_r^{(i)}(\lambda)$, $i=1, \dots, N$. В частности, как и в (5.13), введем обозначения
$$ \begin{equation*} M_N^{(r)}(d)=\sum_{i=1}^N M(\nu_r^{(i)}(\lambda),d), \qquad M_N^{(r)}=\inf_{1/4\leqslant d\leqslant1/2} M_N^{(r)}(d). \end{equation*} \notag $$
Следуя доказательству (5.19), легко убедиться, что
$$ \begin{equation} C_{17}N\leqslant M_N^{(r)}\leqslant 4N, \end{equation} \tag{6.7} $$
поэтому $M_N^{(r)}\to \infty$. Для завершения доказательства леммы 9 теперь достаточно проверить справедливость аналога (5.16) для рассматриваемого случая.

Оценим сначала $\mathbf D \nu_r^{(1)}(\lambda)$. Из (3.2), (3.3) и (5.3) следует, что

$$ \begin{equation} \mathbf E \nu_r^{(1)}(\lambda)=\frac{a(\lambda)-\sum_{k>r} k\mathbf P\{\nu^{(1)}(\lambda)=k\}}{1-P_r}. \end{equation} \tag{6.8} $$
Используя (2.4)(2.6), (2.14), (2.15), (5.3), (6.5) и лемму 5, из (6.8) получаем
$$ \begin{equation} \mathbf E \nu_r^{(1)}(\lambda)\sim a(\lambda). \end{equation} \tag{6.9} $$

Далее рассмотрим

$$ \begin{equation} \mathbf E (\nu_r^{(1)}(\lambda))^2=\frac{\mathbf E (\nu^{(1)}(\lambda))^2-\sum_{k>r} k^2\mathbf P\{\nu^{(1)}(\lambda)=k\}}{1-P_r}. \end{equation} \tag{6.10} $$
Как и при получении (6.5), находим, что
$$ \begin{equation} \sum_{k>r} k^2\mathbf P\{\nu^{(1)}(\lambda)=k\}\sim \frac{rg(0)}{\beta B_r}e^{-r\beta}. \end{equation} \tag{6.11} $$
Из (2.5), (2.6), (2.14), (2.15) и (6.11) получаем
$$ \begin{equation*} \sum_{k>r} k^2\mathbf P\{\nu^{(1)}(\lambda)=k\}=o(1), \end{equation*} \notag $$
поэтому из (2.4), (5.3), (5.8), (6.9), (6.10) и леммы 5 следуют соотношения
$$ \begin{equation} \mathbf E (\nu_r^{(1)}(\lambda))^2\sim \mathbf E (\nu^{(1)}(\lambda))^2, \qquad\mathbf D \nu_r^{(1)}(\lambda)\sim b^2(\lambda). \end{equation} \tag{6.12} $$
Таким же способом мы можем оценить и
$$ \begin{equation} \mathbf E (\nu_r^{(1)}(\lambda))^4=\frac{\mathbf E (\nu^{(1)}(\lambda))^4-\sum_{k>r} k^4\mathbf P\{\nu^{(1)}(\lambda)=k\}}{1-P_r}. \end{equation} \tag{6.13} $$
Поскольку
$$ \begin{equation*} \sum_{k>r} k^4\mathbf P\{\nu^{(1)}(\lambda)=k\} \sim \frac{g(0)}{B_r}\int_r^\infty y^3e^{-y\beta}\,dy =\frac{g(0)r^3}{\beta B_r}e^{-r\beta}(1+o(1)), \end{equation*} \notag $$
с помощью (2.5), (2.14), (2.15) находим, что
$$ \begin{equation*} \sum_{k>r} k^4\mathbf P\{\nu^{(1)}(\lambda)=k\}=o(1). \end{equation*} \notag $$
Отсюда с учетом (6.13) и леммы 5 очевидным образом получаем
$$ \begin{equation} \mathbf E (\nu_r^{(1)}(\lambda))^4\sim \mathbf E (\nu^{(1)}(\lambda))^4. \end{equation} \tag{6.14} $$
Полагая $M_N^{(r)}$ вместо $M_N$ в (5.16) и учитывая (5.22), (6.7), (6.12), (6.14), получаем оценку, аналогичную (5.24),
$$ \begin{equation*} W^2\bigl(\nu_r^{(1)}(\lambda),(M_N^{(r)})^\upsilon \bigr)\geqslant C_{19}\ D\nu_r^{(1)}(\lambda). \end{equation*} \notag $$
Отсюда в силу (5.15) следует равенство
$$ \begin{equation*} \sqrt{\ D\nu_r^{(1)}(\lambda){N}}=O\bigl(W_N((M_N^{(r)})^\upsilon)\bigr). \end{equation*} \notag $$

Лемма 9 доказана.

§ 7. Доказательства теорем

Из лемм 7 и 9 следует, что во всех рассматриваемых случаях

$$ \begin{equation} \frac{\mathbf P\{\nu_r(\lambda)=N+n\}}{\mathbf P\{\nu(\lambda)=N+n\}}=1+o(1). \end{equation} \tag{7.1} $$

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

$$ \begin{equation*} \mathbf P\{\nu_{\max}\leqslant r-1\}\to 0, \qquad \mathbf P\{\nu_{\max}\leqslant r\}\to e^{-\gamma}, \qquad \mathbf P\{\nu_{\max}\leqslant r+1\}\to 1. \end{equation*} \notag $$
Отсюда очевидным образом следуют утверждения теоремы 1.

Доказательство теоремы 2 состоит в объединении утверждений лемм 1, 4 и (7.1). Так же просто доказывается и теорема 3, если использовать леммы 1, 5 и (7.1).

Благодарность

Автор выражает глубокую благодарность рецензенту за полезные и конструктивные замечания.

Список литературы

1. Ю. Л. Павлов, “Условные конфигурационные графы со случайным параметром степенного распределения степеней”, Матем. сб., 209:2 (2018), 120–137  mathnet  crossref  mathscinet  zmath; англ. пер.: Yu. L. Pavlov, “Conditional configuration graphs with discrete power-law distribution of vertex degrees”, Sb. Math., 209:2 (2018), 258–275  crossref  adsnasa
2. B. Bollobás, “A probabilistic proof of an asymptotic formula for the number of labelled regular graphs”, European J. Combin., 1:4 (1980), 311–316  crossref  mathscinet  zmath
3. R. van der Hofstad, Random graphs and complex networks, v. 1, Camb. Ser. Stat. Probab. Math., 43, Cambridge Univ. Press, Cambridge, 2017, xvi+321 pp.  crossref  mathscinet  zmath
4. R. Hofstad, Random graphs and complex networks, v. 2, Camb. Ser. Stat. Probab. Math., Cambridge Univ. Press, Cambridge (to appear); 2021, xx+510 pp. https://www.win.tue.nl/~rhofstad/
5. H. Reittu, I. Norros, “On the power-law random graph model of massive data networks”, Performance Evaluation, 55:1-2 (2004), 3–23  crossref
6. Ю. Л. Павлов, Случайные леса, КарНЦ РАН, Петрозаводск, 1996, 256 с.; англ. пер.: Yu. L. Pavlov, Random forests, VSP, Utrecht, 2000, 122 с.  crossref
7. Н. И. Казимиров, Ю. Л. Павлов, “Одно замечание о лесах Гальтона–Ватсона”, Дискрет. матем., 12:1 (2000), 47–59  mathnet  crossref  mathscinet  zmath; англ. пер.: N. I. Kazimirov, Yu. L. Pavlov, “A remark on Galton–Watson forests”, Discrete Math. Appl., 10:1 (2000), 49–62  crossref
8. В. М. Золотарев, Одномерные устойчивые распределения, Наука, М., 1983, 304 с.  mathscinet  zmath; англ. пер.: V. M. Zolotarev, One-dimensional stable distributions, Transl. Math. Monogr., 65, Amer. Math. Soc., Providence, RI, 1986, x+284 с.  crossref  mathscinet  zmath
9. Ю. Л. Павлов, “Предельные распределения числа деревьев заданного объема в случайном лесе”, Дискрет. матем., 8:2 (1996), 31–47  mathnet  crossref  mathscinet  zmath; англ. пер.: Yu. L. Pavlov, “Limit distribution of the number of trees of given size in a random forest”, Discrete Math. Appl., 6:2 (1996), 117–133  crossref
10. В. Ф. Колчин, Случайные отображения, Наука, М., 1984, 207 с.  mathscinet  zmath; англ. пер.: V. F. Kolchin, Random mappings, Transl. Ser. Math. Engrg., Optimization Software, Inc., Publications Division, New York, 1986, xiv+207 с.  mathscinet  zmath
11. В. Феллер, Введение в теорию вероятностей и ее приложения, т. 2, Мир, М., 1984, 752 с.  mathscinet  zmath; пер. с англ.: W. Feller, An introduction to probability theory and its applications, т. 2, 2nd ed., John Wiley & Sons, Inc., New York–London–Sydney, 1971, xxiv+669 с.  mathscinet  zmath  adsnasa
12. И. А. Ибрагимов, Ю. В. Линник, Независимые и стационарно связанные величины, Наука, М., 1965, 524 с.  mathscinet  zmath; англ. пер.: I. A. Ibragimov, Yu. V. Linnik, Independent and stationary sequences of random variables, Wolters-Noordhoff Publishing, Groningen, 1971, 443 с.  mathscinet  zmath
13. Г. Бэйтмен, А. Эрдейи, Высшие трансцендентные функции. Функции Бесселя, функции параболического цилиндра, ортогональные многочлены, Наука, М., 1966, 295 с.  mathscinet  zmath; пер. с англ.: A. Erdélyi, W. Magnus, F. Oberhettinger, F. G. Tricomi, Higher transcendental functions, Based, in part, on notes left by H. Bateman, т. 2, McGraw-Hill Book Company, Inc., New York–Toronto–London, 1953, xvii+396 с.  mathscinet  zmath  adsnasa
14. А. Б. Мухин, “Локальные предельные теоремы для решетчатых случайных величин”, Теория вероятн. и ее примен., 36:4 (1991), 660–674  mathnet  mathscinet  zmath; англ. пер.: A. B. Mukhin, “Local limit theorems for lattice random variables”, Theory Probab. Appl., 36:4 (1992), 698–713  crossref

Образец цитирования: Ю. Л. Павлов, “Максимальное дерево случайного леса в конфигурационном графе”, Матем. сб., 212:9 (2021), 146–163; Yu. L. Pavlov, “The maximum tree of a random forest in the configuration graph”, Sb. Math., 212:9 (2021), 1329–1346
Цитирование в формате AMSBIB
\RBibitem{Pav21}
\by Ю.~Л.~Павлов
\paper Максимальное дерево случайного леса в конфигурационном графе
\jour Матем. сб.
\yr 2021
\vol 212
\issue 9
\pages 146--163
\mathnet{http://mi.mathnet.ru/sm9481}
\crossref{https://doi.org/10.4213/sm9481}
\adsnasa{https://adsabs.harvard.edu/cgi-bin/bib_query?2021SbMat.212.1329P}
\elib{https://elibrary.ru/item.asp?id=47540482}
\transl
\by Yu.~L.~Pavlov
\paper The maximum tree of a~random forest in the configuration graph
\jour Sb. Math.
\yr 2021
\vol 212
\issue 9
\pages 1329--1346
\crossref{https://doi.org/10.1070/SM9481}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000718596400001}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85120772460}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/sm9481
  • https://doi.org/10.4213/sm9481
  • https://www.mathnet.ru/rus/sm/v212/i9/p146
  • Эта публикация цитируется в следующих 9 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Математический сборник Sbornik: Mathematics
    Статистика просмотров:
    Страница аннотации:358
    PDF русской версии:60
    PDF английской версии:28
    HTML русской версии:136
    Список литературы:63
    Первая страница:10
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024