The range of a random walk on a comb (Q396906): Difference between revisions

Summary: 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 \textit{E. Csáki} et al. [Electron. J. Probab. 14, 2371--2390 (2009; Zbl 1190.60020)] 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 \textit{G. H. Weiss} and \textit{Sh. Havlin} [``Some properties of a random walk on a comb structure'', Physica A 134, 474--482 (1986)].