Question

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.

Answer 1

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.