RUS  ENG
Полная версия
ЖУРНАЛЫ // Теория вероятностей и ее применения // Архив

Теория вероятн. и ее примен., 1993, том 38, выпуск 2, страницы 273–287 (Mi tvp3940)

Эта публикация цитируется в 3 статьях

Распределение расстояния до корня минимального поддерева, содержащего все вершины данной высоты

В. А. Ватутин

Институт математики им. В. А. Стеклова РАН, Москва, Россия

Аннотация: Пусть $h(s)$ – производящая функция числа непосредственных потомков в ветвящемся процессе Гальтона–Ватсона, $\mu(t)$ – число частиц в этом процессе в момент $t$, $\mu$ – общее число частиц, появившихся в процессе за время его эволюции, a $\tau(t)$ – расстояние до ближайшего общего предка всех частиц, существующих в момент $t$. В предположении, что
$$ h'(1)=1, \qquad 0<B=h''(1)<\infty, $$
а параметры $N$, $t\to\infty$ так, что $t(B/N)^{1/2}\to\beta\in(0,\infty)$, найден предел
$$ \lim\mathbf{P}\{t^{-1}\tau(t)\le a\mid\mu(t)>0,\nu=N\}=I_\beta(a),\qquad 0<a<1. $$
Полученный результат используется для нахождения предельного (при $N\to\infty$) распределения расстояния до корня минимального поддерева содержащего все вершины данной высоты, в случае, когда дерево выбирается случайно и равновероятно либо из множества всех плоских деревьев с висячим корнем и $N$ некорневыми вершинами, либо из множества всех помеченных корневых деревьев с $N$ вершинами.

Ключевые слова: ветвящийся процесс Гальтона–Ватсона, предельные теоремы, расстояние до ближайшего общего предка, плоское дерево с висячем корнем, помеченные деревья.

Поступила в редакцию: 26.08.1991


 Англоязычная версия: Theory of Probability and its Applications, 1993, 38:2, 330–341

Реферативные базы данных:


© МИАН, 2024