Accessibility percolation with backsteps

MaRDI QIDQ2964177zbMATH OpenFDO

Authors Julien Berestycki, Éric Brunet, Zhan Shi

Publication date 23 February 2017

Full work available at URL https://arxiv.org/abs/1401.6894, http://alea.impa.br/articles/v14/14-04.pdf

zbMATH Keywords

accessibility percolationevolutionary biology

Mathematics Subject Classification ID

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

Abstract: Consider a graph in which each site is endowed with a value called emph{fitness}. A path in the graph is said to be "open" or "accessible" if the fitness values along that path is strictly increasing. We say that there is accessibility percolation between two sites when such a path between them exists. Motivated by the so called House-of-Cards model from evolutionary biology, we consider this question on the $L$-hypercube ${0,1}^L$ where the fitness values are independent random variables. We show that, in the large $L$ limit, the probability that an accessible path exists from an arbitrary starting point to the (random) fittest site is no more than $x_{1/2}^{\ast }=1-frac12sin{h}^{-1}(2)=0.27818ldots$ and we conjecture that this probability does converge to $x_{1/2}^{\ast }$. More precisely, there is a phase transition on the value of the fitness $x$ of the starting site: assuming that the fitnesses are uniform in $[0,1]$, we show that, in the large $L$ limit, there is almost surely no path to the fittest site if $x>x_{1/2}^{\ast }$ and we conjecture that there are almost surely many paths if $x<x_{1/2}^{\ast }$. If one conditions on the fittest site to be on the opposite corner of the starting site rather than being randomly chosen, the picture remains the same but with the critical point being now $x_1^{\ast }=1-sin{h}^{-1}(1)=0.11863ldots$. Along the way, we obtain a large $L$ estimation for the number of self-avoiding paths joining two opposite corners of the $L$-hypercube.

Recommendations

• Accessibility percolation on Cartesian power graphs
• Phase transition for accessibility percolation on hypercubes
• On the existence of accessible paths in various models of fitness landscapes
• The number of accessible paths in the hypercube
• Evolutionary accessibility of modular fitness landscapes

Cites work

• A simple model for the balance between selection and mutation
• A simple stochastic gene substitution model
• Evolutionary accessibility of modular fitness landscapes
• scientific article; zbMATH DE number 960162 (Why is no real title available?)
• Increasing paths in regular trees
• On the existence of accessible paths in various models of fitness landscapes
• Percolation, first-passage percolation and covering times for Richardson's model on the \(n\)-cube
• The number of accessible paths in the hypercube
• Unoriented first-passage percolation on the n-cube

Cited in

(12)

• Universality classes of interaction structures for NK fitness landscapes
• Phase transition for accessibility percolation on hypercubes
• On the existence of accessibility in a tree-indexed percolation model
• From adaptive dynamics to adaptive walks
• Accessibility percolation with crossing valleys on n-ary trees
• On the existence of accessible paths in various models of fitness landscapes
• The number of accessible paths in the hypercube
• Accessibility percolation on Cartesian power graphs
• Undirected polymers in random environment: path properties in the mean field limit
• RMF accessibility percolation on oriented graphs
• A general multi-scale description of metastable adaptive motion across fitness valleys
• Evolutionary accessibility of random and structured fitness landscapes

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Accessibility percolation with backsteps

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2964177)