Accessible Percolation with Crossing Valleys on $n$-ary Trees

Frank Duque, Alejandro Roldán-Correa, Leon A. Valencia

Published 2017-12-12Version 1

In this paper, also motivated by evolutionary biology and evolutionary computation, we study a variation of the accessibility percolation model. 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 leave, 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 proof that, as $h$ tends to infinity the probability of having such subsequence: tends to 1, if $n(h)\geq c\sqrt[k]{h/(ek)} $ and $c>1$; and tends to 0, if $n(h)\leq c\sqrt[k]{h/(ek)} $ and $c<1$.