# RANDOM WALKS ON THE RANDOM GRAPH

## Author(s): Berestycki, Nathanael; Lubetzky, Eyal; Peres, Yuval; Sly, Allan M.

To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1bm4n
DC FieldValueLanguage
dc.contributor.authorBerestycki, Nathanael-
dc.contributor.authorLubetzky, Eyal-
dc.contributor.authorPeres, Yuval-
dc.contributor.authorSly, Allan M.-
dc.date.accessioned2019-04-05T18:40:55Z-
dc.date.available2019-04-05T18:40:55Z-
dc.date.issued2018-01en_US
dc.identifier.citationBerestycki, Nathanael, Lubetzky, Eyal, Peres, Yuval, Sly, Allan. (2018). RANDOM WALKS ON THE RANDOM GRAPH. ANNALS OF PROBABILITY, 46 (456 - 490). doi:10.1214/17-AOP1189en_US
dc.identifier.issn0091-1798-
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr1bm4n-
dc.description.abstractWe study random walks on the giant component of the Erdos-Renyi random graph G(n, p) where p = lambda/n for lambda > 1 fixed. The mixing time from a worst starting point was shown by Fountoulakis and Reed, and independently by Benjamini, Kozma and Wormald, to have order log(2) n. We prove that starting from a uniform vertex (equivalently, from a fixed vertex conditioned to belong to the giant) both accelerates mixing to O(log n) and concentrates it (the cutoff phenomenon occurs): the typical mixing is at (nu d)(-1) log n +/-(log n)(1/2+o(1)), where nu and d are the speed of random walk and dimension of harmonic measure on a Poisson(lambda)-Galton-Watson tree. Analogous results are given for graphs with prescribed degree sequences, where cutoff is shown both for the simple and for the nonbacktracking random walk.en_US
dc.format.extent456 - 490en_US
dc.languageEnglishen_US
dc.language.isoen_USen_US
dc.relation.ispartofANNALS OF PROBABILITYen_US
dc.rightsAuthor's manuscripten_US
dc.titleRANDOM WALKS ON THE RANDOM GRAPHen_US
dc.typeJournal Articleen_US
dc.identifier.doidoi:10.1214/17-AOP1189-
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/journal-articleen_US

Files in This Item:
File Description SizeFormat