Random walks on the random graph

Nathanaël Berestycki ^[1] ; Eyal Lubetzky ^[2] ; Yuval Peres ^[3] ; Allan Sly ^[4]
1. [1] University of Cambridge
  
  University of Cambridge
  
  Cambridge District, Reino Unido
2. [2] New York University
  
  New York University
  
  Estados Unidos
3. [3] One Microsoft Way (USA)
4. [4] University of California (USA)
Mostrar afiliaciones +
Localización: Annals of probability: An official journal of the Institute of Mathematical Statistics, ISSN 0091-1798, Vol. 46, Nº. 1, 2018, págs. 456-490
Idioma: inglés
DOI: 10.1214/17-AOP1189
Enlaces
- Texto completo
Resumen
- We study random walks on the giant component of the Erdős–Rényi random graph G(n,p)G(n,p) where p=λ/np=λ/n for λ>1λ>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 log2nlog2⁡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(logn)O(log⁡n) and concentrates it (the cutoff phenomenon occurs): the typical mixing is at (νd)−1logn±(logn)1/2+o(1)(νd)−1log⁡n±(log⁡n)1/2+o(1), where νν and dd are the speed of random walk and dimension of harmonic measure on a Poisson(λ)Poisson⁡(λ)-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.