| Математические заметки |
|
|
|
|
|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях) О предельном распределении числа вершин в слоях дерева процесса Гальтона–Ватсона Ю. Л. Павлов Карельский научный центр РАН, г. Петрозаводск
Англоязычная версия:
Mathematical Notes, 2024, Volume 116, Issue 3, Pages DOI: https://doi.org/10.1134/S0001434624090104 
Реферативные базы данных:
 1. ВведениеВ [1; гл. II, § 5] рассматривалось множество $T_n$ всех корневых деревьев с $n$ вершинами, корни которых обозначены единицей, а некорневые вершины занумерованы числами $2, \dots, n$. Хорошо известно, что число различных таких деревьев равно $n^{n-2}$. На $T_n$ задавалось равномерное распределение вероятностей. Высотой вершины дерева называется число ребер, образующих путь от корня к этой вершине. Множество вершин высоты $t$, $t=0,1, \dots, n-1$, назовем $t$-м слоем дерева. Обозначим $\mu (t,T_n)$ число вершин $t$-го слоя. В [1] изучалось предельное поведение числа вершин в слоях случайного дерева из $T_n$ при $n, t \to \infty$. В частности, для нижних слоев было доказано следующее утверждение. Доказательство этой теоремы основано на связи случайных деревьев и ветвящихся процессов Гальтона–Ватсона. Пусть $\mu (t)$ означает число частиц поколения $t$, $t=0,1, \dots$, начинающегося с одной частицы критического ветвящегося процесса Гальтона–Ватсона. Сам процесс мы также обозначим $\mu (t)$, поскольку такой двойной смысл этого выражения далее не приводит к недоразумениям. Пусть $\nu$ означает общее число частиц, существовавших в процессе $\mu (t)$ до его вырождения. В [1; гл. II, § 3] получен такой результат Теорема 2. Если в критическом ветвящемся процессе $\mu (t)$ дисперсия числа непосредственных потомков одной частицы равна $B>0$, то при $n,t\to \infty$, $t/\sqrt{n}\to 0$, для любого фиксированного $x>0$ Рассмотрим подмножество траекторий процесса $\mu (t)$, содержащих ровно $n$ частиц. Это подмножество вместе с распределением вероятностей, естественным образом генерируемом на нем процессом, образует случайное дерево с $n$ вершинами. Такие случайные деревья называются деревьями Гальтона–Ватсона, образованными процессом $\mu (t)$. В [1; гл. II] показано, что для появления на $T_n$ равномерного распределения вероятностей, в качестве $\mu (t)$ достаточно взять процесс, в котором число непосредственных потомков каждой частицы имеет распределение Пуассона с параметром, равным единице. В этом случае, как легко видеть, теорема 1 является очевидным следствием теоремы 2. В настоящей статье аналогичная задача решается для деревьев Гальтона–Ватсона, образованных критическим ветвящимся процессом, в котором распределение числа прямых потомков каждой частицы имеет бесконечную дисперсию. В следующем разделе описываются свойства рассматриваемых деревьев и формулируется основной результат статьи (теорема 3) о предельном поведении числа вершин в нижних слоях дерева. В разделе 3 получены вспомогательные результаты, с помощью которых в разделе 4 доказывается теорема 4, являющаяся аналогом теоремы 2 для случая с бесконечной дисперсией. А утверждение теоремы 3 вытекает из теоремы 4 как простое следствие. 2. Постановка задачи и формулировка основного результатаРассмотрим дерево Гальтона–Ватсона, образованное начинающимся с одной частицы критическим ветвящимся процессом $\mu_\tau(t)$, в котором случайная величина $\xi$, равная числу непосредственных потомков каждой частицы, имеет распределение
