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