The small world effect on the coalescing time of random walks

Daniela Bertacchi and Davide Borrello

Stochastic Processes and their Applications, 2011, vol. 121, issue 5, 925-956

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 TL 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 TL by a factor C1L2 if d=1, by C2L2logL if d=2 and CdLd if d>=3. We prove that on the small world the rescaling factor is and identify the constant , proving that the walks always meet faster on the small world than on the torus 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.

Keywords: Small; world; Random; walk; Coalescing; random; walk (search for similar items in EconPapers)
Date: 2011
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0304-4149(11)00015-9
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:spapps:v:121:y:2011:i:5:p:925-956

Ordering information: This journal article can be ordered from
http://http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

Access Statistics for this article

Stochastic Processes and their Applications is currently edited by T. Mikosch

More articles in Stochastic Processes and their Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().