### Increasing paths in regular trees

**Matthew Roberts**

*(University of Bath)*

**Lee Zhuo Zhao**

*(University of Cambridge)*

#### 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 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

#### References

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

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