2017/12/12 by Frank Duque, Duque, Frank, Alejandro Roldán-Correa +3
Mathematics · Physics and Astronomy · Computer Science · #Stochastic processes and statistical mechanics #Complex Network Analysis Techniques #Data Management and Algorithms
paper · pdf · doi:10.48550/arxiv.1712.04548
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 √[k]h/(ek); and tends to 0, if n grows significantly slower than √[k]h/(ek).