The Range of a Random Walk on a Comb

Abstract

The graph obtained from the integer grid $\mathbb{Z}\times\mathbb{Z}$ by the removal of all horizontal edges that do not belong to the $x$-axis is called a comb. In a random walk on a graph, whenever a walker is at a vertex $v$, in the next step it will visit one of the neighbors of $v$, each with probability $1/d(v)$, where $d(v)$ denotes the degree of $v$. We answer a question of Csáki, Csörgő, Földes, Révész, and Tusnády by showing that the expected number of vertices visited by a random walk on the comb after $n$ steps is $(\frac1{2\sqrt{2\pi}}+o(1))\sqrt{n}\log n.$ This contradicts a claim of Weiss and Havlin.