On the Distribution of Range for Tree-Indexed Random Walks

Abstract

We study tree-indexed random walks as introduced by Benjamini, Häggström, and Mossel, i.e. labelings of a tree for which adjacent vertices have labels differing by 1. It is a conjecture of those authors that the distribution of the range for any such tree is dominated by that of a path on the same number of edges. The two main variants of this conjecture considered in the literature are the $\text{standard}$ walks, in which adjacent vertices must have labels differing by $\text{exactly}$ 1, and $\text{lazy}$ walks, in which adjacent vertices must have labels differing by $\text{at most}$ 1. We confirm this conjecture for all trees in the lazy case and provide some partial results in the standard case.

9 pages