What is the expected depth of a randomly generated tree?

Question

I thought about this problem a long time ago, but have no ideas about it.

The generating algorithm is as follows. We assume there are $n$ discrete nodes numbered from $0$ to $n - 1$. Then for each $i$ in $\{1, \dotsc, n - 1\}$, we make the $i$th node's parent in the tree be a random node in $\{0, \dotsc, i - 1\}$. Iterate through each $i$ in order so that the result is a random tree with root node $0$. (Perhaps this is not random enough but this doesn't matter.)

What is the expected depth of this tree?

Answer 1

I think there is a concentration result about $e \log n$, but I haven't filled in the details yet.

We can get an upper bound for the probability that node $n$ has $d$ ancestors not including $0$. For each possible complete chain of $d$ nonzero ancestors $(a_1,a_2,...,a_d)$, the probability of that chain is $(\frac{1}{a_1})(\frac{1}{a_2})\cdots (\frac{1}{a_d}) \times \frac{1}{n}$. This corresponds to $\frac{1}{n}$ times a term of $(1+\frac{1}{2} + \frac{1}{3}+ \cdots \frac{1}{n-1})^d$ where the terms are ordered. So, an upper bound for this probability is $\frac{1}{n (d!)} H_{n-1}^d$ where $H_{n-1}$ is the $n-1$st harmonic number $1 + \frac{1}{2} + ... + \frac{1}{n-1}$. $H_{n-1} \approx \log (n-1) + \gamma$. For fixed $d$ and $n \to \infty$, the probability that node $n$ is at depth $d+1$ is at most

$$\frac{(\log n)^d}{n (d!)} \left(1+o(1)\right)$$

By Stirling's approximation we can estimate this as

$$ \frac{1}{n\sqrt{2\pi d}} \left( \frac{e \log n}{d} \right)^d. $$

For large $d$, anything much larger than $e \log n$, the base of the exponential is small, so this bound is small, and we can use the union bound to say that the probability that there is at least one node with $d$ nonzero ancestors is small.

---

See

Luc Devroye, Omar Fawzi, Nicolas Fraiman. "Depth properties of scaled attachment random recursive trees."

B. Pittel. Note on the heights of random recursive trees and random m-ary search trees. Random Structures and Algorithms, 5:337–348, 1994.

The former claims the latter showed the the maximum depth is $(e+o(1))\log n$ with high probability, and offers another proof.

Answer 2

This question was answered several years back, but, just for fun, here is a simple proof of the upper bound. We give a bound on the expectation, then a tail bound.

Define r.v. $d_i$ to be the depth of node $i\in\{0,1,\ldots,n-1\}$. Define $\phi_i = \sum_{j=0}^i e^{d_j}.$

lemma 1. The expected maximum depth, $E[\max_i d_i]$ is at most $e\, H_{n-1}$.

Proof. The maximum depth is at most $\ln \phi_{n-1}$. To finish we show $E[\ln \phi_{n-1}] \le e\, H_{n-1}$.

For any $i\ge 1$, conditioning on $\phi_{i-1}$, by inspection of $\phi_i$, $$\textstyle E[\phi_i\, |\, \phi_{i-1}] \,=\,\phi_{i-1} + E[e^{d_i}] \,=\, \phi_{i-1} + \frac{e}{i} \phi_{i-1} \,=\, (1+\frac{e}{i}) \phi_{i-1}.$$

By induction it follows that $$\textstyle E[\phi_{n-1}] \,=\, \prod_{i=1}^{n-1} (1+\frac{e}{i}) \,<\, \prod_{i=1}^{n-1} \exp(\frac{e}{i}) \,=\, \exp(e\, H_{n-1}).$$

So, by the concavity of the logarithm, $$E[\ln \phi_{n-1}] \,\le\, \ln E[\phi_{n-1}] \,<\, \ln \exp(e\, H_{n-1}) \,=\, e\, H_{n-1}.~~~~~~~\Box$$

Here is the tail bound:

lemma 2. Fix any $c \ge 0$. Then $\Pr[\max_i d_i] \ge e\,H_{n-1} + c$ is at most $\exp(-c)$.

Proof. By inspection of $\phi$, and the Markov bound, the probability in question is at most $$\Pr[\phi_{n-1} \ge \exp(e\,H_{n-1} + c)] \,\le\,\frac{E[\phi_{n-1}]}{\exp(e\,H_{n-1} + c)}.$$ From the proof of Lemma 1, $E[\phi_{n-1}]\le \exp(e\,H_{n-1})$. Substituting this into the right-hand side above completes the proof.$~~~\Box$

As for a lower bound, I think a lower bound of $(e-1)H_n - O(1)$ follows pretty easily by considering $\max_i d_i \ge \ln\phi_t - \ln n$. But... [EDIT: spoke too soon]

It doesn't seem so easy to show the tight lower bound, of $(1-o(1))e H_n$...

Answer 3

I have actually thought about the same question (although in a completely different formulation) a few months ago, as well as some close variants.

I don't have a closed form (/ asymptotic) solution for it, but you might find this view useful (are you only looking for upper bound perhaps?).

The process you describe here is a generalization of the Chinese Restaurant Process, where each "table" is a subtree whose root's parent is $v_0$.

This also gives us a recursion formula for your question.

Denote by $h(n)$ the expected heights of a such tree process with $n$ nodes.

Denote by $P_n(B)=\frac{\Pi_{b\in B} (b-1)!}{n!}$ (the probability of distribution $B$ of the nodes into subtrees).

Then the quantity you're looking for, $h(n)$, is given by:

$$h(n)=\sum_{B\in \mathcal B_n}P_n(B)\cdot \max_{b\in B} h(b)$$

If you wish to code this recursion, make sure you use the following so it won't go into infinite loop:

$$h(n)=\frac{\sum_{B\in \mathcal B_n\setminus \{\{n\}\}}P_n(B)\cdot \max_{b\in B} h(b)}{1-\frac{1}{n!}}$$

Where $\mathcal B_n$ is the set of all partitions of $n$ identical balls into any number of non-empty bins, and $h(1)=1$.

---

In practice, when I needed this I just used a simple monte-carlo method for estimating $h(n)$, as trying to actually compute $h$ by this method is extremely inefficient.