The size of random fragmentation trees

DOI10.1007/S00440-007-0110-1zbMATH Open1158.60044arXivmath/0609350OpenAlexW2592489754MaRDI QIDQ946483FDOQ946483

Authors: Svante Janson, Ralph Neininger 

Publication date: 23 September 2008

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

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.

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

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

zbMATH Keywords

Laplace transformasymptotic normalityrandom treesrenewal equationcontraction methodfragmentation process

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (29)

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

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)