2005/09/21 by Svante Janson, Janson, Svante
Mathematics · Physics and Astronomy · #05C05 #60C05 #Combinatorics (math.CO) #FOS: Mathematics #Mathematical Dynamics and Fractals #Probability (math.PR) #Stochastic processes and statistical mechanics #Theoretical and Computational Physics #math.CO #math.PR #msc:05C05 #msc:60C05
paper · pdf · doi:10.48550/arxiv.math/0509471
23 pages
arxiv created 2005/09/21 · openalex publication_date 2005/09/21 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Consider a random recusive tree with n vertices. We show that the number of vertices with even depth is asymptotically normal as n tends to infinty. The same is true for the number of vertices of depth divisible by m for m=3, 4 or 5; in all four cases the variance grows linearly. On the other hand, for m at least 7, the number is not asymptotically normal, and the variance grows faster than linear in n. The case m=6 is intermediate: the number is asymptotically normal but the variance is of order n log n. This is a simple and striking example of a type of phase transition that has been observed by other authors in several cases. We prove, and perhaps explain, this non-intuitive behavious using a translation to a generalized Polya urn. Similar results hold for a random binary search tree; now the number of vertices of depth divisible by m is asymptotically normal for m at most 8 but not for m at least 9, and the variance grows linearly in the first case both faster in the second. (There is no intermediate case.) In contrast, we show that for conditioned Galton-Watson trees, including random labelled trees and random binary trees, there is no such phase transition: the number is asymptotically normal for every m.