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?
What is the expected depth of a randomly generated tree?
pr.probability
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:337348, 1994.The former claims the latter showed the the maximum depth is $(e+o(1))\log n$ with high probability, and offers another proof.