Increasing paths in regular trees

Matthew Roberts (University of Bath)
Lee Zhuo Zhao (University of Cambridge)


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 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 that 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$.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-10

Publication Date: November 9, 2013

DOI: 10.1214/ECP.v18-2784


  • T. Aita, H. Uchiyama, T. Inaoka, M. Nakajima, T. Kokubo and Y. Husimi (2000). Analysis of a local fitness landscape with a model of the rough Mt. Fuji-type landscape: application to prolyl endopeptidase and thermolysin. Biopolymers, 54, 64--79.
  • J. Berestycki, É. Brunet and Z. Shi (2013+). How many evolutionary histories only increase fitness? Preprint, arXiv:1304.0246.
  • Franke, Jasper; Klözer, Alexander; de Visser, J. Arjan G. M.; Krug, Joachim. Evolutionary accessibility of mutational pathways. PLoS Comput. Biol. 7 (2011), no. 8, e1002134, 9 pp. MR2845072
  • J. H. Gillespie (1983). Some properties of finite populations experiencing strong selection and weak mutation. Amer. Natur., 121, 691--708.
  • P. Hegarty and A. Martinsson (2013+). On the existence of accessible paths in various models of fitness landscapes. Preprint, arXiv:1210.4798.
  • M. Kimura (1962). On the probability of fixation of mutant genes in a population. Genetics, 47, 713--719.
  • Kingman, J. F. C. A simple model for the balance between selection and mutation. J. Appl. Probability 15 (1978), no. 1, 1--12. MR0465272
  • Kauffman, Stuart; Levin, Simon. Towards a general theory of adaptive walks on rugged landscapes. J. Theoret. Biol. 128 (1987), no. 1, 11--45. MR0907587
  • S. Nowak and J. Krug (2013). Accessibility percolation on n-trees. Europhys. Lett., 101, 66004.
  • H. A. Orr (2002). The population genetics of adaptation: The adaptation of DNA sequences. Evolution, 56, 1317-–1330.
  • D. M. Weinreich, N. F. Delaney, M. A. DePristo and D. M. Hartl (2006). Darwinian evolution can follow only very few mutational paths to fitter proteins. Science, 312, 111--114.
  • D. M. Weinreich, R. A. Watson and L. Chao (2005). Perspective: Sign epistasis and genetic constraints on evolutionary trajectories. Evolution, 59, 1165--1174.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.