3
$\begingroup$

A Galton-Watson tree is the family tree of a Galton-Watson process. Let $T_n$ denote a Galton-Watson tree conditioned on total population size $n$. The time of extinction is its height $H(T_n)$ and its diameter $D(T_n)$ is the length of a longest path in the tree. It is known that for certain offspring distributions the ratio $\mathbb{E}[D(T_n)] / \mathbb{E}[H(T_n)]$ converges to $4/3$. The same property is expected to hold in a more general context, as argued heuristically by Aldous in the paper "The continuum random tree II: an overview" (1991).

I would like to know if a formal proof of this is known in the case of an arbitrary offspring distribution with expected value 1 and finite nonzero variance.

$\endgroup$

1 Answer 1

2
$\begingroup$

Yes, it is known. By results of Haas & Miermont [http://arxiv.org/pdf/1003.3632v3.pdf - Lemma 33] (see also Addario--Berry, Devroy & Janson [http://arxiv.org/pdf/1011.4121v1.pdf - Theorem 1.2 - for stronger bounds], $ H(T_n)/\sqrt{n}$ is bounded in $L^2$, and so is $D(T_n)/\sqrt{n}$ because $D(T_n) \leq 2 H(T_n)$. Since $H(T_n)/\sqrt{n}$ and $D(T_n)/\sqrt{n}$ converge in distribution respectively to the height and diameter of the Brownian CRT times the same constant, it follows that $\mathbb{E}[H(T_n)]/\mathbb{E}[D(T_n)]$ converges towards $\mathbb{E}[H]/\mathbb{E}[D]$, where $H$ is the height of the Brownian CRT and $D$ its diameter.

Since it is known that $\mathbb{E}[H(T_n)]/\mathbb{E}[D(T_n)]$ converges towards $4/3$ for some offspring distributions, we get that $\mathbb{E}[H]/\mathbb{E}[D]=4/3$, implying that $\mathbb{E}[H(T_n)]/\mathbb{E}[D(T_n)]$ converges actually towards $4/3$ for all offspring distributions (critical with finite positive variance).

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.