The frog model is a branching random walk on a graph in which particles branch only at unvisited sites. Consider an initial particle density of $mu$ on the full $d$-ary tree of height $n$. If $mu= Omega( d^2)$, all of the vertices are visited in time $Theta(nlog n)$ with high probability. Conversely, if $mu = O(d)$ the cover time is $exp(Theta(sqrt n))$ with high probability.
تحميل البحث