Increasing paths in regular trees

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 \leq 1/e$.

• Publication year

  2013

• Venue

  arXiv: Probability

• Publication date

  2013-05-03

• Fields of study

  Biology, Mathematics, Computer Science

• Identifiers
  DOI 10.1214/ECP.v18-2784arXiv 1305.0814
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• How many evolutionary histories only increase fitness

  2013cited by this paper
• Accessibility percolation on n-trees

  2013cited by this paper
• The number of accessible paths in the hypercube

  2013cited by this paper
• On the existence of accessible paths in various models of fitness landscapes

  2012cited by this paper
• Evolutionary Accessibility of Mutational Pathways

  2011cited by this paper
• Darwinian Evolution Can Follow Only Very Few Mutational Paths to Fitter Proteins

  2006cited by this paper
• PERSPECTIVE:SIGN EPISTASIS AND GENETIC CONSTRAINT ON EVOLUTIONARY TRAJECTORIES

  2005cited by this paper
• THE POPULATION GENETICS OF ADAPTATION: THE ADAPTATION OF DNA SEQUENCES

  2002cited by this paper
• Analysis of a local fitness landscape with a model of the rough Mt. Fuji-type landscape: application to prolyl endopeptidase and thermolysin.

  2000cited by this paper
• Towards a general theory of adaptive walks on rugged landscapes.

  1987cited by this paper
• Some Properties of Finite Populations Experiencing Strong Selection and Weak Mutation

  1983cited by this paper
• A simple model for the balance between selection and mutation

  1978cited by this paper
• On the probability of fixation of mutant genes in a population.

  1962cited by this paper

• Uniform Temporal Trees

  2025cites this paper
• Percolation Problems on N-Ary Trees

  2023cites this paper
• Accessibility percolation on N-ary trees

  2022cites this paper
• RMF accessibility percolation on oriented graphs

  2022cites this paper
• Open and increasing paths on N-ary trees with different fitness values

  2022cites this paper
• Accessibility percolation in random fitness landscapes

  2019cites this paper
• Accessibility Percolation with Crossing Valleys on n-ary Trees

  2019influential citation
• Accessibility percolation on random rooted labeled trees

  2019cites this paper
• Phase Transition for Accessibility Percolation on Hypercubes

  2017cites this paper
• Galton–Watson processes in varying environment and accessibility percolation

  2016cites this paper
• Phase Transition for Accessibility Percolation on Hypercubes

  2015cites this paper
• Accessibility percolation and first-passage site percolation on the unoriented binary hypercube

  2015cites this paper
• Properties of Random Fitness Landscapes and Their Influence on Evolutionary Dynamics. A Journey through the Hypercube

  2015cites this paper
• Adaptation in Tunably Rugged Fitness Landscapes: The Rough Mount Fuji Model

  2014cites this paper
• On the existence of accessibility in a tree-indexed percolation model

  2014cites this paper
• Accessibility percolation with backsteps

  2014cites this paper
• Evolutionary Accessibility of Modular Fitness Landscapes

  2013cites this paper
• The number of accessible paths in the hypercube

  2013cites this paper