Show simple item record

dc.contributor.authorRivera, Nicolasen
dc.contributor.authorStauffer, Alexandreen
dc.contributor.authorSauerwald, Thomasen
dc.contributor.authorSylvester, Johnen
dc.date.accessioned2019-07-04T10:05:47Z
dc.date.available2019-07-04T10:05:47Z
dc.date.issued2019-06-25en
dc.identifier.urihttps://www.repository.cam.ac.uk/handle/1810/294353
dc.description.abstractWe 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.sponsorshipERC Grant Dynamic March
dc.publisherAssociation for Computing Machinery
dc.titleThe dispersion time of random walks on finite graphsen
dc.typeConference Object
prism.endingPage113
prism.publicationDate2019en
prism.publicationNameSPAA '19: Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architecturesen
prism.startingPage103
dc.identifier.doi10.17863/CAM.41451
dcterms.dateAccepted2019-04-30en
rioxxterms.versionofrecord10.1145/3323165.3323204en
rioxxterms.versionAM*
rioxxterms.licenseref.urihttp://www.rioxx.net/licenses/all-rights-reserveden
rioxxterms.licenseref.startdate2019-06-25en
dc.contributor.orcidSylvester, John [0000-0002-6543-2934]
rioxxterms.typeConference Paper/Proceeding/Abstracten
pubs.funder-project-idECH2020 EUROPEAN RESEARCH COUNCIL (ERC) (679660)
pubs.conference-name31st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2019)en
pubs.conference-start-date2019-06-22en


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record