$$
\begin{equation}
\mathbf P\{\xi =k\}=\frac{h(1/(k+1))}{(k+1)^\tau}, \qquad k=0,1,2, \dots, \quad \tau \in (2,3),
\end{equation}
\tag{2.1}
$$
где $h(x)$ – медленно меняющаяся в нуле функция, которая при $x\geqslant 1$ принимает только положительные значения. Выбор распределения (2.1) для потомства частиц процесса связан с успешным использованием теории ветвящихся процессов Гальтона–Ватсона при изучении структуры и динамики случайных графов, предназначенных для моделирования современных сетей коммуникаций, подробнее об этом; см., например, [2] и использованные там источники. Поскольку процесс $\mu_\tau (t)$ критический, справедливо равенство $\mathbf E\xi=1$. Из (2.1) следует, что распределение $\xi$ имеет бесконечную дисперсию. Обозначим $U(z)$ производящую функцию распределения (2.1). Далее нам потребуется следующее утверждение об этой функции. Доказательство. Нетрудно видеть, что
$$
\begin{equation}
\frac{1-U(z)}{1-z}=\sum_{j=0}^\infty \mathbf P\{\xi> j\}z^j.
\end{equation}
\tag{2.3}
$$
Поскольку из (2.3) получаем, что где
Обозначим $F_\xi (x)$ функцию распределения случайной величины $\xi$ с распределением (2.1). Из (2.1) и [3; гл. VIII, § 9, теорема 1] следует, что при $x\to \infty$
$$
\begin{equation}
F_\xi (x)=1-\frac{h(1/x)}{(\tau-1)x^{\tau-1}}(1+o(1)),
\end{equation}
\tag{2.6}
$$
а при $r\to \infty$
$$
\begin{equation*}
\sum_{j=r+1}^\infty \mathbf P\{\xi >j\}\sim \frac{h(1/r)}{(\tau-1)(\tau-2)r^{\tau-2}}.
\end{equation*}
\notag
$$
Отсюда, из (2.5) и [3; гл. XIII, § 5, теорема 5] находим, что при $z\to 1$
$$
\begin{equation*}
\Psi (z)\sim \frac{h(1-z)}{(\tau-1)(\tau-2)(1-z)^{3-\tau}}.
\end{equation*}
\notag
$$
Из этого соотношения и (2.4) вытекает (2.2). Обозначим
$$
\begin{equation}
\varphi (u)=1+\frac{iu}{(1+(-iu)^{\tau-2})^{1/(\tau-2)}}.
\end{equation}
\tag{2.7}
$$
В теореме 7 статьи [4] показано, что $\varphi (u)$ является характеристической функцией случайной величины с распределением
$$
\begin{equation}
G(x)=1-\frac{\tau-2}{\Gamma (1/(\tau-2))} \int_0^\infty e^{-(x/u)^{\tau-2}} p(u,\tau-2,1)\,du,
\end{equation}
\tag{2.8}
$$
где $\Gamma (1/(\tau-2))$ – значение гамма-функции, а $p(u,\tau-2,1)$ – плотность устойчивого распределения с параметрами $\tau-2$ и $1$. Рассмотрим вероятность $Q(t)=\mathbf P\{\mu_\tau (t)>0\}$. Предельное поведение этой вероятности при $t\to \infty$ для критических процессов, в которых распределение числа прямых потомков частиц имеет бесконечную дисперсию и производящую функцию, представимую в виде (2.2), исследовалось в [5; лемма 2]. Из этой леммы следует, что Пусть $\mathrm{GW}_{n,\tau}$ – случайное дерево Гальтона–Ватсона, имеющее $n$ вершин и образованное процессом $\mu_\tau (t)$, в котором распределение числа прямых потомков частиц задано равенствами (2.1). Пусть также $\mu (t,\mathrm{GW}_{n,\tau})$ означает число вершин высоты $t$ в дереве $\mathrm{GW}_{n,\tau}$. Главным результатом статьи является следующее утверждение. Замечание 1. Известно (см., например, [1; гл. II, § 1, теорема 2], что если распределение числа прямых потомков каждой частицы ветвящегося процесса имеет конечную дисперсию $B>0$, то $Q(t)\sim 2/(Bt)$. Тогда из (2.9) вытекает, что $t/\sqrt{n}\to 0$, следовательно, условие (2.9), в силу теоремы 2, совпадает с оптимальным в случае конечной дисперсии. 3. Вспомогательные утвержденияДокажем две леммы, которые в следующем разделе будут использованы для доказательства теоремы 3. Доказательство. Предположим, что $x/y\to c$, $0<c<\infty$. Тогда, используя определение медленно меняющейся функции, находим, что что противоречит (3.1). Пусть теперь $x/y\to \infty$. В силу известных свойств медленно меняющихся функций при $x>y>0$ и $x\to 0$
$$
\begin{equation*}
\frac{h(x)}{h(y)}\sim \exp \biggl\{\int_y^x \frac{\varepsilon (w)}{w}\,dw\biggr\},
\end{equation*}
\notag
$$
где $\varepsilon (w)\to 0$ при $w\to 0$. Тогда для любого $\varepsilon >0$ при достаточно малых $x$
$$
\begin{equation*}
\exp \biggl\{\int_y^x \frac{\varepsilon (w)}{w}\,dw\biggr \} \geqslant \exp\biggl\{-\varepsilon \int_y^x\frac{dw}{w}\biggr\}\geqslant \biggl(\frac{x}{y}\biggr)^{-\varepsilon}.
\end{equation*}
\notag
$$
Отсюда при достаточно малых $\varepsilon >0$
$$
\begin{equation*}
\frac{x^{\tau-1}h(x)}{y^{\tau-1}h(y)} \geqslant \biggl(\frac{x}{y}\biggr)^{\tau -1-\varepsilon}\to \infty,
\end{equation*}
\notag
$$
и противоречит (3.1). Лемма доказана. Введем последовательность $B_n$, $n=1,2, \dots$, такую, что
$$
\begin{equation}
B_n=\min \biggl\{x>0\colon 1-F_\xi (x) \leqslant \frac 1n\biggr\}.
\end{equation}
\tag{3.2}
$$
Понятно, что $B_n \to \infty$ при $n\to \infty$. Лемма 3. Пусть $n,t\to \infty$ так, что выполнено (2.9). Тогда $B_nQ(t)\to \infty$. Доказательство. Из (2.6), (3.2) и свойств медленно меняющихся функций следует, что при $n\to \infty$
$$
\begin{equation}
\frac{h(1/B_n)}{(\tau-1)B_n^{\tau-1}}\sim \frac{1}{n}.
\end{equation}
\tag{3.3}
$$
В утверждении леммы 2 положим $x=1/B_n$, $y=Q(t)$. Тогда из (3.3) следует, что
$$
\begin{equation*}
\frac{h(1/B_n)}{Q^{\tau-1}h(Q(t))B_n^{\tau-1}}=\frac{h(1/B_n)}{(Q(t)B_n)^{\tau-1}h(Q(t))}\to 0.
\end{equation*}
\notag
$$
Учитывая (2.9), отсюда получаем утверждение леммы 3. 4. Доказательство теоремы 3Обозначим $\nu$ общее число частиц, существовавших в процессе $\mu_\tau (t)$ за все время его эволюции. Ниже формулируется и доказывается теорема 4 о предельном поведении распределения $\mu_\tau (t)$ при условии $\nu =n$ и $n,t\to \infty$. Эта теорема является аналогом теоремы 2 и, как легко видеть, для доказательства теоремы 3 достаточно получить утверждение теоремы 4. Теорема 4. Пусть $n,t\to \infty$ так, что выполнено условие (2.9). Тогда для любого фиксированного $x>0$ Доказательство. Будем следовать идее доказательства теоремы 3 из [1; гл. II, § 3]. Для произвольных положительных $x_1<x_2$ обозначим
В силу (2.9) существует функция $g(n,t)$ такая, что при $n,t\to \infty$ Нам потребуется вспомогательный ветвящийся процесс $G_N$, отличающийся от $\mu_\tau (t)$ только тем, что он начинается с $N>1$ частиц. Обозначим $\nu (G_N)$ общее число частиц процесса $G_N$ за все время его существования. Заметим, что $k_1>1$ при достаточно больших $t$ и cправедливо равенство
$$
\begin{equation}
\begin{aligned} \, \notag &\mathbf P\bigl\{x_1\leqslant Q(t)\mu_\tau(t) \leqslant x_2\mid \nu=n\bigr\} \\ \notag &\qquad=\sum_{k_1\leqslant k\leqslant k_2} \sum_{s=1}^{n-k} \mathbf P\bigl\{\mu_{\tau} (t)=k,\,\nu(t)=s\bigr\} \frac{\mathbf P\{\nu(G_k)=n-s\}}{\mathbf P\{\nu=n\}}, \\ &\qquad =\Sigma_1 (k_1,k_2)+\Sigma_2(k_1,k_2), \end{aligned}
\end{equation}
\tag{4.3}
$$
где $\nu(t)=\mu_\tau (1)+ \dots +\mu_\tau (t-1)$,
$$
\begin{equation*}
\begin{gathered} \, \Sigma_i(k_1,k_2)=\sum_{k_1\leqslant k\leqslant k_2} \sum_{S_i} \mathbf P\bigl\{\mu_{\tau} (t)=k,\,\nu(t)=s\bigr\} \frac{\mathbf P\{\nu(G_k)=n-s\}}{\mathbf P\{\nu=n\}}, \qquad i=1,2, \\ S_1=\bigl\{s\colon 1\leqslant s\leqslant \gamma n\bigr\}, \qquad S_2=\bigl\{s\colon \gamma n<s\leqslant n-k\bigr\}. \end{gathered}
\end{equation*}
\notag
$$
Предельное поведение случайной величины $\nu(G_N)$ исследовано в [6; лемма 2]. Для того, чтобы сформулировать полученный там результат, введем необходимые обозначения. Пусть $p(x)$ означает плотность устойчивого закона распределения с показателем $\tau-1$ и характеристической функцией
$$
\begin{equation*}
f(t)= \exp \biggl\{-c\Gamma (2-\tau)|t|^{\tau-1}\biggl(1-i\frac{t}{|t|}\operatorname{tg}\biggl(\frac{\pi (\tau-1)}{2}\biggr)\biggr)\cos \biggl(\frac{\pi (\tau-1)}{2}\biggr)\biggr\},
\end{equation*}
\notag
$$
где $\Gamma (x)$ – гамма-функция, а константа $c>0$ зависит от медленно меняющейся функции $h(x)$ из распределения (2.1). Если вид этой функции известен, то константу $c$ можно найти, используя [7; формула (2.6.4)]. В [6; лемма 2] показано, что если $N/n\to 0$, то Полагая $N=1$, из (4.4) находим, что Используя (2.9), (4.1), (4.4) и лемму 3, видим, что если $s=o(n)$, то равномерно относительно $k$, $k_1\leqslant k \leqslant k_2$,
$$
\begin{equation*}
\mathbf P\{\nu (G_k)=n-s\}=\frac{kp(0)}{nB_n}(1+o(1)).
\end{equation*}
\notag
$$
Отсюда и из (4.5) получаем, что
$$
\begin{equation*}
\frac{\mathbf P\{\nu(G_k)=n-s\}}{\mathbf P\{\nu=n\}}=k(1+o(1))
\end{equation*}
\notag
$$
равномерно относительно $s\leqslant \gamma n, k_1\leqslant k\leqslant k_2$. Используя это, находим, что
$$
\begin{equation}
\begin{aligned} \, \notag \Sigma_1 (k_1,k_2) &=(1+o(1))\sum_{k_1\leqslant k \leqslant k_2} k \sum_{S_1} \mathbf P\bigl\{\mu_\tau (t)=k,\,\nu(t)=s\bigr\} \\ &=(1+o(1))\biggl(\sum_{k_1\leqslant k\leqslant k_2} k\mathbf P\{\mu_\tau (t)=k\}-\Sigma_3 (k_1,k_2)\biggr), \end{aligned}
\end{equation}
\tag{4.6}
$$
где
$$
\begin{equation}
\Sigma_3(k_1,k_2)=\sum_{k_1\leqslant k\leqslant k_2} k\sum_{S_2} \mathbf P\bigl\{\mu_\tau (t)=k,\,\nu (t)=s\bigr\}.
\end{equation}
\tag{4.7}
$$
Учитывая, что $\mathbf E\nu(t)=t$, и применяя неравенство Чебышева, находим, что
$$
\begin{equation*}
\mathbf P\{\nu(t)>\gamma n\}\leqslant \frac{\mathbf E\nu(t)}{\gamma n}=\frac{t}{\gamma n}.
\end{equation*}
\notag
$$
В силу (4.1), (4.2), (4.7)
$$
\begin{equation}
\Sigma_3(k_1,k_2)\leqslant k_2\mathbf P\{\nu (t)>\gamma n\}\leqslant \frac{x_2t}{Q(t)\gamma n}=\frac{x_2}{g(n,t)}\to 0.
\end{equation}
\tag{4.8}
$$
Если $x=k/Q(t)$, то из (4.1) при $t\to \infty$ получаем
$$
\begin{equation}
k\mathbf P\{\mu_\tau (t)=k\}=x\mathbf P\bigl\{\mu_\tau (t)=k\mid \mu_\tau (t)>0\bigr\}(1+o(1)).
\end{equation}
\tag{4.9}
$$
В [5] рассматривалась асимптотика $\mu_\tau (t)$ при условии $\mu_\tau (t)>0$. Обозначим
$$
\begin{equation}
H_t(x)=\mathbf P\bigl\{Q(t)\mu_\tau (t)<x\mid \mu_\tau (t)>0\bigr\}.
\end{equation}
\tag{4.10}
$$
Из [5; теорема 1 и следствие из нее] вытекает, что при $t\to \infty$ и любом фиксированном $x>0$ где функция распределения $G(x)$ определена в (2.8). Поэтому из (4.9)-(4.11) следует, что
$$
\begin{equation*}
\begin{aligned} \, & \sum_{k_1\leqslant k\leqslant k_2} k\mathbf P\{\mu_\tau (t)=k\} \\ &\qquad =\sum_{x_1\leqslant x\leqslant x_2} x\mathbf P\bigl\{Q(t)\mu_\tau (t)=x\mid \mu_\tau (t)>0\bigr\}(1+o(1)) =\int_{x_1}^{x_2} y\,dG(y)(1+o(1)). \end{aligned}
\end{equation*}
\notag
$$
Отсюда и из (4.6)–(4.8) находим, что при выполнении условий теоремы 4
Докажем теперь, что для любого сколь угодно малого $\varepsilon >0$ и достаточно больших $n,t$ Выберем положительные $w_1<w_2$ так, чтобы
$$
\begin{equation}
l_1=\frac{w_1}{Q(t)}\leqslant k_1, \qquad l_2=\frac{w_2}{Q(t)} \geqslant k_2.
\end{equation}
\tag{4.14}
$$
Из (2.7) следует, как легко видеть, что математическое ожидание случайной величины с распределением $G(x)$ равно единице. Поэтому $w_1$ и $w_2$ можно подобрать так, что Это равенство вместе с (4.12) влечет за собой соотношение
$$
\begin{equation}
\Sigma_1 (l_1,l_2)\to \int_{w_1}^{w_2} y\,dG(y)=1-\frac{\varepsilon}{2}>1-\varepsilon.
\end{equation}
\tag{4.15}
$$
Из (4.3) видно, что
$$
\begin{equation*}
1\geqslant \mathbf P\bigl\{l_1\leqslant \mu_\tau (t)\leqslant l_2\mid \nu=n\bigr\}=\Sigma_1 (l_1,l_2)+\Sigma_2 (l_1,l_2).
\end{equation*}
\notag
$$
Отсюда и, учитывая (4.14),
$$
\begin{equation*}
\Sigma_2 (k_1,k_2)\leqslant \Sigma_2 (l_1,l_2)\leqslant 1-\Sigma_1 (l_1,l_2).
\end{equation*}
\notag
$$
Поэтому при достаточно больших $n,t$ из (4.15) следует (4.13).
Поскольку в (4.1) в качестве $x_1$ можно взять сколь угодно малое положительное число, из (4.3), (4.12), (4.13), (4.15) приходим к утверждению теоремы 4. Автор выражает благодарность рецензенту за ряд полезных замечаний, позволивших существенно улучшить текст и устранить несколько ошибок и опечаток. В частности, он обратил внимание, что возникшее в теореме 3 распределение можно рассматривать как преобразование смещения объема относительно распределения из [5], см., например, [8]. Особая благодарность профессору В. А. Ватутину, рекомендации которого позволили с помощью предложенных им лемм 1–3 доказать теорему 3 при оптимальных условиях. 
Цитирование в формате AMSBIB
\RBibitem{Pav24} |
|
||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|