|
Teoriya Veroyatnostei i ee Primeneniya, 1993, Volume 38, Issue 2, Pages 273–287
(Mi tvp3940)
|
|
|
|
This article is cited in 3 scientific papers (total in 3 papers)
The distribution of the distance to the root of the minimal subtree containing all the vertices of a given height
V. A. Vatutin Steklov Mathematical Institute, Russian Academy of Sciences
Abstract:
Let $h(s)$ be the generating function of the number of direct descendants in a Galton–Watson branching process, $\mu (t)$ the number of particles in the process at time $t$, $\nu$ the total number of particles bornn in the process during its evolution, and let $\tau (t)$ be the distance to the nearest mutual ancestor of all the particles existing at time $t$. Assuming that
$$
h'(1)=1,\qquad 0<B=h''(1)<\infty,
$$
and the parameters $N$, $t\to\infty$ in such a way that $t({B/N})^{1/2}\to\beta\in(0,\infty)$, we find the limit
$$
\lim\mathbf{P}\{t^{-1}\tau(t)\le a\mid\mu(t)>0,\nu=N\}=I_\beta(a),\qquad 0<a<1.
$$
The result obtained is used to find the limiting (as $N\to\infty$) distribution of the distance to the root of the minimal subtree containing all the vertices of a given height in the case where the tree is chosen at random and equiprobably either from the set of all planted plane trees with $N$ nonrooted vertices or from the set of all labelled rooted trees with $N$ vertices.
Keywords:
Galton–Watson branching process, limit theorems, distribution distance to the nearest mutual ancestor, planted plane trees, labelled trees.
Received: 26.08.1991
Citation:
V. A. Vatutin, “The distribution of the distance to the root of the minimal subtree containing all the vertices of a given height”, Teor. Veroyatnost. i Primenen., 38:2 (1993), 273–287; Theory Probab. Appl., 38:2 (1993), 330–341
Linking options:
https://www.mathnet.ru/eng/tvp3940 https://www.mathnet.ru/eng/tvp/v38/i2/p273
|
Statistics & downloads: |
Abstract page: | 220 | Full-text PDF : | 58 | First page: | 9 |
|