×

The size of random fragmentation trees. (English) Zbl 1158.60044

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 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 D. S. Dean and 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.

MSC:

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

References:

[1] Asmussen, S., Applied Probability and Queues (1987), Chichester: Wiley, Chichester · Zbl 0624.60098
[2] Baryshnikov, Y.; Gnedin, A., Counting intervals in the packing process, Ann. Appl. Probab., 11, 863-877 (2001) · Zbl 1021.60005
[3] Bertoin, J., Random Fragmentation and Coagulation Processes (2006), Cambridge: Cambridge University Press, Cambridge · Zbl 1107.60002
[4] Bertoin, J.; Gnedin, A., Asymptotic laws for nonconservative self-similar fragmentations, Electron. J. Probab., 9, 575-593 (2004) · Zbl 1064.60075
[5] Bickel, P. J.; Freedman, D. A., Some asymptotic theory for the bootstrap, Ann. Statist., 9, 1196-1217 (1981) · Zbl 0449.62034
[6] Brennan, M. D.; Durrett, R., Splitting intervals, Ann. Probab., 14, 1024-1036 (1986) · Zbl 0601.60028
[7] Brennan, M. D.; Durrett, R., Splitting intervals. II. Limit laws for lengths, Probab. Theory Related Fields, 75, 109-127 (1987) · Zbl 0607.60010
[8] Chauvin, B.; Pouyanne, N., m-ary search trees when m ≥ 27: a strong asymptotics for the space requirements, Random Struct. Algorithms, 24, 133-154 (2004) · Zbl 1037.60027
[9] Chern, H.-H., Fuchs, M., Hwang, H.-K.: Phase changes in random point quadtrees. ACM Trans. Algorithms (to appear) (2006) · Zbl 1321.68218
[10] Chern, H.-H.; Hwang, H.-K., Phase changes in random m-ary search trees and generalized quicksort, Random Struct. Algorithms, 19, 316-358 (2001) · Zbl 0990.68052
[11] Dall’Aglio, G., Sugli estremi dei momenti delle funzioni di ripartizione doppia, Ann. Scuola Norm. Sup. Pisa, 10, 35-74 (1956) · Zbl 0073.14002
[12] Dean, D. S.; Majumdar, S. N., Phase transition in a random fragmentation problem with applications to computer science, J. Phys. A: Math. Gen., 35, L501-L507 (2002) · Zbl 1040.82021
[13] Devroye, L., Universal limit laws for depths in random trees, SIAM J. Comput., 28, 409-432 (1999) · Zbl 0915.68089
[14] Feller, W., An Introduction to Probability Theory and its Applications, vol. II (1971), New York: Wiley, New York · Zbl 0219.60003
[15] Fill, J. A.; Janson, S., A characterization of the set of fixed points of the quicksort transformation, Electronic Comm. Probab., 5, 9, 77-84 (2000) · Zbl 0943.68192
[16] 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)
[17] Fill, J. A.; Kapur, N., Transfer theorems and asymptotic distributional results for m-ary search trees, Random Struct. Algorithms, 26, 359-391 (2005) · Zbl 1101.68018
[18] Garnett, J. B., Bounded Analytic Functions (1981), New York: Academic, New York · Zbl 0469.30024
[19] Gnedin, A. V.; Yakubovich, Y., Recursive partition structures, Ann. Probab., 34, 2203-2218 (2006) · Zbl 1119.60025
[20] Itoh, Y.; Mahmoud, H., One-sided variations on interval trees, J. Appl. Prob., 40, 654-670 (2003) · Zbl 1043.05036
[21] Jagers, P., Branching Processes with Biological Applications (1975), Chichester: Wiley, Chichester · Zbl 0356.60039
[22] Janson, S., Functional limit theorems for multitype branching processes and generalized Pólya urns, Stochastic Processes Appl., 110, 177-245 (2004) · Zbl 1075.60109
[23] Janson, S., One-sided interval trees, J. Iranian Stat. Soc., 3, 149-164 (2004) · Zbl 1499.60309
[24] Janson, S., Rounding of continuous random variables and oscillatory asymptotics, Ann. Probab., 34, 1807-1826 (2006) · Zbl 1113.60017
[25] Javanian, M.; Mahmoud, H.; Vahidi-Asl, M., Paths in m-ary interval trees, Discrete Math., 287, 45-53 (2004) · Zbl 1095.68085
[26] Javanian, M.; Vahidi-Asl, M.; Drmota, M.; Flajolet, P.; Gardy, D.; Gittenberger, B., Multidimensional interval trees, Mathematics and Computer Science III, Algorithms, Trees, Combinatorics and Probabilities (Vienna 2004), 255-256 (2004), Basel: Birkhäuser, Basel · Zbl 1062.05039
[27] 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) · Zbl 0363.60023
[28] Kolmogoroff, A. N., Über das logarithmisch normale Verteilungsgesetz der Dimensionen der Teilchen bei Zerstückelung, C. R. (Doklady) Acad. Sci. URSS (N. S.), 31, 99-101 (1941) · Zbl 0025.19602
[29] Krapivsky, P. L.; Ben-Naim, E.; Grosse, I., Stable distributions in stochastic fragmentation, J. Phys. A: Math. Gen., 37, 2863-2880 (2004) · Zbl 1038.82028
[30] Krapivsky, P. L.; Grosse, I.; Ben-Naim, E., Scale invariance and lack of self-averaging in fragmentation, Phys. Rev. E, 61, R993-R996 (2000)
[31] Mahmoud, H. M.; Pittel, B., Analysis of the space of search trees under the random insertion algorithm, J. Algorithms, 10, 52-75 (1989) · Zbl 0685.68060
[32] Major, P., On the invariance principle for sums of independent identically distributed random variables, J. Multivariate Anal., 8, 487-517 (1978) · Zbl 0408.60028
[33] Neininger, R.; Rüschendorf, L., A general limit theorem for recursive algorithms and combinatorial structures, Ann. Appl. Probab., 14, 378-418 (2004) · Zbl 1041.60024
[34] Rachev, S. T., Probability Metrics and the Stability of Stochastic Models (1991), New York: Wiley, New York · Zbl 0744.60004
[35] 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 · Zbl 0105.11903
[36] Rösler, U.; Rüschendorf, L., The contraction method for recursive algorithms, Algorithmica, 29, 3-33 (2001) · Zbl 0967.68166
[37] Sibuya, M.; Itoh, Y., Random sequential bisection and its associated binary tree, Ann. Inst. Statist. Math., 39, 69-84 (1987) · Zbl 0622.60020
[38] 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) · Zbl 0378.60003
[39] Zolotarev, V. M., Ideal metrics in the problem of approximating the distributions of sums of independent random variables (Russian), Teor. Verojatnost. i Primenen., 22, 3, 449-465 (1977) · Zbl 0385.60025
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.