ISSN 0253-2778

CN 34-1054/N

open
Free to Publish. Free to Read.
Open AccessOpen Access JUSTC Mathematics 13 December 2022

Accessibility percolation on N-ary trees

  • Department of Statistics and Finance, School of Management, University of Science and Technology of China, Hefei 230026, China

Cite this:
https://doi.org/10.52396/JUSTC-2022-0059
More Information
  • Author Bio:

    Zhishui Hu received his Ph.D. degree in Statistics from the University of Science and Technology of China (USTC) in 2005. He is currently an Associate Professor with the USTC. He is mainly engaged in limit theory. Related research results were published in Annals of Statistics, Journal of Applied Probability, Electronic Journal of Probability, Science China Mathematics, and other academic journals

    Liang Dong received his Ph.D. degree in Statistics from the University of Science and Technology of China in 2022. He is currently a lecturer with Nanjing University of Science and Technology. His research mainly focuses on limit theory in random graphs

  • Corresponding author: E-mail: dongliang@njust.edu.cn
  • Received Date: 30 March 2022
  • Accepted Date: 25 June 2022
    • Available Online: 13 December 2022
    Abstract

  • Abstract

    Consider a rooted $ N $-ary tree. To each of its vertices, we assign an independent and identically distributed continuous random variable. A vertex is called accessible if the assigned random variables along the path from the root to it are increasing. We study the number $C_{N,\,k}$ of accessible vertices of the first $ k $ levels and the number $ C_N $ of accessible vertices in the $ N $-ary tree. As $ N\rightarrow \infty $, we obtain the limit distribution of $C_{N,\, \beta N}$ as $ \beta $ varies from $ 0 $ to $ +\infty $ and the joint limiting distribution of $(C_{N}, C_{N,\,\alpha N+t \sqrt{\alpha N}})$ for $0 < \alpha\leqslant 1$ and $ t\in \mathbb{R} $. In this work, we also obtain a weak law of large numbers for the longest increasing path in the first $ n $ levels of the $ N $-ary tree for fixed $ N $.

    Graphical abstract

    The overall framework of our accessibility percolation on a rooted tree.

    Abstract

    Consider a rooted $ N $-ary tree. To each of its vertices, we assign an independent and identically distributed continuous random variable. A vertex is called accessible if the assigned random variables along the path from the root to it are increasing. We study the number $C_{N,\,k}$ of accessible vertices of the first $ k $ levels and the number $ C_N $ of accessible vertices in the $ N $-ary tree. As $ N\rightarrow \infty $, we obtain the limit distribution of $C_{N,\, \beta N}$ as $ \beta $ varies from $ 0 $ to $ +\infty $ and the joint limiting distribution of $(C_{N}, C_{N,\,\alpha N+t \sqrt{\alpha N}})$ for $0 < \alpha\leqslant 1$ and $ t\in \mathbb{R} $. In this work, we also obtain a weak law of large numbers for the longest increasing path in the first $ n $ levels of the $ N $-ary tree for fixed $ N $.

    • Public Summary

    • Several limit theorems for the number of accessible vertices on an N-ary tree are established.
    • The law of large numbers of the length of longest increasing paths on an N-ary tree is proved.

    FullText(HTML)
  • loading
    • References(13)
  • [1]
    Nowak S, Krug J. Accessibility percolation on n-trees. Europhysics Letters, 2013, 101 (6): 66004. doi: 10.1209/0295-5075/101/66004
    [2]
    Kingman J F C. A simple model for the balance between selection and mutation. Journal of Applied Probability, 1978, 15 (1): 1–12.
    [3]
    Kauffman S, Levin S. Towards a general theory of adaptive walks on rugged landscapes. Journal of Theoretical Biology, 1987, 128 (1): 11–45. doi: 10.1016/S0022-5193(87)80029-2
    [4]
    Roberts M I, Zhao L Z. Increasing paths in regular trees. Electronic Communications in Probability, 2013, 18: 1–10. doi: 10.1214/ECP.v18-2784
    [5]
    Chen X. Increasing paths on N-ary trees. 2014. https://arxiv.org/abs/1403.0843. Accessed March 1, 2022.
    [6]
    Duque F, Roldán-Correa A, Valencia L A. Accessibility percolation with crossing valleys on n-ary trees. Journal of Statistical Physics, 2019, 174 (5): 1027–1037. doi: 10.1007/s10955-019-02223-5
    [7]
    Coletti C F, Gava R J, Rodríguez P M. On the existence of accessibility in a tree-indexed percolation model. Physica A: Statistical Mechanics and its Applications, 2018, 492: 382–388. doi: 10.1016/j.physa.2017.10.019
    [8]
    Hegarty P, Martinsson A. On the existence of accessible paths in various models of fitness landscapes. The Annals of Applied Probability, 2014, 24 (4): 1375–1395. doi: 10.1214/13-AAP949
    [9]
    Berestycki J, Brunet E, Shi Z. The number of accessible paths in the hypercube. Bernoulli, 2016, 22 (2): 653–680. doi: 10.3150/14-BEJ641
    [10]
    Berestycki J, Brunet E, Shi Z. Accessibility percolation with backsteps. ALEA Latin American Journal of Probability and Mathematical Statistics, 2017, 14 (1): 45–62. doi: 10.30757/ALEA.v14-04
    [11]
    Li L. Phase transition for accessibility percolation on hypercubes. Journal of Theoretical Probability, 2018, 31 (4): 2072–2111. doi: 10.1007/s10959-017-0769-x
    [12]
    Krug J. Accessibility percolation in random fitness landscapes. In: Probabilistic Structures in Evolution. Berlin: EMS Press, 2021: 1–22
    [13]
    Hu Z, Li Z, Feng Q. Accessibility percolation on random rooted labeled trees. Journal of Applied Probability, 2019, 56 (2): 533–545. doi: 10.1017/jpr.2019.29
    • Supplements(0)
    • Related Articles
    • Track Citations
  • 加载中

