1
$\begingroup$

What is the asymptotic variance of the height of rooted plane trees (ie rooted, unlabelled, ordered trees with unbounded node degree) and of ordered binary trees (ie rooted, unlabelled, plane trees, in which every node has zero or two successors)?

It is known that the asymptotic average height of rooted plane trees is $\sqrt{\pi n} - \frac{1}{2}$ (by Knuth et al); and the asymptotic average height of binary trees is $2 \sqrt{ \pi n}$ (by Flajolet & Odlyzko).

Is anything known about the asymptotic variance of the height of one of the two tree classes?

I am asking about both tree classes because they are the two most prominent tree class examples.
Note that the variance of the height of binary search trees is known; yet these are a different class of trees (they are binary trees with a nonuniform distribution).

$\endgroup$
  • $\begingroup$ By ordered, you mean that the children (subtrees) of each node are ordered, i.e. you mean plane trees, is that right? Anyway, Analytic Combinatorics should have something relevant, I think. $\endgroup$ – ShreevatsaR Feb 3 '14 at 2:31
  • $\begingroup$ Right, plane trees. I looked in Analytic Combinatorics (where else would I start?), but I didn't find anything. There is surprisingly little discussion on variances of parameters of combinatorial classes. $\endgroup$ – john_leo Feb 3 '14 at 9:48
  • $\begingroup$ I'm not sure I understand all the mathematics, but (looking in the index for "height") their Proposition VII.16 (pp. 537–538) seems to apply. It gives the moments of the distribution of height, for certain classes of trees, which is a lot more than variance. See also p. 328 (under "Probability distribution of height"). $\endgroup$ – ShreevatsaR Feb 3 '14 at 11:11
  • $\begingroup$ Ah, you're right. I will look into that, thanks. $\endgroup$ – john_leo Feb 3 '14 at 11:14
1
$\begingroup$

Thanks to ShreevatsaR's comment, I could find the right section in Flajolet's book and work out the examples.
Proposition VII.16 states that, with $\phi$ the basic tree constructor of a tree family $F$ and $\tau$ the root of the characteristic equation $\phi(\tau) - \tau \phi'(\tau)=0$ (note that there's a typo in the book), the second moment of the tree height $\chi$ of the trees of size $n$ satisfies $$ E_{F_n}(\chi^2) \sim \frac{\pi^2}{3} \frac{2\phi'(\tau)^2}{\phi(\tau)\phi''(\tau)} n. $$ Let $B$ denote the family of binary trees, and let $P$ denote the family of plane trees. Then $\phi_B(u) = 1+ u^2 $, $\phi_P(u) = (1-u)^{-1}$, $\tau_B=1$ and $\tau_p = 1/2$. So $$ E_{B_n}(\chi^2) \sim \frac{4\pi^2}{3}n \quad \text{and} \quad E_{P_n}(\chi^2) \sim \frac{\pi^2}{3}n, $$ hence the variances are asymptotically $4 \pi \left(\frac{\pi}{3} - 1 \right) n$ (for binary trees) and $\pi\left(\frac{\pi}{3} - 1 \right) n$ (for plane trees).

$\endgroup$

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.