Accessiblility Percolation with Crossing Valleys on $n$-ary Trees
| Autor: | Duque, Frank, Roldán-Correa, Alejandro, Valencia, Leon A. |
|---|---|
| Rok vydání: | 2017 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | In this paper we study a variation of the accessibility percolation model, this is also motivated by evolutionary biology and evolutionary computation. Consider a tree whose vertices are labeled with random numbers. We study the probability of having a monotone subsequence of a path from the root to a leaf, where any $k$ consecutive vertices in the path contain at least one vertex of the subsequence. An $n$-ary tree, with height $h$, is a tree whose vertices at distance at most $h-1$ to the root have $n$ children. For the case of $n$-ary trees, we prove that, as $h$ tends to infinity the probability of having such subsequence: tends to 1, if $n$ grows significantly faster than $\sqrt[k]{h/(ek)}$; and tends to 0, if $n$ grows significantly slower than $\sqrt[k]{h/(ek)}$. Comment: 14 pages, 5 figures |
| Databáze: | arXiv |
| Externí odkaz: |
|