Repository logo

The dispersion time of random walks on finite graphs

Accepted version


Conference Object

Change log


Rivera, Nicolas 
Stauffer, Alexandre 
Sauerwald, Thomas 


We study two random processes on an n-vertex graph inspired by the internal diffusion limited aggregation (IDLA) model. In both processes n particles start from an arbitrary but fixed origin. Each particle performs a simple random walk until first encountering an unoccupied vertex, and at which point the vertex becomes occupied and the random walk terminates. In one of the processes, called Sequential-IDLA, only one particle moves until settling and only then does the next particle start whereas in the second process, called Parallel-IDLA, all unsettled particles move simultaneously. Our main goal is to analyze the so-called dispersion time of these processes, which is the maximum number of steps performed by any of the n particles. In order to compare the two processes, we develop a coupling that shows the dispersion time of the Parallel-IDLA stochastically dominates that of the Sequential-IDLA; however, the total number of steps performed by all particles has the same distribution in both processes. This coupling also gives us that dispersion time of Parallel-IDLA is bounded in expectation by dispersion time of the Sequential-IDLA up to a multiplicative logn factor. Moreover, we derive asymptotic upper and lower bound on the dispersion time for several graph classes, such as cliques, cycles, binary trees, d-dimensional grids, hypercubes and expanders. Most of our bounds are tight up to a multiplicative constant.



Random Walks on Graphs, Parallelization of random processes, Interacting particle systems

Journal Title

SPAA '19: Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures

Conference Name

31st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2019)

Journal ISSN

Volume Title


Association for Computing Machinery
European Research Council (679660)
ERC Grant Dynamic March