Increasing paths in regular trees

Abstract

We consider a regular $n$-ary tree of height $h$, for which every vertex except the root is labelled with an independent and identically distributed continuous random variable. Taking motivation from a question in evolutionary biology, we consider the number of simple paths from the root to a leaf along vertices with increasing labels. We show that if $\alpha =n/h$ is fixed and $\alpha >1/e$, the probability there exists such a path converges to 1 as $h\to \infty$. This complements a previously known result that the probability converges to 0 if $\alpha \le 1/e$.

Version published at http://ecp.ejpecp.org/article/view/2784 in Electronic Communications in Probability

References in corpus (3)

• On the existence of accessible paths in various models of fitness landscapes
• The number of accessible paths in the hypercube
• Accessibility percolation on n-trees

Cited by in corpus (7)

• Adaptation in tunably rugged fitness landscapes: The Rough Mount Fuji Model
• Evolutionary accessibility of modular fitness landscapes
• The number of accessible paths in the hypercube
• Accessibility percolation and first-passage site percolation on the unoriented binary hypercube
• On the existence of accessibility in a tree-indexed percolation model
• Phase transition for accessibility percolation on hypercubes
• RMF accessibility percolation on oriented graphs