Breakage and restoration in recursive trees
- 1 June 2002
- journal article
- Published by Cambridge University Press (CUP) in Journal of Applied Probability
- Vol. 39 (2) , 383-390
Abstract
Uniform sequential tree-building aggregation of n particles is analyzed together with the effect of the avalanche that takes place when a subtree rooted at a uniformly chosen vertex is removed. For large n, the expected subtree size is found to be ≃ logn both for the tree of size n and the tree that remains after an avalanche. Repeated breakage-restoration cycles are seen to give independent avalanches which attain size k(1 ≤ k ≤ n-1) with probability (k(k+1))-1 and restored trees that are recursive.Keywords
This publication has 10 references indexed in Scilit:
- Punctuated equilibrium and criticality in a simple model of evolutionPhysical Review Letters, 1993
- Distances in random plane-oriented recursive treesJournal of Computational and Applied Mathematics, 1992
- Self-Organized CriticalityScientific American, 1991
- Experimental study of critical-mass fluctuations in an evolving sandpilePhysical Review Letters, 1990
- Fractal Growth Phenomena1989
- Diffusion-Limited Aggregation with DisaggregationPhysical Review Letters, 1985
- Two Probability Models of Pyramid or Chain Letter Schemes Demonstrating that Their Promotional Claims are UnreliableOperations Research, 1984
- On the number of terminal vertices in certain random trees with an application to stemma construction in philologyJournal of Applied Probability, 1982
- Diffusion-Limited Aggregation, a Kinetic Critical PhenomenonPhysical Review Letters, 1981
- On the Altitude of Nodes in Random TreesCanadian Journal of Mathematics, 1978