Projects per year
Abstract
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 $\textit{SequentialIDLA}$, only one particle moves until settling and only then does the next particle start whereas in the second process, called $\textit{ParallelIDLA}$, all unsettled particles move simultaneously. Our main goal is to analyze the socalled 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 ParallelIDLA stochastically dominates that of the SequentialIDLA; 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 ParallelIDLA is bounded in expectation by dispersion time of the SequentialIDLA up to a multiplicative $\log n$ 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.
Original language  English 

Journal  Preprint on arXiv 
DOIs  
Publication status  Published  30 Jun 2019 
Bibliographical note
35 pages, 1 tableKeywords
 cs.DM
 math.CO
 math.PR
Fingerprint
Dive into the research topics of 'The dispersion time of random walks on finite graphs'. Together they form a unique fingerprint.Projects
 1 Finished

Early Career Fellowship  Mathematical Analysis of Strongly Correlated Processes on Discrete Dynamic Structures
Stauffer, A.
Engineering and Physical Sciences Research Council
1/04/16 → 30/09/22
Project: Research council