Phase transition in a generalized Eden growth model on a tree

DOI10.1007/S10955-006-9193-9zbMATH Open1106.82023OpenAlexW2098908366MaRDI QIDQ858046FDOQ858046

Authors David S. Dean, Satya N. Majumdar 

Publication date 5 January 2007

Published in Journal of Statistical Physics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cond-mat/0510429

zbMATH Keywords

Phase transitionsSearch treesGrowth models

Mathematics Subject Classification ID

Trees (05C05) Dynamic and nonequilibrium phase transitions (general) in statistical mechanics (82C26) Stochastic methods (Fokker-Planck, Langevin, etc.) applied to problems in time-dependent statistical mechanics (82C31) General biology and biomathematics (92B05)

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

Recommendations

• The critical exponent of the tree lattice generating function in the Eden model
• scientific article; zbMATH DE number 999745
• scientific article; zbMATH DE number 1984555
• Birth and death processes on certain random trees: classification and stationary laws
• The expected perimeter in Eden and related growth processes

Cites work

• scientific article; zbMATH DE number 425307 (Why is no real title available?)
• scientific article; zbMATH DE number 3165855 (Why is no real title available?)
• scientific article; zbMATH DE number 53861 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3040053 (Why is no real title available?)
• m‐ary Search trees when m ≥ 27: A strong asymptotics for the space requirements
• A diffusion limit for a class of randomly-growing binary trees
• A universal algorithm for sequential data compression
• Asymptotic Behavior of the Height in a Digital Search Tree and the Longest Phrase of the Lempel--Ziv Scheme
• Digital Search Trees Revisited
• Fragment size distributions in random fragmentations with cutoff
• Generalized Digital Trees and Their Difference—Differential Equations
• Paths in a random digital tree: limiting distributions
• Phase changes in random \(m\)-ary search trees and generalized quicksort
• Phase transition in a random fragmentation problem with applications to computer science
• Singularity analysis, Hadamard products, and tree recurrences
• Statistical mechanics of complex networks
• Transfer theorems and asymptotic distributional results for m‐ary search trees

Cited in

(9)

• Off-lattice Eden-C cluster growth model
• Behavior near the extinction time in self-similar fragmentations. II: Finite dislocation measures.
• The critical exponent of the tree lattice generating function in the Eden model
• Universality class of isotropic on-lattice Eden clusters
• Field induced stationary state for an accelerated tracer in a bath
• Tree growth parameter in the eden model on face-centered hypercubic lattices
• An analytic approach to the asymptotic variance of trie statistics and related structures
• Stationary Eden model on Cayley graphs
• A Markovian growth dynamics on rooted binary trees evolving according to the Gompertz curve

This page was built for publication: Phase transition in a generalized Eden growth model on a tree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q858046)