Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Consider a full binary tree with $k>10$ levels. Let the lengths of individual edges in this tree be i.i.d. random variables with finite moments. Then total lengths of the $2^{k-1}$ source-to-sink paths in this tree are approximately Gaussian by the CLT, regardless of the edge-length distribution. We are interested in the limit distribution ($k\rightarrow\infty$) of the maximum path length in the tree.

Our numerical simulation built 100K independent trees ($k=15$) with $(a)$ uniform and $(b)$ Gaussian edge lengths. The resulting distributions for $(a)$ and $(b)$ did not look qualitatively different and were somewhat skewed to the right. Lognormal distributions provided very close fits --- better than Gumbel and Airy. If lognormal is indeed the limit distribution, we would appreciate references or suggestions on proving this analytically.

share|improve this question

1 Answer 1

up vote 2 down vote accepted

Unless I misunderstood your question, this can be entirely rephrased in terms of branching random walks. This goes as follows: at time 0 there is 1 individual at position 0. Each individual gives birth to two descendants, whose position is the position of the parent plus a jump, where all jumps are i.i.d. random variable. You are asking about the maximum position at time $k$, $M_k$.

This is a much studied problem, with deep links to traveling wave partial differential equations such as the Fisher-KPP equation. (Eg, in the space-time continuous case where branching random walk is replaced by branching Brownian motion, the function $u(t,x) = \mathbb{P}(M_t >x)$ solves the KPP equation with initial condition $u(0,x) = 1_{x<0}$.)

See this recent paper http://front.math.ucdavis.edu/1101.1810 by Elie Aidekon, which provides complete answers to your question under minimal assumptions on the jump distribution. The main result is then that $M_k - ck + (3/2) \log k$ converges to a random variable, where $c$ is a constant that is easy to compute. The distribution of the limiting random variable doesn't have to be either Gumbel or lognormal.

In the space-time continuous case where branching random walk is replaced by branching Brownian motion, this result is a famous result originally due to Maury Bramson (1983): Convergence of solutions of the Kolmogorov equation to travelling waves. Mem. Amer. Math. Soc. 44, no. 285.

share|improve this answer
    
Makes sense - thanks ! –  Igor Markov Jan 1 '12 at 7:21

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.