Explosion and linear transit times in infinite trees

详细信息    查看全文

• 作者：Omid Amini ; Luc Devroye ; Simon Griffiths…
• 关键词：Mathematics Subject Classification60K35 ; 60C05 ; 60G55 ; 60J80 ; 05C80
• 刊名：Probability Theory and Related Fields
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：167
• 期：1-2
• 页码：325-347
• 全文大小：
• 刊物类别：Mathematics and Statistics
• 刊物主题：Probability Theory and Stochastic Processes; Theoretical, Mathematical and Computational Physics; Quantitative Finance; Mathematical and Computational Biology; Statistics for Business/Economics/Mathem
• 出版者：Springer Berlin Heidelberg
• ISSN：1432-2064
• 卷排序：167

文摘

Let T be an infinite rooted tree with weights \(w_e\) assigned to its edges. Denote by \(m_n(T)\) the minimum weight of a path from the root to a node of the nth generation. We consider the possible behaviour of \(m_n(T)\) with focus on the two following cases: we say T is explosive if $$\begin{aligned} \lim _{n\rightarrow \infty }m_n(T)\, <\, \infty \,, \end{aligned}$$and say that T exhibits linear growth if $$\begin{aligned} \liminf _{n\rightarrow \infty }\, \frac{m_n(T)}{n}\, > \, 0\,. \end{aligned}$$We consider a class of infinite randomly weighted trees related to the Poisson-weighted infinite tree, and determine precisely which trees in this class have linear growth almost surely. We then apply this characterization to obtain new results concerning the event of explosion in infinite randomly weighted spherically-symmetric trees, answering a question of Pemantle and Peres (Ann Probab 22(1), 180–194, 1994). As a further application, we consider the random real tree generated by attaching sticks of deterministic decreasing lengths, and determine for which sequences of lengths the tree has finite height almost surely.Mathematics Subject Classification60K3560C0560G5560J8005C80References1.Addario-Berry, L., Griffiths, S., Kang, R.J.: Invasion percolation on the Poisson-weighted infinite tree. Ann. Appl. Probab. 22(3), 931–970 (2012)MathSciNetCrossRefMATHGoogle Scholar2.Addario-Berry, L., Reed, B.: Minima in branching random walks. Ann. Appl. Probab. 37, 1044–1079 (2009)MathSciNetCrossRefMATHGoogle Scholar3.Aïdekon, E.: Convergence in law of the minimum of a branching random walk. Ann. Probab. 41(3A), 1362–1426 (2013)MathSciNetCrossRefMATHGoogle Scholar4.Aïdekon, E., Shi, Z.: The Seneta–Heyde scaling for the branching random walk. Ann. Probab. 42(3), 959–993 (2014)MathSciNetCrossRefMATHGoogle Scholar5.Aldous, D.J.: The continuum random tree I. Ann. Probab. 19, 1–28 (1991)MathSciNetCrossRefMATHGoogle Scholar6.Aldous, D.J.: Asymptotics in the random assignment problem. Probab. Theory Related Fields 93, 507–534 (1992)MathSciNetCrossRefMATHGoogle Scholar7.Aldous, D.J.: The continuum random tree III. Ann. Probab. 21, 248–289 (1993)MathSciNetCrossRefMATHGoogle Scholar8.Aldous, D.J., Pitman, J.: Inhomogeneous continuum random trees and the entrance boundary of the additive coalescent. Probab. Theory Related Fields 118, 455–482 (2000)MathSciNetCrossRefMATHGoogle Scholar9.Aldous, D.J., Steele, J.M.: The objective method: probabilistic combinatorial optimization and local weak convergence. In: Kesten, H. (ed.) Probability on Discrete Structures, Encyclopedia of Mathematical Sciences, vol. 110, pp. 1–72. Springer, Berlin (2003)CrossRefGoogle Scholar10.Amini, O., Devroye, L., Griffiths, S., Olver, N.: On explosions in heavy-tailed branching random walks. Ann. Probab. 41(3B), 1864–1899 (2013)MathSciNetCrossRefMATHGoogle Scholar11.Biggins, J.D.: The first- and last-birth problems for a multitype age-dependent branching process. Adv. Appl. Probab. 8, 446–459 (1976)MathSciNetCrossRefMATHGoogle Scholar12.Biggins, J.D.: Chernoff’s theorem in the branching random walk. J. Appl. Probab. 14(3), 630–636 (1977)MathSciNetCrossRefMATHGoogle Scholar13.Bordenave, C., Caputo, C., Chafaï, D.: Spectrum of large random reversible Markov chains: heavy-tailed weights on the complete graph. Ann. Probab. 39(4), 1544–1590 (2011)MathSciNetCrossRefMATHGoogle Scholar14.Bramson, M.D.: Minimal displacement of branching random walks. Z. Wahrsch. Verw. Gebiete 45, 89–108 (1978)MathSciNetCrossRefMATHGoogle Scholar15.Curien, N.: Open question at the probability. In: Combinatorics and Geometry Workshop. McGill University’s Bellairs Institute, Barbados (2014)16.Curien, N., Haas, B.: Random trees constructed by aggregation. arXiv:1411.4255 17.Dekking, F.M., Host, B.: Limit distributions for minimal displacement of branching random walks. Probab. Theory Related Fields 90, 403–426 (1991)MathSciNetCrossRefMATHGoogle Scholar18.Goldschmidt, C., Haas, B.: A line-breaking construction of the stable trees (2014). arXiv:1407.5691 19.Hammersley, J.M.: Postulates for subadditive processes. Ann. Probab. 2, 652–680 (1974)MathSciNetCrossRefMATHGoogle Scholar20.Hu, Y., Shi, Z.: Minimal position and critical martingale convergence in branching random walks, and directed polymers on disordered trees. Ann. Probab. 37, 742–789 (2009)MathSciNetCrossRefMATHGoogle Scholar21.Kingman, J.F.: The first birth problem for an age-dependent branching process. Ann. Probab. 3, 790–801 (1975)MathSciNetCrossRefMATHGoogle Scholar22.McDiarmid, C.: Minimal positions in a branching random walk. Ann. Appl. Probab. 5, 128–139 (1995)MathSciNetCrossRefMATHGoogle Scholar23.Pemantle, R., Peres, Y.: Domination between trees and application to an explosion problem. Ann. Probab. 22(1), 180–194 (1994)MathSciNetCrossRefMATHGoogle Scholar24.Vatutin, V.A.: On the explosiveness of nonhomogeneous age-dependent branching processes. Theory Probab. Math. Stat. 52, 39–42 (1996) [translated from Teor. Imovir. Mat. Stat. No. 52, 37–40 (1995, Ukrainian)]25.Vatutin, V.A., Zubkov, A.M.: Branching processes II. Probability theory and mathematical statistics, 1. J. Soviet Math. 67, 3407–3485 (1993)CrossRefMATHGoogle ScholarCopyright information© Springer-Verlag Berlin Heidelberg 2015Authors and AffiliationsOmid Amini1Email authorLuc Devroye2Simon Griffiths3Neil Olver451.CNRS, DMA, École Normale SupérieureParisFrance2.School of Computer ScienceMcGill UniversityMontrealCanada3.Department of StatisticsUniversity of OxfordOxfordUK4.Department of Econometrics and Operations ResearchVrije Universiteit AmsterdamAmsterdamThe Netherlands5.CWIAmsterdamThe Netherlands About this article CrossMark Publisher Name Springer Berlin Heidelberg Print ISSN 0178-8051 Online ISSN 1432-2064 About this journal Reprints and Permissions Article actions .buybox { margin: 16px 0 0; position: relative; } .buybox { font-family: Source Sans Pro, Helvetica, Arial, sans-serif; font-size: 14px; font-size: .875rem; } .buybox { zoom: 1; } .buybox:after, .buybox:before { content: ''; display: table; } .buybox:after { clear: both; } /*---------------------------------*/ .buybox .buybox__header { border: 1px solid #b3b3b3; border-bottom: 0; padding: 8px 12px; position: relative; background-color: #f2f2f2; } .buybox__header .buybox__login { font-family: Source Sans Pro, Helvetica, Arial, sans-serif; font-size: 14px; font-size: .875rem; letter-spacing: .017em; display: inline-block; line-height: 1.2; padding: 0; } .buybox__header .buybox__login:before { position: absolute; top: 50%; -webkit-transform: perspective(1px) translateY(-50%); transform: perspective(1px) translateY(-50%); content: '\A'; width: 34px; height: 34px; left: 10px; } /*---------------------------------*/ .buybox .buybox__body { padding: 0; padding-bottom: 16px; position: relative; text-align: center; background-color: #fcfcfc; border: 1px solid #b3b3b3; } .buybox__body .buybox__section { padding: 16px 12px 0 12px; text-align: left; } .buybox__section .buybox__buttons { text-align: center; width: 100%; } /********** mycopy buybox specific **********/ .buybox.mycopy__buybox .buybox__section .buybox__buttons { border-top: 0; padding-top: 0; } /******/ .buybox__section:nth-child(2) .buybox__buttons { border-top: 1px solid #b3b3b3; padding-top: 20px; } .buybox__buttons .buybox__buy-button { display: inline-block; text-align: center; margin-bottom: 5px; padding: 6px 12px; } .buybox__buttons .buybox__price { white-space: nowrap; text-align: center; font-size: larger; padding-top: 6px; } .buybox__section .buybox__meta { letter-spacing: 0; padding-top: 12px; } .buybox__section .buybox__meta:only-of-type { padding-top: 0; position: relative; bottom: 6px; } /********** mycopy buybox specific **********/ .buybox.mycopy__buybox .buybox__section .buybox__meta { margin-top: 0; margin-bottom: 0; } /******/ .buybox__meta .buybox__product-title { display: inline; font-weight: bold; } .buybox__meta .buybox__list { line-height: 1.3; } .buybox__meta .buybox__list li { position: relative; padding-left: 1em; list-style: none; margin-bottom: 5px; } .buybox__meta .buybox__list li:before { font-size: 1em; content: '\2022'; float: left; position: relative; top: .1em; font-family: serif; font-weight: 600; text-align: center; line-height: inherit; color: #666; width: auto; margin-left: -1em; } .buybox__meta .buybox__list li:last-child { margin-bottom: 0; } /*---------------------------------*/ .buybox .buybox__footer { border: 1px solid #b3b3b3; border-top: 0; padding: 8px 12px; position: relative; border-style: dashed; } /*-----------------------------------------------------------------*/ @media screen and (min-width: 460px) and (max-width: 1074px) { .buybox__body .buybox__section { display: inline-block; vertical-align: top; padding: 12px 12px; padding-bottom: 0; text-align: left; width: 48%; } .buybox__body .buybox__section { padding-top: 16px; padding-left: 0; } .buybox__section:nth-of-type(2) .buybox__meta { border-left: 1px solid #d3d3d3; padding-left: 28px; } .buybox__section:nth-of-type(2) .buybox__buttons { border-top: 0; padding-top: 0; padding-left: 16px ; } .buybox__buttons .buybox__buy-button { } /********** article buybox specific **********/ .buybox.article__buybox .buybox__section:nth-of-type(2) { margin-top: 16px; padding-top: 0; } .buybox.article__buybox .buybox__section:nth-of-type(2) .buybox__meta { margin-top: 40px; padding-top: 0; padding-bottom: 45px; } .buybox.article__buybox .buybox__section:nth-of-type(2) .buybox__meta:only-of-type { margin-top: 8px; padding-top: 12px; padding-bottom: 12px; } /********** mycopy buybox specific **********/ .buybox.mycopy__buybox .buybox__section:first-child { width: 69%; } .buybox.mycopy__buybox .buybox__section:last-child { width: 29%; } /******/ } /*-----------------------------------------------------------------*/ @media screen and (max-width: 459px) { /********** mycopy buybox specific **********/ .buybox.mycopy__buybox .buybox__body { padding-bottom: 5px; } .buybox.mycopy__buybox .buybox__section:last-child { text-align: center; width: 100%; } .buybox.mycopy__buybox .buybox__buttons { display: inline-block; width: 150px ; } /******/ } /*-----------------------------------------------------------------*/ Log in to check access Buy (PDF) EUR 34,95 Unlimited access to the full article Instant download Include local sales tax if applicable Subscribe to Journal Get Access to Probability Theory and Related Fields for the whole of 2017 Find out about institutional subscriptions (function () { var forEach = function (array, callback, scope) { for (var i = 0; i Export citation .RIS Papers Reference Manager RefWorks Zotero .ENW EndNote .BIB BibTeX JabRef Mendeley Share article Email Facebook Twitter LinkedIn Cookies We use cookies to improve your experience with our site. More information Accept Over 10 million scientific documents at your fingertips