4
$\begingroup$

I am currently pursuing my PhD degree and in my research I came across a family of random trees. I need to prove a logarithmic asymptotic bound for the heights of such trees as their size grows. I found a paper "A note on the growth of random trees" by J. D. Biggins, D. R. Grey describing an approach using Crump-Mode-Jagers branching processes. The basis for this approach is Theorem 5 from "The First Birth Problem for an Age-dependent Branching Process" by J.F.C. Kingman (http://www.jstor.org/stable/2959121) and Theorem 2 from "The growth and spread of the general branching random walk" by J.D.Biggins (http://biggins.staff.shef.ac.uk/growth.html).

The trees I am interested in are generated as follows. Let $\Gamma$ be a fixed discrete probability distribution on a finite set of natural numbers.

1) Each node $v \in V(T_i)$ of a tree $T_i$ has an assosiated weight $w^{(i)}(v)$.

2) $V(T_0) = \{ v_0 \}$ with $w^{(0)}(v_0) = 1$.

3) For $i = 0, \dots, n-1$ the tree $T_{i+1}$ is constructed from $T_i$ by adding $\eta_i$ new children to a random node $\xi_i$, where $\eta_i \in \Gamma$ and the probability to pick a specific $v \in V_i$ is proportional to its weight, that is: $$ Prob\left(\xi_i = v\right) = \frac{w^{(i)}(v)}{\sum_{x \in V(T_i)} w^{(i)}(x)}. $$ For a node $u \in V_{i+1}$ the weight is defined in the following way: $$ w^{(i + 1)}(u) = \begin{cases} w^{(i)}(u) + 1, &\text{if $u = \xi_i$;}\\ 1, &\text{if $u \in V_{i + 1} \setminus V_i$;}\\ w^{(i)}(u), &\text{otherwise.} \end{cases} $$

This tree can be defined by a Crump-Mode-Jagers process. The process starts with a single ancestor, which produces children. Each of the children behaves in the same way as the ancestor independently. The births of children of the initial ancestor are described in the following way:

1) Childrens are born in batches. The size of each batch is distributed as $\Gamma$.

2) The ith interarrival time is an exponential r.v. with parameter $i$. So the intervals after each birth tend to shrink.

More precisely, the number of children of initial ancestor $$ Z_1(t) = \begin{cases} 0, &\text{if $t < \tau_1$;}\\ \eta_1, &\text{if $\tau_1 \le t < \tau_1 + \tau_2$;}\\ \dots &\dots\\ \eta_1 + \dots + \eta_n, &\text{if $\tau_1 + \dots + \tau_n \le t < \tau_1 + \dots + \tau_n + \tau_{n + 1}$;}\\ \dots &\dots\\ \end{cases} $$ where $\tau_i$ is an exponential r.v. with parameter $i$ and $\eta_i \sim \Gamma$.

My confusion stems from the fact that there seem to be two versions of the definition of a point process. One that allows only increments of size $1$ (simple point process) and another that allows any positive integer increments, which leads to multypoints of the point process. It says in the paper "A note on the growth of random trees" that we add new vertices one by one (which gives essentially a simple point process), but in an earlier work by Biggins he used a general point process.

It seems that Kingman's theorem can be applied without any problems, but I am not sure about Biggins' theorem, because it looks like it is limited to renewal processes (it looks like there are no multypoints allowed for the point process $Z_1$ and it uses renewal theory for proofs). Can I apply these theorems for my case? If not, are there any results that I can use in my case to get a logarithmic bound on the height of $T_n$ as $n \to \infty$?

$\endgroup$

0

Your Answer

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