On the phase transition for the number of collisions on comb graphs

Abstract

We consider collisions of simple random walks on comb graphs $\mathrm{Comb}(\mathbb{Z},H)$, which are obtained by attaching vertical segments of the form $[0,H_x]\cap \mathbb{Z}$ to any point $x$ of the integer axis. For $\mathrm{Comb}(\mathbb{Z},H)$ with profile $H_x(x)=|x|{\log }^{\gamma }(|x|\vee 1)$, we show that two independent simple random walks starting from the same site collide infinitely often almost surely if $\gamma \le 2$. If the tooth profile is taken as a typical realization of i.i.d. heavy-tailed random variables with $\text{P}(H_x>z)\sim C{z}^{-\gamma }$ (with some $C>0$) as $z$ tends to infinity, we show that infinitely many collisions occur almost surely for two independent random walks if $\gamma >1/3$, whereas finitely many collisions occur almost surely if $\gamma \in (0,1/3)$, and for any $\gamma \in (0,1]$, three independent random walks only collide finitely many times, almost surely.

48 pages, 3 figures