Hostname: page-component-78c5997874-ndw9j Total loading time: 0 Render date: 2024-11-05T05:03:40.399Z Has data issue: false hasContentIssue false
  • English
  • Français

Accessibility percolation on random rooted labeled trees

Part of: Limit theorems Graph theory Combinatorial probability

Published online by Cambridge University Press:  30 July 2019

Zhishui Hu ,
Zheng Li  and
Qunqiang Feng
Zhishui Hu*
Affiliation:
University of Science and Technology of China
Zheng Li*
Affiliation:
University of Science and Technology of China
Qunqiang Feng*
Affiliation:
University of Science and Technology of China
*
*Postal address: Department of Statistics and Finance, School of Management, University of Science and Technology of China, Hefei 230026, China.
*Postal address: Department of Statistics and Finance, School of Management, University of Science and Technology of China, Hefei 230026, China.
*Postal address: Department of Statistics and Finance, School of Management, University of Science and Technology of China, Hefei 230026, China.
Get access Rights & Permissions [Opens in a new window]

Abstract

The accessibility percolation model is investigated on random rooted labeled trees. More precisely, the number of accessible leaves (i.e. increasing paths) Zn and the number of accessible vertices Cn in a random rooted labeled tree of size n are jointly considered in this work. As n → ∞, we prove that (Zn, Cn) converges in distribution to a random vector whose probability generating function is given in an explicit form. In particular, we obtain that the asymptotic distributions of Zn + 1 and Cn are geometric distributions with parameters e/(1 + e) and 1/e, respectively. Much of our analysis is performed in the context of local weak convergence of random rooted labeled trees.

Keywords

Accessibility percolationrandom treeincreasing pathaccessible vertexlocal weak convergence

MSC classification

Primary: 05C05: Trees 60C05: Combinatorial probability
Secondary: 60F05: Central limit and other weak theorems
Type
Research Papers
Information
Journal of Applied Probability , Volume 56 , Issue 2 , June 2019 , pp. 533 - 545
Copyright
© Applied Probability Trust 2019 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Aldous, D. J. and Steele, J. M. (2004). The objective method: Probabilistic combinatorial optimization and local weak convergence. In Probability on Discrete Structures, ed. Kesten, H., Vol. 110 of Encyclopaedia of Mathematical Sciences. Springer, Berlin, pp. 1–72.Google Scholar
Benjamini, I. and Schramm, O. (2001). Recurrence of distributional limits of finite planar graphs. Electron. J. Prob. 6, 23.CrossRefGoogle Scholar
Berestycki, J., Brunet, É. and Shi, Z. (2016). The number of accessible paths in the hypercube. Bernoulli 22, 653–680.CrossRefGoogle Scholar
Chen, X. (2014). Increasing paths on N-ary trees. Preprint, arXiv:1403.0843.Google Scholar
Coletti, C. F., Gava, R. J. and Rodríguez, P. M. (2018). On the existence of accessibility in a tree-indexed percolation model. Physica A 492, 382–388.CrossRefGoogle Scholar
Drmota, M. (2009). Random Trees: An Interplay between Combinatorics and Probability. Springer, Wien.CrossRefGoogle Scholar
Franke, J., Klözer, A., De Visser, J. A. G. M. and Krug, J. (2011). Evolutionary accessibility of mutational pathways. PLoS Comput. Biol. 7, e1002134.CrossRefGoogle ScholarPubMed
Grimmett, G. R. (1980). Random labelled trees and their branching networks. J. Austral. Math. Soc. (Ser. A) 30, 229–237.CrossRefGoogle Scholar
Hegarty, P. and Martinsson, A. (2014). On the existence of accessible paths in various models of fitness landscapes. Ann. Appl. Prob. 24, 1375–1395.CrossRefGoogle Scholar
Janson, S. (2006). Random cutting and records in deterministic and random trees. Random Structures Algorithms 29, 139–179.CrossRefGoogle Scholar
Kallenberg, O. (2002). Foundations of Modern Probability, 2nd ed. Springer, Berlin.CrossRefGoogle Scholar
Kolchin, V. F. (1977). Branching processes, random trees, and a generalized scheme of arrangements of particles. Math. Notes Acad. Sci. USSR 21, 386–394.Google Scholar
Li, L. (2017). Phase transition for accessibility percolation on hypercubes. J. Theoret. Prob. 31, 2072–2111.CrossRefGoogle Scholar
Nowak, S. and Krug, J. (2013). Accessibility percolation on n-trees. Europhys. Lett. 101, 66004.CrossRefGoogle Scholar
Roberts, M. I. and Zhao, L. Z. (2013). Increasing paths in regular trees. Electron. Commun. Prob. 18, 87.CrossRefGoogle Scholar
Weinreich, D. M., Delaney, N. F., Depristo, M. A. and Hartl, D. M. (2006). Darwinian evolution can follow only very few mutational paths to fitter proteins. Science 312, 111–114.CrossRefGoogle ScholarPubMed
Weinreich, D. M., Watson, R. A. and Chao, L. (2005). Perspective: Sign epistasis and genetic constraints on evolutionary trajectories. Evolution 59, 1165–1174.Google Scholar