Abstract
We consider the random fragmentation process introduced by Kolmogorov, where a particle having some mass is broken into pieces and the mass is distributed among the pieces at random in such a way that the proportions of the mass shared among different daughters are specified by some given probability distribution (the dislocation law); this is repeated recursively for all pieces. More precisely, we consider a version where the fragmentation stops when the mass of a fragment is below some given threshold, and we study the associated random tree. Dean and Majumdar found a phase transition for this process: the number of fragmentations is asymptotically normal for some dislocation laws but not for others, depending on the position of roots of a certain characteristic equation. This parallels the behavior 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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Asmussen S. (1987). Applied Probability and Queues. Wiley, Chichester
Baryshnikov Y. and Gnedin A. (2001). Counting intervals in the packing process. Ann. Appl. Probab. 11: 863–877
Bertoin J. (2006). Random Fragmentation and Coagulation Processes. Cambridge University Press, Cambridge
Bertoin J. and Gnedin A. (2004). Asymptotic laws for nonconservative self-similar fragmentations. Electron. J. Probab. 9: 575–593
Bickel P.J. and Freedman D.A. (1981). Some asymptotic theory for the bootstrap. Ann. Statist. 9: 1196–1217
Brennan M.D. and Durrett R. (1986). Splitting intervals. Ann. Probab. 14: 1024–1036
Brennan M.D. and Durrett R. (1987). Splitting intervals. II. Limit laws for lengths. Probab. Theory Related Fields 75: 109–127
Chauvin B. and Pouyanne N. (2004). m-ary search trees when m ≥ 27: a strong asymptotics for the space requirements. Random Struct. Algorithms 24: 133–154
Chern, H.-H., Fuchs, M., Hwang, H.-K.: Phase changes in random point quadtrees. ACM Trans. Algorithms (to appear) (2006)
Chern H.-H. and Hwang H.-K. (2001). Phase changes in random m-ary search trees and generalized quicksort. Random Struct. Algorithms 19: 316–358
Dall’Aglio G. (1956). Sugli estremi dei momenti delle funzioni di ripartizione doppia. Ann. Scuola Norm. Sup. Pisa 10: 35–74
Dean D.S. and Majumdar S.N. (2002). Phase transition in a random fragmentation problem with applications to computer science. J. Phys. A: Math. Gen. 35: L501–L507
Devroye L. (1999). Universal limit laws for depths in random trees. SIAM J. Comput. 28: 409–432
Feller W. (1971). An Introduction to Probability Theory and its Applications, vol. II, 2nd edn. Wiley, New York
Fill J.A. and Janson S. (2000). A characterization of the set of fixed points of the quicksort transformation. Electronic Comm. Probab. 5(9): 77–84
Fill, J.A., Kapur, N.: The space requirement of m-ary search trees: distributional asymptotics for m ≥ 27. In: Proceedings of the 7th Iranian Statistical Conference, Tehran (2004)
Fill J.A. and Kapur N. (2005). Transfer theorems and asymptotic distributional results for m-ary search trees. Random Struct. Algorithms 26: 359–391
Garnett J.B. (1981). Bounded Analytic Functions. Academic, New York
Gnedin A.V. and Yakubovich Y. (2006). Recursive partition structures. Ann. Probab. 34: 2203–2218
Itoh Y. and Mahmoud H. (2003). One-sided variations on interval trees. J. Appl. Prob. 40: 654–670
Jagers P. (1975). Branching Processes with Biological Applications. Wiley, Chichester
Janson S. (2004). Functional limit theorems for multitype branching processes and generalized Pólya urns. Stochastic Processes Appl. 110: 177–245
Janson S. (2004). One-sided interval trees. J. Iranian Stat. Soc. 3: 149–164
Janson S. (2006). Rounding of continuous random variables and oscillatory asymptotics. Ann. Probab. 34: 1807–1826
Javanian M., Mahmoud H. and Vahidi-Asl M. (2004). Paths in m-ary interval trees. Discrete Math. 287: 45–53
Javanian M. and Vahidi-Asl M. (2004). Multidimensional interval trees. In: Drmota, M., Flajolet, P., Gardy, D. and Gittenberger, B. (eds) Mathematics and Computer Science III, Algorithms, Trees, Combinatorics and Probabilities (Vienna 2004), pp 255–256. Birkhäuser, Basel
Kakutani, S.: A problem of equidistribution on the unit interval [0,1]. Measure theory (Oberwolfach, 1975), Lecture Notes in Math., vol. 541, pp. 369–375. Springer, Berlin (1976)
Kolmogoroff A.N. (1941). Über das logarithmisch normale Verteilungsgesetz der Dimensionen der Teilchen bei Zerstückelung. C. R. (Doklady) Acad. Sci. URSS (N. S.) 31: 99–101
Krapivsky P.L., Ben-Naim E. and Grosse I. (2004). Stable distributions in stochastic fragmentation. J. Phys. A: Math. Gen. 37: 2863–2880
Krapivsky P.L., Grosse I. and Ben-Naim E. (2000). Scale invariance and lack of self-averaging in fragmentation. Phys. Rev. E 61: R993–R996
Mahmoud H.M. and Pittel B. (1989). Analysis of the space of search trees under the random insertion algorithm. J. Algorithms 10: 52–75
Major P. (1978). On the invariance principle for sums of independent identically distributed random variables. J. Multivariate Anal. 8: 487–517
Neininger R. and Rüschendorf L. (2004). A general limit theorem for recursive algorithms and combinatorial structures. Ann. Appl. Probab. 14: 378–418
Rachev S.T. (1991). Probability Metrics and the Stability of Stochastic Models. Wiley, New York
Rényi, A.: On a one-dimensional random space-filling problem. (Hungarian.) Magyar Tud. Akad. Mat. Kutató Int. Közl. 3, 109–127 (1958). English transl. in Selected papers of Alfréd Rényi, vol. II: 1956–1961. Ed. Pál Turán, (1976) pp. 173–188. Akadémiai Kiadó, Budapest
Rösler U. and Rüschendorf L. (2001). The contraction method for recursive algorithms. Algorithmica 29: 3–33
Sibuya M. and Itoh Y. (1987). Random sequential bisection and its associated binary tree. Ann. Inst. Statist. Math. 39: 69–84
Zolotarev, V.M.: Approximation of the distributions of sums of independent random variables with values in infinite-dimensional spaces. (Russian.) Teor. Verojatnost. i Primenen. 21, no. 4, 741–758 (1976). Erratum ibid 22 (1977), no. 4, 901. English transl. Theor. Probability Appl. 21, no. 4, 721–737; 22 (1977), no. 4, 679–691 (1978)
Zolotarev V.M. (1977). Ideal metrics in the problem of approximating the distributions of sums of independent random variables (Russian). Teor. Verojatnost. i Primenen. 22(3): 449–465
Author information
Authors and Affiliations
Corresponding author
Additional information
Research supported by an Emmy Noether fellowship of the DFG.
Rights and permissions
About this article
Cite this article
Janson, S., Neininger, R. The size of random fragmentation trees. Probab. Theory Relat. Fields 142, 399–442 (2008). https://doi.org/10.1007/s00440-007-0110-1
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00440-007-0110-1