Cover time for branching random walks on regular trees

Matthew I. Roberts

Published 2019-01-15Version 1

Let $T$ be the regular tree in which every vertex has exactly $d\ge 3$ neighbours. Run a branching random walk on $T$, in which at each time step every particle gives birth to a random number of children with mean $d$ and finite variance, and each of these children moves independently to a uniformly chosen neighbour of its parent. We show that, starting with one particle at some vertex $0$ and conditionally on survival of the process, the time it takes for every vertex within distance $r$ of $0$ to be hit by a particle of the branching random walk is $r + \frac{1}{\log(3/2)}\log\log r + o(\log\log r)$. As part of the proof we develop apparently new bounds on the distribution of the total progeny up to generation $n$ of a critical Galton-Watson process. These we prove using a simple minimal inequality for supermartingales.