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{Sequential-IDLA}$, only one particle moves until settling and only then does the next particle start whereas in the second process, called $\textit{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 $\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. (PI)
Engineering and Physical Sciences Research Council
1/04/16 → 30/09/22
Project: Research council