5
$\begingroup$

I just finished reading the proof that the average height of a random binary of given size $n$ is asymptotically $2\sqrt{\pi n}$.

I'm now searching for an intuitive, or geometric, or visual proof of this asymptotic equivalence. In other words, I'm trying to find an intuitive arguments that shows that this number grows like $\sqrt{n}$.

Any ideas?
Thanks!

  • 0
    The $lg(n)$ bound is only obtained when you build a binary search tree, not a random binary tree.2011-01-09

1 Answers 1

7

Here's one way to at least guess the growth rate. A random binary tree of size $n$ is the same thing (plus or minus one) as a random walk on the non-negative integers of length $n$ starting and ending at $0$, with the height of the tree corresponding to the farthest the walk goes from $0$. The order of magnitude of the height should behave like the order of magnitude of the related problem of looking at the ending position of a random walk on the integers of length $n$ starting at $0$. (I don't know how to justify this rigorously but it seems pretty plausible to me.)

But this question is much easier, since now it's a sum of independent Bernoulli random variables. The expected end position is $0$, but it is straightforward to calculate that the variance in the end position is $n$, so the standard deviation is $\sqrt{n}$. Of course, since we're dealing with a sum of independent Bernoulli random variables, we can be much more precise because the central limit theorem applies. The point is that this probabilistic reasoning tells us what the right growth rate to expect is: it's also the same rate that crops up in Brownian motion.

  • 0
    yup, yup, of course =) Anyway, your explanation is pretty convincing :) +1 for your help and careful explanations.2011-01-15