Эта публикация цитируется в
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