The small world effect on the coalescing time of random walks

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 C1L2 if d = 1, by C2L2 log L if d = 2 and CdLd if d >= 3. We prove that on the small world the resealing 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. (C) 2011 Elsevier B.V. All rights reserved.