dc.contributor.author Rivera, Nicolas en dc.contributor.author Stauffer, Alexandre en dc.contributor.author Sauerwald, Thomas en dc.contributor.author Sylvester, John en dc.date.accessioned 2019-07-04T10:05:47Z dc.date.available 2019-07-04T10:05:47Z dc.date.issued 2019-06-25 en dc.identifier.uri https://www.repository.cam.ac.uk/handle/1810/294353 dc.description.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. dc.description.sponsorship ERC Grant Dynamic March dc.publisher Association for Computing Machinery dc.title The dispersion time of random walks on finite graphs en dc.type Conference Object prism.endingPage 113 prism.publicationDate 2019 en prism.publicationName SPAA '19: Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures en prism.startingPage 103 dc.identifier.doi 10.17863/CAM.41451 dcterms.dateAccepted 2019-04-30 en rioxxterms.versionofrecord 10.1145/3323165.3323204 en rioxxterms.version AM * rioxxterms.licenseref.uri http://www.rioxx.net/licenses/all-rights-reserved en rioxxterms.licenseref.startdate 2019-06-25 en dc.contributor.orcid Sylvester, John [0000-0002-6543-2934] rioxxterms.type Conference Paper/Proceeding/Abstract en pubs.funder-project-id ECH2020 EUROPEAN RESEARCH COUNCIL (ERC) (679660) pubs.conference-name 31st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2019) en pubs.conference-start-date 2019-06-22 en
﻿