Accessibility percolation with backsteps
Consider a graph in which each site is endowed with a value called fitness. A path in the graph is said to be “open” or “accessible” if the fitness values along that path are strictly increasing. We say that there is accessibility percolation between two sites when such a path between them exists. M...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Published: |
Instituto Nacional de Matemática Pura e Aplicada
2017
|
| _version_ | 1826263110403489792 |
|---|---|
| author | Berestycki, J Brunet, É Shi, Z |
| author_facet | Berestycki, J Brunet, É Shi, Z |
| author_sort | Berestycki, J |
| collection | OXFORD |
| description | Consider a graph in which each site is endowed with a value called fitness. A path in the graph is said to be “open” or “accessible” if the fitness values along that path are 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 = 1− 1 2 sinh−1 (2) = 0.27818 . . . and we conjecture that this probability does converge to x ∗ 1/2 . 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 and we conjecture that there are almost surely many paths if x < x∗ 1/2 . 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 = 1 − sinh−1 (1) = 0.11863 . . .. Along the way, we obtain a large L estimation for the number of self-avoiding paths joining two opposite corners of the L-hypercube. |
| first_indexed | 2024-03-06T19:46:30Z |
| format | Journal article |
| id | oxford-uuid:227a5cc8-dc1e-455f-86b4-240055529c74 |
| institution | University of Oxford |
| last_indexed | 2024-03-06T19:46:30Z |
| publishDate | 2017 |
| publisher | Instituto Nacional de Matemática Pura e Aplicada |
| record_format | dspace |
| spelling | oxford-uuid:227a5cc8-dc1e-455f-86b4-240055529c742022-03-26T11:39:02ZAccessibility percolation with backstepsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:227a5cc8-dc1e-455f-86b4-240055529c74Symplectic Elements at OxfordInstituto Nacional de Matemática Pura e Aplicada2017Berestycki, JBrunet, ÉShi, ZConsider a graph in which each site is endowed with a value called fitness. A path in the graph is said to be “open” or “accessible” if the fitness values along that path are 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 = 1− 1 2 sinh−1 (2) = 0.27818 . . . and we conjecture that this probability does converge to x ∗ 1/2 . 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 and we conjecture that there are almost surely many paths if x < x∗ 1/2 . 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 = 1 − sinh−1 (1) = 0.11863 . . .. Along the way, we obtain a large L estimation for the number of self-avoiding paths joining two opposite corners of the L-hypercube. |
| spellingShingle | Berestycki, J Brunet, É Shi, Z Accessibility percolation with backsteps |
| title | Accessibility percolation with backsteps |
| title_full | Accessibility percolation with backsteps |
| title_fullStr | Accessibility percolation with backsteps |
| title_full_unstemmed | Accessibility percolation with backsteps |
| title_short | Accessibility percolation with backsteps |
| title_sort | accessibility percolation with backsteps |
| work_keys_str_mv | AT berestyckij accessibilitypercolationwithbacksteps AT brunete accessibilitypercolationwithbacksteps AT shiz accessibilitypercolationwithbacksteps |