  The simple random walk on $\mathbb{Z}^p$ shows two drastically different
behaviours depending on the value of $p$: it is recurrent when $p\in\{1,2\}$
while it escapes (with a rate increasing with $p$) as soon as $p\geq3$. This
classical example illustrates that the asymptotic properties of a random walk
provides some information on the structure of its state space. This paper aims
to explore analogous questions on space made up of combinatorial objects with
no algebraic structure. We take as a model for this problem the space of
unordered unlabeled rooted trees endowed with Zhang edit distance. To this end,
it defines the canonical unbiased random walk on the space of trees and
provides an efficient algorithm to evaluate its escape rate. Compared to Zhang
algorithm, it is incremental and computes the edit distance along the random
walk approximately 100 times faster on trees of size $500$ on average. The
escape rate of the random walk on trees is precisely estimated using intensive
numerical simulations, out of reasonable reach without the incremental
algorithm.
