## The number of accessible paths in the hypercube.(English)Zbl 1341.60103

Summary: Motivated by an evolutionary biology question, we study the following problem: we consider the hypercube $$\{0,1\}^{L}$$, where each node carries an independent random variable uniformly distributed on $$[0,1]$$, except $$(1,1,\ldots,1)$$ which carries the value $$1$$ and $$(0,0,\ldots,0)$$ which carries the value $$x\in[0,1]$$. We study the number $$\Theta$$ of paths from the vertex $$(0,0,\ldots,0)$$ to the opposite vertex $$(1,1,\ldots,1)$$ along which the values on the nodes form an increasing sequence. We show that if the value on $$(0,0,\ldots,0)$$ is set to $$x=X/L$$, then $$\Theta/L$$ converges in law as $$L\to\infty$$ to $$\mathrm{e}^{-X}$$ times the product of two standard independent exponential variables. { }As a first step in the analysis, we study the same question when the graph is that of a tree where the root has arity $$L$$, each node at level 1 has arity $$L-1, \ldots$$, and the nodes at level $$L-1$$ have only one offspring which are the leaves of the tree (all the leaves are assigned the value 1, the root the value $$x\in[0,1]$$).

### MSC:

 60J80 Branching processes (Galton-Watson, birth-and-death, etc.) 60K35 Interacting random processes; statistical mechanics type models; percolation theory 92D15 Problems related to evolution

### Keywords:

branching processes; evolutionary biology; percolation; trees

OEIS
Full Text:

### References:

 [1] Aldous, D. and Steele, J.M. (2004). The objective method: Probabilistic combinatorial optimization and local weak convergence. In Probability on Discrete Structures. Encyclopaedia Math. Sci. 110 1-72. Berlin: Springer. · Zbl 1037.60008 · doi:10.1007/978-3-662-09444-0_1 [2] Altenberg, L. (1997). NK fitness landscapes. In Handbook of Evolutionary Computation (T. Bäck, D.B. Fogel and Z. Michalewicz, eds.) B2.7:5-B2.7:10. New York: Oxford Univ. Press. [3] Berestycki, J., Brunet, E. and Shi, Z. (2014). Accessibility percolation with backsteps. Preprint. Available at . arXiv:1401.6894 · Zbl 1358.60101 [4] Carneiro, M. and Hartl, D.L. (2010). Adaptive landscapes and protein evolution. Proc. Natl. Acad. Sci. USA 107, Suppl 1 1747-1751. [5] Chen, X. (2014). Increasing paths on $$N$$-ary trees. Preprint. Available at . arXiv:1403.0843 · Zbl 1349.05102 · doi:10.1007/s10587-014-0123-8 [6] Franke, J., Klözer, A., de Visser, J.A.G.M. and Krug, J. (2011). Evolutionary accessibility of mutational pathways. PLoS Comput. Biol. 7 e1002134, 9. · doi:10.1371/journal.pcbi.1002134 [7] Gillespie, J.H. (1983). A simple stochastic gene substitution model. Theor. Popul. Biol. 23 202-215. · Zbl 0507.92010 · doi:10.1016/0040-5809(83)90014-X [8] Hegarty, P. and Martinsson, A. (2014). On the existence of accessible paths in various models of fitness landscapes. Ann. Appl. Probab. 24 1375-1395. · Zbl 1325.92065 · doi:10.1214/13-AAP949 [9] Kauffman, S. and Levin, S. (1987). Towards a general theory of adaptive walks on rugged landscapes. J. Theoret. Biol. 128 11-45. · doi:10.1016/S0022-5193(87)80029-2 [10] Kingman, J.F.C. (1978). A simple model for the balance between selection and mutation. J. Appl. Probab. 15 1-12. · Zbl 0382.92003 · doi:10.2307/3213231 [11] Klozner, A. (2008). NK fitness landscapes. Diplomarbeit Universität zu Köln. [12] Lalley, S.P. and Sellke, T. (1987). A conditional limit theorem for the frontier of a branching Brownian motion. Ann. Probab. 15 1052-1061. · Zbl 0622.60085 · doi:10.1214/aop/1176992080 [13] Nowak, S. and Krug, J. (2013). Accessibility percolation on $$n$$-trees. Europhys. Lett. 101 66004. [14] On-line Encyclopedia of Integer Sequences. Available at . · Zbl 1044.11108 [15] Roberts, M.I. and Zhao, L.Z. (2013). Increasing paths in regular trees. Electron. Commun. Probab. 18 1-10. · Zbl 1306.60128 · doi:10.1214/ECP.v18-2784 [16] Weinreich, D.M., Delaney, N.F., DePristo, M.A. and Hartl, D.M. (2006). Darwinian evolution can follow only very few mutational paths to fitter proteins. Science 312 111-114. [17] Weinreich, D.M., Watson, R.A. and Chao, L. (2005). Perspective: Sign epistasis and genetic constraints on evolutionary trajectories. Evolution 59 1165-1174.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.