<p>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.</p>

<p>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}.$</p>

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

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

<p>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}.$$</p>

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

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

<p>Here is the tail bound:</p>

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

<p><em>Proof.</em>  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$</p>

<p><del>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...</del> [EDIT: spoke too soon]</p>

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

CC BY-SA 4.0
2020-10-25T09:39:20.693Z
Thank you for this answer. Could you explain why $\mathbb{E}(e^{d_i}) = \frac{e}{i} \phi_{i-1}$ holds?
black
CC BY-SA 4.0
2020-10-25T14:04:56.483Z
For $1\le i< n$ let r.v. $P_i$ be the parent of $i$, so $P_i$ is uniformly random in $\{0,1,\ldots,i-1\}$.  Then, conditioned on $\phi_{i-1}$,
$$E[e^{d_i}] = \sum_{j=0}^{i-1} \Pr[P_i = j] E[e^{d_i} | P_i=j] = \sum_{j=0}^{i-1} \frac{1}{i} e^{d_j+1} = \frac{e}{i} \sum_{j=0}^{i-1} e^{d_j} = \frac{e}{i} \phi_{i-1}.$$
Neal Young
CC BY-SA 4.0
2018-06-24T02:36:52.927Z
2018-06-25T15:24:43.393Z
2018-06-25T15:24:43.393Z
Neal Young
<p>I have actually thought about the same question (although in a completely different formulation) a few months ago, as well as some close variants.</p>

<p>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?).</p>

<p>The process you describe here is a generalization of the <a href="http://en.wikipedia.org/wiki/Chinese_restaurant_process" rel="nofollow">Chinese Restaurant Process</a>, where each "table" is a subtree whose root's parent is $v_0$.</p>

<p>This also gives us a recursion formula for your question.</p>

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

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

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

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

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

<p>$$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!}}$$</p>

<p>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$.</p>

<hr>

<p>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.</p>

CC BY-SA 3.0
2014-08-05T16:38:49.927Z
Thanks for the idea! Actually I wrote a monte-carlo program the first time when I met with this problem, but to my surprise the accurate result is so difficult to get.
zhxchen17
CC BY-SA 3.0
2014-08-04T17:19:55.323Z
2014-08-04T18:48:14.647Z
2014-08-04T18:48:14.647Z
R B
<p>I think there is a concentration result about $e \log n$, but I haven't filled in the details yet.</p>

<p>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 </p>

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

<p>By Stirling's approximation we can estimate this as</p>

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

<p>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. </p>

<hr>

<p>See </p>

<p><a href="http://arxiv.org/abs/1210.7168" rel="nofollow noreferrer">Luc Devroye, Omar Fawzi, Nicolas Fraiman. "Depth properties of scaled attachment random recursive trees."</a> </p>

<p><a href="https://doi.org/10.1002/rsa.3240050207" rel="nofollow noreferrer">B. Pittel. Note on the heights of random recursive trees and random m-ary search trees.
Random Structures and Algorithms, 5:337–348, 1994.</a></p>

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

CC BY-SA 3.0
2014-08-05T12:03:07.093Z
Very nice. To clarify for other readers: since you can't repeat an $a_i$, the term $(1 + \frac{1}{2} + \ldots + \frac{1}{n-1})^d$ is just an upper bound.
Peter Shor 
CC BY-SA 4.0
2014-08-05T05:21:14.447Z
2018-06-24T02:43:15.650Z
2018-06-24T02:43:15.650Z
Douglas Zare
<p>I thought about this problem a long time ago, but have no ideas about it.</p>

<p>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.)</p>

<p>What is the expected depth of this tree?</p>

CC BY-SA 3.0
2014-08-04T03:54:49.193Z
I assume $v_0$ is root and you  meant to say: "Then for each $i$ in $[1,n)$, we make the $i$-th node's parent...". Right?
Untitled
CC BY-SA 3.0
2014-08-04T11:22:29.073Z
What have you tried?  Have you tried writing a recurrence relation, say for $d(i)$ which is the expected depth of node $i$?
D.W.
CC BY-SA 3.0
2014-08-05T05:55:23.297Z
These objects are known under the name "random recursive tree".
James Martin
<pr.probability>
What is the expected depth of a randomly generated tree?
zhxchen17
# What is the expected depth of a randomly generated tree?

(Asked by: username_0 on 2014-08-04)

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?

**Tags:** pr.probability

> **Comments:**
> **username_1**: I assume $v_0$ is root and you  meant to say: "Then for each $i$ in $[1,n)$, we make the $i$-th node's parent...". Right?  
> **username_2**: What have you tried?  Have you tried writing a recurrence relation, say for $d(i)$ which is the expected depth of node $i$?  
> **username_3**: These objects are known under the name "random recursive tree".  

---

## 3 answers

### Answer by username_7 on 2014-08-05. Score: 15 | Accepted answer

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."](http://arxiv.org/abs/1210.7168)

[B. Pittel. Note on the heights of random recursive trees and random m-ary search trees.
Random Structures and Algorithms, 5:337–348, 1994.](https://doi.org/10.1002/rsa.3240050207)

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

> **Comments:**
> **username_8**: Very nice. To clarify for other readers: since you can't repeat an $a_i$, the term $(1 + \frac{1}{2} + \ldots + \frac{1}{n-1})^d$ is just an upper bound.  

---

### Answer by username_4 on 2018-06-24. Score: 3

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$...

> **Comments:**
> **username_5**: Thank you for this answer. Could you explain why $\mathbb{E}(e^{d_i}) = \frac{e}{i} \phi_{i-1}$ holds?  
> **username_4**: For $1\le i< n$ let r.v. $P_i$ be the parent of $i$, so $P_i$ is uniformly random in $\{0,1,\ldots,i-1\}$.  Then, conditioned on $\phi_{i-1}$, $$E[e^{d_i}] = \sum_{j=0}^{i-1} \Pr[P_i = j] E[e^{d_i} | P_i=j] = \sum_{j=0}^{i-1} \frac{1}{i} e^{d_j+1} = \frac{e}{i} \sum_{j=0}^{i-1} e^{d_j} = \frac{e}{i} \phi_{i-1}.$$  

---

### Answer by username_6 on 2014-08-04. Score: 2

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](http://en.wikipedia.org/wiki/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.

> **Comments:**
> **username_0**: Thanks for the idea! Actually I wrote a monte-carlo program the first time when I met with this problem, but to my surprise the accurate result is so difficult to get.  

---

