×

zbMATH — the first resource for mathematics

The dual tree of a recursive triangulation of the disk. (English) Zbl 1355.60014
In the recursive lamination of the disk, one tries to add chords one after another at random; a chord is kept and inserted if it does not intersect any of the previously inserted ones. N. Curien and J.-F. Le Gall [Ann. Probab. 39, No. 6, 2224–2270 (2011; Zbl 1252.60016)] have proved that the set of chords converges to a limit triangulation of the disk encoded by a continuous process \(\mathcal{M}\). Based on a new approach resembling ideas from the so-called contraction method in function spaces, this paper proves that, when properly rescaled, the planar dual of the discrete lamination converges almost surely in the Gromov-Hausdorff sense to a limit real tree \(\mathcal{T}\), which is encoded by \(\mathcal{M}\). This confirms a conjecture of Curien and Le Gall [loc. cit.].

MSC:
60C05 Combinatorial probability
60F17 Functional limit theorems; invariance principles
05C05 Trees
11Y16 Number-theoretic algorithms; complexity
05A15 Exact enumeration problems, generating functions
05A16 Asymptotic enumeration
PDF BibTeX XML Cite
Full Text: DOI Euclid arXiv
References:
[1] Addario-Berry, L., Broutin, N., Goldschmidt, C. and Miermont, G. (2013). The scaling limit of the minimum spanning tree of the complete graph. Preprint. Available at . arXiv:1301.1664 · Zbl 1407.60013 · arxiv.org
[2] Aldous, D. (1991). The continuum random tree. I. Ann. Probab. 19 1-28. · Zbl 0722.60013 · doi:10.1214/aop/1176990534
[3] Aldous, D. (1991). The continuum random tree. II. An overview. In Stochastic Analysis ( Durham , 1990) (M. T. Barlow and N. H. Bingham, eds.) 23-70. Cambridge Univ. Press, Cambridge. · Zbl 0791.60008 · doi:10.1017/CBO9780511662980.003
[4] Aldous, D. (1993). The continuum random tree. III. Ann. Probab. 21 248-289. · Zbl 0791.60009 · doi:10.1214/aop/1176989404
[5] Aldous, D. (1994). Recursive self-similarity for random trees, random triangulations and Brownian excursion. Ann. Probab. 22 527-545. · Zbl 0808.60017 · doi:10.1214/aop/1176988720
[6] Aldous, D. (1994). Triangulating the circle, at random. Amer. Math. Monthly 101 223-233. · Zbl 0804.52011 · doi:10.2307/2975599
[7] Bai, Z.-D., Hwang, H.-K., Liang, W.-Q. and Tsai, T.-H. (2001). Limit theorems for the number of maxima in random samples from planar regions. Electron. J. Probab. 6 41 pp. (electronic). · Zbl 0986.60007 · doi:10.1214/EJP.v6-76
[8] Baryshnikov, Y. and Gnedin, A. (2001). Counting intervals in the packing process. Ann. Appl. Probab. 11 863-877. · Zbl 1021.60005 · doi:10.1214/aoap/1015345351
[9] Bertoin, J. (2006). Random Fragmentation and Coagulation Processes . Cambridge Univ. Press, Cambridge. · Zbl 1107.60002 · doi:10.1017/CBO9780511617768
[10] Bertoin, J. and Gnedin, A. V. (2004). Asymptotic laws for nonconservative self-similar fragmentations. Electron. J. Probab. 9 575-593. · Zbl 1064.60075 · doi:10.1214/EJP.v9-215 · emis:journals/EJP-ECP/_ejpecp/EjpVol9/paper19.abs.html · eudml:124731 · arxiv:math/0402227
[11] Billingsley, P. (1968). Convergence of Probability Measures . Wiley, New York. · Zbl 0172.21201
[12] Broutin, N., Neininger, R. and Sulzbach, H. (2012). Partial match queries in random quadtrees. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms ( SODA ) (Y. Rabani, ed.) 1056-1065. · Zbl 1358.68080 · doi:10.1214/12-AAP912 · arxiv:1202.1342
[13] Broutin, N., Neininger, R. and Sulzbach, H. (2013). A limit process for partial match queries in random quadtrees and \(2\)-d trees. Ann. Appl. Probab. 23 2560-2603. · Zbl 1358.68080 · doi:10.1214/12-AAP912 · arxiv:1202.1342
[14] Chern, H.-H. and Hwang, H.-K. (2003). Partial match queries in random quadtrees. SIAM J. Comput. 32 904-915 (electronic). · Zbl 1053.68128 · doi:10.1137/S0097539702412131
[15] Coffman, E. G. Jr., Mallows, C. L. and Poonen, B. (1994). Parking arcs on the circle with applications to one-dimensional communication networks. Ann. Appl. Probab. 4 1098-1111. · Zbl 0812.60090 · doi:10.1214/aoap/1177004905
[16] Curien, N. and Joseph, A. (2011). Partial match queries in two-dimensional quadtrees: A probabilistic approach. Adv. in Appl. Probab. 43 178-194. · Zbl 1215.68083 · doi:10.1239/aap/1300198518 · arxiv:1009.3113
[17] Curien, N. and Kortchemski, I. (2014). Random noncrossing plane configurations: A conditioned Galton-Watson tree approach. Random Structures Algorithms . · Zbl 1301.05310 · doi:10.1002/rsa.20481 · arxiv:1201.3354
[18] Curien, N. and Le Gall, J.-F. (2011). Random recursive triangulations of the disk via fragmentation theory. Ann. Probab. 39 2224-2270. · Zbl 1252.60016 · doi:10.1214/10-AOP608 · arxiv:1006.0792
[19] Curien, N. and Werner, W. (2013). The Markovian hyperbolic triangulation. J. Eur. Math. Soc. ( JEMS ) 15 1309-1341. · Zbl 1287.60017 · doi:10.4171/JEMS/393 · arxiv:1105.5089
[20] David, F., Hagendorf, C. and Wiese, K. J. (2008). A growth model for rna secondary structures. J. Stat. Mech. Theory Exp. 2008 P04008.
[21] Duquesne, T. and Le Gall, J.-F. (2002). Random trees, Lévy processes and spatial branching processes. Astérisque 281 vi+147. · Zbl 1037.60074
[22] Duquesne, T. and Le Gall, J.-F. (2005). Probabilistic and fractal aspects of Lévy trees. Probab. Theory Related Fields 131 553-603. · Zbl 1070.60076 · doi:10.1007/s00440-004-0385-4
[23] Evans, S. N. (2008). Probability and Real Trees. Lecture Notes in Math. 1920 . Lectures from the 35 th Summer School on Probability Theory held in Saint-Flour , July 6 - 23, 2005. Springer, Berlin.
[24] Falconer, K. (1990). Fractal Geometry : Mathematical Foundations and Applications . Wiley, Chichester. · Zbl 0689.28003
[25] Falconer, K. J. (1986). The Geometry of Fractal Sets. Cambridge Tracts in Mathematics 85 . Cambridge Univ. Press, Cambridge. · Zbl 0587.28004
[26] Flajolet, P., Gonnet, G., Puech, C. and Robson, J. M. (1993). Analytic variations on quadtrees. Algorithmica 10 473-500. · Zbl 0783.68056 · doi:10.1007/BF01891833
[27] Flajolet, P. and Puech, C. (1986). Partial match retrieval of multidimensional data. J. Assoc. Comput. Mach. 33 371-407. · doi:10.1145/5383.5453
[28] Flajolet, P. and Sedgewick, R. (1995). Mellin transforms and asymptotics: Finite differences and Rice’s integrals. Theoret. Comput. Sci. 144 101-124. · Zbl 0869.68056 · doi:10.1016/0304-3975(94)00281-M
[29] Flajolet, P. and Sedgewick, R. (2009). Analytic Combinatorics . Cambridge Univ. Press, Cambridge. · Zbl 1165.05001
[30] Gromov, M. (1999). Metric Structures for Riemannian and Non-Riemannian Spaces. Progress in Mathematics 152 . Birkhäuser, Boston, MA. · Zbl 0953.53002
[31] Haas, B. and Miermont, G. (2004). The genealogy of self-similar fragmentations with negative index as a continuum random tree. Electron. J. Probab. 9 57-97 (electronic). · Zbl 1064.60076 · doi:10.1214/EJP.v9-187 · emis:journals/EJP-ECP/_ejpecp/EjpVol9/paper4.abs.html · eudml:124732
[32] Haas, B. and Miermont, G. (2012). Scaling limits of Markov branching trees with applications to Galton-Watson and random unordered trees. Ann. Probab. 40 2589-2666. · Zbl 1259.60033 · doi:10.1214/11-AOP686 · euclid:aop/1351258735 · arxiv:1003.3632
[33] Knuth, D. E. (1973). The Art of Computer Programming : Sorting and Searching . Addison-Wesley, Reading, MA. · Zbl 0302.68010
[34] Kortchemski, I. (2014). Random stable laminations of the disk. Ann. Probab. · Zbl 1304.60094 · doi:10.1214/12-AOP799 · euclid:aop/1393251301 · arxiv:1106.0271
[35] Le Gall, J.-F. (2005). Random trees and applications. Probab. Surv. 2 245-311. · Zbl 1189.60161 · doi:10.1214/154957805100000140 · eudml:229216 · arxiv:math/0511515
[36] Le Gall, J.-F. and Le Jan, Y. (1998). Branching processes in Lévy processes: The exploration process. Ann. Probab. 26 213-252. · Zbl 0948.60071 · doi:10.1214/aop/1022855417
[37] Le Gall, J.-F. and Paulin, F. (2008). Scaling limits of bipartite planar maps are homeomorphic to the 2-sphere. Geom. Funct. Anal. 18 893-918. · Zbl 1166.60006 · doi:10.1007/s00039-008-0671-x
[38] Marckert, J.-F. and Panholzer, A. (2002). Noncrossing trees are almost conditioned Galton-Watson trees. Random Structures Algorithms 20 115-125. · Zbl 1003.60077 · doi:10.1002/rsa.10016
[39] Neininger, R. and Rüschendorf, L. (2004). A general limit theorem for recursive algorithms and combinatorial structures. Ann. Appl. Probab. 14 378-418. · Zbl 1041.60024 · doi:10.1214/aoap/1075828056
[40] Neininger, R. and Sulzbach, H. (2014). On a functional contraction method. Ann. Probab. · Zbl 1372.60045
[41] Nörlund, N. E. (1924). Vorlesungen über Differenzenrechnung . Springer, Berlin. · JFM 50.0315.02
[42] Rachev, S. T. and Rüschendorf, L. (1995). Probability metrics and recursive algorithms. Adv. in Appl. Probab. 27 770-799. · Zbl 0829.60094 · doi:10.2307/1428133
[43] Ragab, M. and Roesler, U. (2014). The Quicksort process. Stochastic Process. Appl. 124 1036-1054. · Zbl 1306.60011 · doi:10.1016/j.spa.2013.09.014 · arxiv:1302.3770
[44] Revuz, D. and Yor, M. (1991). Continuous Martingales and Brownian Motion . Springer, Berlin. · Zbl 0731.60002
[45] Rösler, U. (1991). A limit theorem for “Quicksort.” RAIRO Inform. Théor. Appl. 25 85-100. · Zbl 0718.68026
[46] Sedgewick, R. and Flajolet, P. (1996). An Introduction to the Analysis of Algorithm . Addison-Wesley, Reading, MA. · Zbl 0841.68059
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.