The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content



Phase transition in the Aldous-Shields Model of growing trees

Dean, D (Universite Paul Sabatier)
Thursday 29 June 2006, 10:00-11:00

Seminar Room 1, Newton Institute


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}$.


[pdf ]


MP3MP3 Real AudioReal Audio

Back to top ∧