Accessibility Percolation with Crossing Valleys on n -ary Trees

In this paper, we study a variation of the accessibility percolation model. This work 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 \(\root k \of {h/(ek)}\); and tends to 0, if n grows significantly slower than \(\root k \of {h/(ek)}\).