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*logL if d=2 and C_d*L^d if d≥3. We prove that on the small world the rescaling factor is C_d^\prime*L^d and identify the constant C_d^\prime source, 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

Bertacchi, D., Borrello, D. (2011). The small world effect on the coalescing time of random walks. STOCHASTIC PROCESSES AND THEIR APPLICATIONS, 121(5), 925-956 [10.1016/j.spa.2011.01.003].

### 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*logL if d=2 and C_d*L^d if d≥3. We prove that on the small world the rescaling factor is C_d^\prime*L^d and identify the constant C_d^\prime source, 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
##### Scheda breve Scheda completa Scheda completa (DC)
Articolo in rivista - Articolo scientifico
Coalescing random walk; Random walk; Small world
English
2011
925
956
32
Bertacchi, D., Borrello, D. (2011). The small world effect on the coalescing time of random walks. STOCHASTIC PROCESSES AND THEIR APPLICATIONS, 121(5), 925-956 [10.1016/j.spa.2011.01.003].
File in questo prodotto:
File
The_small_world_effect_on_the_coalescing_time_of_random_walks.pdf

Solo gestori archivio

Dimensione 360.76 kB
Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/26700