Catalog

    |
    Get Citation
    PDF
    XML
    [1]
    Nowak S, Krug J. Accessibility percolation on n-trees. Europhysics Letters, 2013, 101 (6): 66004. doi: 10.1209/0295-5075/101/66004
    [2]
    Kingman J F C. A simple model for the balance between selection and mutation. Journal of Applied Probability, 1978, 15 (1): 1–12.
    [3]
    Kauffman S, Levin S. Towards a general theory of adaptive walks on rugged landscapes. Journal of Theoretical Biology, 1987, 128 (1): 11–45. doi: 10.1016/S0022-5193(87)80029-2
    [4]
    Roberts M I, Zhao L Z. Increasing paths in regular trees. Electronic Communications in Probability, 2013, 18: 1–10. doi: 10.1214/ECP.v18-2784
    [5]
    Chen X. Increasing paths on N-ary trees. 2014. https://arxiv.org/abs/1403.0843. Accessed March 1, 2022.
    [6]
    Duque F, Roldán-Correa A, Valencia L A. Accessibility percolation with crossing valleys on n-ary trees. Journal of Statistical Physics, 2019, 174 (5): 1027–1037. doi: 10.1007/s10955-019-02223-5
    [7]
    Coletti C F, Gava R J, Rodríguez P M. On the existence of accessibility in a tree-indexed percolation model. Physica A: Statistical Mechanics and its Applications, 2018, 492: 382–388. doi: 10.1016/j.physa.2017.10.019
    [8]
    Hegarty P, Martinsson A. On the existence of accessible paths in various models of fitness landscapes. The Annals of Applied Probability, 2014, 24 (4): 1375–1395. doi: 10.1214/13-AAP949
    [9]
    Berestycki J, Brunet E, Shi Z. The number of accessible paths in the hypercube. Bernoulli, 2016, 22 (2): 653–680. doi: 10.3150/14-BEJ641
    [10]
    Berestycki J, Brunet E, Shi Z. Accessibility percolation with backsteps. ALEA Latin American Journal of Probability and Mathematical Statistics, 2017, 14 (1): 45–62. doi: 10.30757/ALEA.v14-04
    [11]
    Li L. Phase transition for accessibility percolation on hypercubes. Journal of Theoretical Probability, 2018, 31 (4): 2072–2111. doi: 10.1007/s10959-017-0769-x
    [12]
    Krug J. Accessibility percolation in random fitness landscapes. In: Probabilistic Structures in Evolution. Berlin: EMS Press, 2021: 1–22
    [13]
    Hu Z, Li Z, Feng Q. Accessibility percolation on random rooted labeled trees. Journal of Applied Probability, 2019, 56 (2): 533–545. doi: 10.1017/jpr.2019.29
    Recommended articles
    TrendMD
    Volume 52 Issue 11 page: 2
    Cover

    Article Metrics

    Article views (477) PDF downloads(1562)
    Proportional views

    Copyright © Editorial Office of JUSTC, All Rights Reserved. 皖ICP备05002528号

    Supported by: Beijing Renhe Information Technology Co. Ltd    

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return