Accessibility percolation and first-passage site percolation on the unoriented binary hypercube
A Martinsson - arXiv preprint arXiv:1501.02206, 2015 - arxiv.org
arXiv preprint arXiv:1501.02206, 2015•arxiv.org
Inspired by biological evolution, we consider the following so-called accessibility percolation
problem: The vertices of the unoriented $ n $-dimensional binary hypercube are assigned
independent $ U (0, 1) $ weights, referred to as fitnesses. A path is considered accessible if
fitnesses are strictly increasing along it. We prove that the probability that the global fitness
maximum is accessible from the all zeroes vertex converges to $1-\frac {1}{2}\ln\left (2+\sqrt
{5}\right) $ as $ n\rightarrow\infty $. Moreover, we prove that if one conditions on the location …
problem: The vertices of the unoriented $ n $-dimensional binary hypercube are assigned
independent $ U (0, 1) $ weights, referred to as fitnesses. A path is considered accessible if
fitnesses are strictly increasing along it. We prove that the probability that the global fitness
maximum is accessible from the all zeroes vertex converges to $1-\frac {1}{2}\ln\left (2+\sqrt
{5}\right) $ as $ n\rightarrow\infty $. Moreover, we prove that if one conditions on the location …
Inspired by biological evolution, we consider the following so-called accessibility percolation problem: The vertices of the unoriented -dimensional binary hypercube are assigned independent weights, referred to as fitnesses. A path is considered accessible if fitnesses are strictly increasing along it. We prove that the probability that the global fitness maximum is accessible from the all zeroes vertex converges to as . Moreover, we prove that if one conditions on the location of the fitness maximum being , then provided is not too close to the all zeroes vertex in Hamming distance, the probability that is accessible converges to a function of this distance divided by as . This resolves a conjecture by Berestycki, Brunet and Shi in almost full generality. As a second result we show that, for any graph, accessibility percolation can equivalently be formulated in terms of first-passage site percolation. This connection is of particular importance for the study of accessibility percolation on trees.
arxiv.org