The size of random fragmentation trees

DOI10.1007/S00440-007-0110-1MaRDI QIDQ946483zbMATH OpenOpenAlexFDO

Authors Svante Janson, Ralph Neininger

Publication date 23 September 2008

Published in Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0609350

zbMATH Keywords

asymptotic normalitycontraction methodfragmentation processLaplace transformrandom treesrenewal equation

Mathematics Subject Classification ID

Combinatorial probability (60C05) Central limit and other weak theorems (60F05) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Data structures (68P05)

Abstract: We study a random fragmentation process and its associated random tree. The process has earlier been studied by Dean and Majumdar (J. Phys. A: Math. Gen., vol. 35, L501--L507), who found a phase transition: the number of fragmentations is asymptotically normal in some cases but not in others, depending on the position of roots of a certain characteristic equation. This parallels the behaviour of discrete analogues with various random trees that have been studied in computer science. We give rigorous proofs of this phase transition, and add further details. The proof uses the contraction method. We extend some previous results for recursive sequences of random variables to families of random variables with a continuous parameter; we believe that this extension has independent interest.

Review text

Split the interval \([0,x]\) at random into \(b\geq2\) smaller subintervals according to a prescribed law, and repeat the same procedure for each subinterval until the length becomes less than unity. How many splitting steps \(N(x)\) are used in such a fragmentation process, often ascribed to Kolmogorov? This paper proves, under very general conditions on the underlying splitting law, that the limiting distribution of \(N(x)\) undergoes a phase change from being normal to non-existent, depending on the real part of the second-largest zeros (arranged in real parts) of a characteristic equation. Using the terminology of \textit{D. Aldous} [Bernoulli 5, No.~1, 3--48 (1999; Zbl 0930.60096)], this is a very successful theorem-proof paper, motivated largely by the scientific modelling mathematics in the paper by \textit{D. S. Dean} and \textit{S. N. Majumdar} [J. Phys. A, Math. Gen. 35, No.~32, L501--L507 (2002; Zbl 1040.82021)]. The interesting results are proved by a combination of a few powerful approaches, relying on tools from renewal theory and contraction method.

Recommendations

• Fragmentation of random trees
• scientific article; zbMATH DE number 3920488
• On the branch size of random m-trees
• A phase transition for the heights of a fragmentation tree
• scientific article; zbMATH DE number 6683511
• The size of random fragmentation intervals
• Limit distributions of the maximum size of a tree in a random recursive forest

Cites work

• m‐ary Search trees when m ≥ 27: A strong asymptotics for the space requirements
• A characterization of the set of fixed points of the quicksort transformation
• A general limit theorem for recursive algorithms and combinatorial structures
• Analysis of the space of search trees under the random insertion algorithm
• Approximation of Distributions of Sums of Independent Random Variables with Values in Infinite-Dimensional Spaces
• Asymptotic laws for nonconservative self-similar fragmentations
• Counting intervals in the packing process
• Functional limit theorems for multitype branching processes and generalized Pólya urns.
• scientific article; zbMATH DE number 4013703 (Why is no real title available?)
• scientific article; zbMATH DE number 2127736 (Why is no real title available?)
• scientific article; zbMATH DE number 3122046 (Why is no real title available?)
• scientific article; zbMATH DE number 3171475 (Why is no real title available?)
• scientific article; zbMATH DE number 3736133 (Why is no real title available?)
• scientific article; zbMATH DE number 49698 (Why is no real title available?)
• scientific article; zbMATH DE number 3555176 (Why is no real title available?)
• scientific article; zbMATH DE number 3565828 (Why is no real title available?)
• scientific article; zbMATH DE number 3349081 (Why is no real title available?)
• scientific article; zbMATH DE number 3040395 (Why is no real title available?)
• Ideal Metrics in the Problem of Approximating Distributions of Sums of Independent Random Variables
• On the invariance principle for sums of independent identically distributed random variables
• One-sided interval trees
• One-sided variations on interval trees
• Paths in \(m\)-ary interval trees
• Phase changes in random m-ary search trees and generalized quicksort
• Phase changes in random point quadtrees
• Phase transition in a random fragmentation problem with applications to computer science
• Random Fragmentation and Coagulation Processes
• Random sequential bisection and its associated binary tree
• Recursive partition structures
• Rounding of continuous random variables and oscillatory asymptotics
• Some asymptotic theory for the bootstrap
• Splitting intervals
• Splitting intervals. II: Limit laws for lengths
• Stable distributions in stochastic fragmentation
• The contraction method for recursive algorithms
• Transfer theorems and asymptotic distributional results for m‐ary search trees
• Universal Limit Laws for Depths in Random Trees

Cited in

(29)

• Splitting intervals. II: Limit laws for lengths
• Size-biased and conditioned random splitting trees
• Normal limiting distribution of the size of binary interval trees
• Benford's law and continuous dependent random variables
• The genealogy of self-similar fragmentations with negative index as a continuum random tree
• Self-similar fragmentations derived from the stable tree. II: Splitting at nodes
• Self-similar real trees defined as fixed points and their geometric properties
• On a functional contraction method
• Solutions to complex smoothing equations
• Pólya urns via the contraction method
• scientific article; zbMATH DE number 6683511 (Why is no real title available?)
• The size of random fragmentation intervals
• A phase transition for the heights of a fragmentation tree
• Breakage and restoration in recursive trees
• The existence of a giant cluster for percolation on large Crump–Mode–Jagers trees
• Phase transition in a random fragmentation problem with applications to computer science
• On the number of large triangles in the Brownian triangulation and fragmentation processes
• Nonhomogenous bivariate fragmentation process: asymptotic distribution via contraction method
• Fragmentation of random trees
• Expected size of a tree in the fixed point forest
• On Random Fragmentations Arising From Binary Splitting
• Dependence and phase changes in random m-ary search trees
• Moments of a non‐homogenous bi‐variate fragmentation process using integral equations tools
• A growth-fragmentation-isolation process on random recursive trees and contact tracing
• Limit theorems for discrete multitype branching processes counted with a characteristic
• A two-time-scale phenomenon in a fragmentation-coagulation process
• Analytic and numerical analysis of some statistical features of fragmentation processes
• Asymptotic fluctuations in supercritical Crump-Mode-Jagers processes
• The fragmentation process of an infinite recursive tree and Ornstein-Uhlenbeck type processes

This page was built for publication: The size of random fragmentation trees

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