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 \leq 2$. If the tooth profile is taken as a typical realization of i.i.d. heavy-tailed random variables with $\textbf{P}(H_x>z) \sim Cz^{-\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.