The small world effect on the coalescing time of random walks

A small world is obtained from the d -dimensional torus of size 2 L 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 ≥ 3 . We prove that on the small world the rescaling factor is C d ′ L d and identify the constant C d ′ , proving that the walks always meet faster on the small world than on the torus if d ≤ 2 , while if d ≥ 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.