Scaling limit for the cover time of the $λ$-biased random walk on a binary tree with $λ<1$
Author:
- David A. CroydonDCDavid A. Croydon
Preprint
Abstract
The $λ$-biased random walk on a binary tree of depth $n$ is the continuous-time Markov chain that has unit mean holding times and, when at a vertex other than the root or a leaf of the tree in question, has a probability of jumping to the parent vertex that is $λ$ times the probability of jumping to a particular child. (From the root, it chooses one of the two children with equal probability.) For this process, when $λ<1$, we derive an $n\rightarrow \infty$ scaling limit for the cover time, that is, the time taken to visit every vertex. The distributional limit is described in terms of a jump process on a Cantor set that can be seen as the asymptotic boundary of the tree. This conclusion complements previous results obtained when $λ\geq 1$.