The small world effect on the coalescing time of random walks

Abstract

A small world is obtained from the $d$-dimensional torus of size 2L adding randomly chosen connections between sites, in a way such that each site has exactly one random neighbour in addition to its deterministic neighbours. We study the asymptotic behaviour of the meeting time $T_L$ of two random walks moving on this small world and compare it with the result on the torus. On the torus, in order to have convergence, we have to rescale $T_L$ by a factor $C_1{L}^2$ if $d=1$, by $C_2{L}^2\log L$ if $d=2$ and $C_d{L}^d$ if $d\ge 3$. We prove that on the small world the rescaling factor is $C_d^{\prime }{L}^d$ and identify the constant $C_d^{\prime }$, proving that the walks always meet faster on the small world than on the torus if $d\le 2$, while if $d\ge 3$ this depends on the probability of moving along the random connection. As an application, we obtain results on the hitting time to the origin of a single walk and on the convergence of coalescing random walk systems on the small world.

33 pages, 2 figures, revised arguments, results unchanged

Cited by in corpus (1)

• Branching random walks and multi-type contact-processes on the percolation cluster of ${\mathbb{Z}}^d$