Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-25T06:59:30.928Z Has data issue: false hasContentIssue false

Accessibility percolation on random rooted labeled trees

Published online by Cambridge University Press:  30 July 2019

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.

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.

Type
Research Papers
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. 172.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, 653680.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, 382388.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, 229237.CrossRefGoogle Scholar
Hegarty, P. and Martinsson, A. (2014). On the existence of accessible paths in various models of fitness landscapes. Ann. Appl. Prob. 24, 13751395.CrossRefGoogle Scholar
Janson, S. (2006). Random cutting and records in deterministic and random trees. Random Structures Algorithms 29, 139179.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, 386394.Google Scholar
Li, L. (2017). Phase transition for accessibility percolation on hypercubes. J. Theoret. Prob. 31, 20722111.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, 111114.CrossRefGoogle ScholarPubMed
Weinreich, D. M., Watson, R. A. and Chao, L. (2005). Perspective: Sign epistasis and genetic constraints on evolutionary trajectories. Evolution 59, 11651174.Google Scholar