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.
@article{10_37236_3571,
author = {J\'anos Pach and G\'abor Tardos},
title = {The range of a random walk on a comb},
journal = {The electronic journal of combinatorics},
year = {2013},
volume = {20},
number = {3},
doi = {10.37236/3571},
zbl = {1295.05215},
url = {http://geodesic.mathdoc.fr/articles/10.37236/3571/}
}
TY - JOUR
AU - János Pach
AU - Gábor Tardos
TI - The range of a random walk on a comb
JO - The electronic journal of combinatorics
PY - 2013
VL - 20
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/3571/
DO - 10.37236/3571
ID - 10_37236_3571
ER -
%0 Journal Article
%A János Pach
%A Gábor Tardos
%T The range of a random walk on a comb
%J The electronic journal of combinatorics
%D 2013
%V 20
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/3571/
%R 10.37236/3571
%F 10_37236_3571
János Pach; Gábor Tardos. The range of a random walk on a comb. The electronic journal of combinatorics, Tome 20 (2013) no. 3. doi: 10.37236/3571
