Skip to main content

RANDOM WALKS ON THE RANDOM GRAPH

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

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1bm4n
Abstract: We 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.
Publication Date: Jan-2018
Citation: Berestycki, Nathanael, Lubetzky, Eyal, Peres, Yuval, Sly, Allan. (2018). RANDOM WALKS ON THE RANDOM GRAPH. ANNALS OF PROBABILITY, 46 (456 - 490). doi:10.1214/17-AOP1189
DOI: doi:10.1214/17-AOP1189
ISSN: 0091-1798
Pages: 456 - 490
Language: English
Type of Material: Journal Article
Journal/Proceeding Title: ANNALS OF PROBABILITY
Version: Author's manuscript



Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.