The small world effect on the coalescing time of random walks

STOCHASTIC PROCESSES AND THEIR APPLICATIONS

卷:121

Article

Bertacchi, Daniela²  Borrello, Davide^1,2 

[1] Univ Rouen, CNRS, UMR 6085, Lab Math Raphael Salem, F-76801 St Etienne, France

[2] Univ Milano Bicocca, Dipartimento Matemat & Applicaz, I-20125 Milan, Italy

关键词: Small world;    Random walk;    Coalescing random walk;   

DOI  :  10.1016/j.spa.2011.01.003

来源: Elsevier

【 摘 要 】

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.

【 授权许可】

Free