2001/05/15 by E. Ben-Naim, E. Ben‐Naim, P. L. Krapivsky +1
Mathematics · Physics and Astronomy · #Stochastic processes and statistical mechanics #Theoretical and Computational Physics #cond-mat.stat-mech
paper · pdf · doi:10.1103/physreve.64.035101
published as Phys. Rev. E 64, R035101 (2001) · 4 pages, revtex
arxiv created 2001/05/15 · openalex publication_date 2001/08/06 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We investigate extremal statistical properties such as the maximal and the minimal heights of randomly generated binary trees. By analyzing the master evolution equations we show that the cumulative distribution of extremal heights approaches a traveling wave form. The wave front in the minimal case is governed by the small-extremal-height tail of the distribution, and conversely, the front in the maximal case is governed by the large-extremal-height tail of the distribution. We determine several statistical characteristics of the extremal height distribution analytically. In particular, the expected minimal and maximal heights grow logarithmically with the tree size, N, h(min) approximately v(min) ln N, and h(max) approximately v(max) ln N, with v(min)=0.373365ellipsis and v(max)=4.31107ellipsis, respectively. Corrections to this asymptotic behavior are of order O(ln ln N).