An Isaac Newton Institute Workshop

First-Passage and Extreme Value Problems in Random Processes

Phase Transition in the Aldous-Shields Model of Growing Trees

28th June 2006

Author: Dean, D (Universite Paul Sabatier)

Abstract

We study analytically the late time statistics of the number of particles in a growing tree model introduced by Aldous and Shields. In this model, a cluster grows in continuous time on a binary Cayley tree, starting from the root, by absorbing new particles at the empty perimeter sites at a rate proportional to $c^{-l}$ where $c$ is a positive parameter and $l$ is the distance of the perimeter site from the root. For $c=1$, this model corresponds to random binary search trees and for $c=2$ it corresponds to digital search trees in computer science. By introducing a backward Fokker-Planck approach, we calculate the mean and the variance of the number of particles at large times and show that the variance undergoes a `phase transition' at a critical value $c=\sqrt{2}$. While for $c>\sqrt{2}$ the variance is proportional to the mean and the distribution is normal, for $c<\sqrt{2}$ the variance is anomalously large and the distribution is non-Gaussian due to the appearance of extreme fluctuations. The model is generalized to one where growth occurs on a tree with $m$ branches and, in this more general case, we show that the critical point occurs at $c=\sqrt{m}$.