Consider the following procedure for generating a random binary tree: Starting with a full binary tree (i.e., each node has either two or no children) we iterate over the leaves and (independently) for each leaf we add two children with probability $\theta(1+d)^{-\gamma}$, where $d$ is the depth of the leaf (the root node has depth $d=0$), $\theta\in (0,1)$, and $\gamma>0$. Repeat this process until none of the leaves have children added to them, at which point we return the tree.

Does this process always terminate (i.e., does it generate a finite binary tree with probability one)? Does it depend on the value of $\gamma$, or even $\theta$?


The expected number of nodes at level $d$ is as $$ 2\frac{\theta}{1^\gamma}\cdot2\frac{\theta}{2^\gamma} \cdots 2\frac{\theta}{d^\gamma} =\frac{(2\theta)^d}{(d!)^\gamma} = \Bigl( \frac{((2\theta)^{1/\gamma})^d}{d!}\Bigr)^\gamma$$ For any positive $\gamma$ the factorial in the denominator will eventually dominate the fraction, so the expected size of each level goes towards zero.

This expectation is also an upper bound for the probability that this particular layer contains at least one node, which is itself an upper bound for the probability that the tree is infinite.

So the tree is infinite with probability 0 and finite with probability 1.

Boundary cases: If $\gamma=0$, then the tree is finite with probability $\min(1, \frac{1-\theta}{\theta})$.
And if $\gamma<0$ and $\theta\ne 0$, then the recipe doesn't make sense at all, as $\theta(1+d)^{-\gamma}$ would not always be in $[0,1]$.

| cite | improve this answer | |
  • $\begingroup$ Thanks! I'm working through this myself, but I think there's a condition missing as the expected number of tree should depend on the "seed" tree. Have you assumed that the seed tree is trivial (a single node)? (This would be fine as the splitting events are independent) $\endgroup$ – MMM Dec 24 '14 at 15:46
  • $\begingroup$ @MMM: Yes, I'm assuming that the initial state is a single node at level 0. $\endgroup$ – hmakholm left over Monica Dec 24 '14 at 15:53
  • $\begingroup$ OK thanks. Stupid question, but I've worked out the expectation for the first couple of depths (via iterated expectation, computing $E(E(N_d\mid N_{d-1}))$ directly using $P(N_{d-1})$. Computing $P(N_{d-1})$ gets annoying quickly though. Could you give me a pointer to how you got your expression? $\endgroup$ – MMM Dec 24 '14 at 16:14
  • $\begingroup$ @MMM: I simply unfolded the recurrence $E(N_{d+1}) = E(N_d)\cdot 2\theta(1+d)^{-\gamma}$, because each node at level $d$ (no matter how many of them there are) has a probability of $\theta(1+d)^{-\gamma}$ to give rise to two nodes on leven $d+1$. (It is not clear to me what you mean by $P(N_d)$ here). $\endgroup$ – hmakholm left over Monica Dec 25 '14 at 0:59
  • $\begingroup$ Alternatively, each of the $2^d$ possible positions on level $d$ has a node in it exactly if all of its ancestor nodes decided to have children, which has probability $\prod_{k=0}^{d-1}\theta(1+k)^{-\gamma} = \theta^d/(d!)^{\gamma}$ to happen. Multiplying this probability by $2^d$ gives the same formula I used. $\endgroup$ – hmakholm left over Monica Dec 25 '14 at 1:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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