Random walks on the random graph

DOI10.1214/17-AOP1189MaRDI QIDQ1747756zbMATH OpenFDO

Authors Nathanaël Berestycki, Eyal Lubetzky, Yuval Peres, Allan Sly

Publication date 27 April 2018

Published in The Annals of Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1504.01999

Random graphs (graph-theoretic aspects) (05C80) Random walks on graphs (05C81) Convergence of probability measures (60B10) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Abstract: We study random walks on the giant component of the ErdH{o}s-R'enyi random graph

c a l G (n, p)

where

p = l a m b d a / n

for

l a m b d a > 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

l o g^{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 (l o g n)

and concentrates it (the cutoff phenomenon occurs): the typical mixing is at

, where

u

and

are the speed of random walk and dimension of harmonic measure on a

m P o i s s o n (l a m b d a)

-Galton-Watson tree. Analogous results are given for graphs with prescribed degree sequences, where cutoff is shown both for the simple and for the non-backtracking random walk.

Review text

This paper studies the mixing time of simple and non-backtracking random walks on Erdős-Renyi random graphs and random graphs with given degree sequences. Let \(C\) be the giant component of the Erdős-Renyi graph \(G(n,p)\) with \(p=\lambda/n\) and \(\lambda>1\) fixed. Let \(v\) and \(d\) be the speed of a random walk and the dimension of the harmonic measure on a Poisson(\(\lambda\))-Galton-Watson tree, respectively. For any \(\varepsilon\in(0,1)\), the random walk from a uniformly chosen vertex \(w\in C\) satisfies \(|t_{\mathrm{MIX}}(\varepsilon)-(vd)^{-1}\ln n|\leq (\ln n)^{0.5+o(1)}\) with high probability. Moreover, let \(G\) be a random graph on a degree sequence \((d_1,\dots,d_n)\) with \(p_k=\frac1n|\{i:d_i=k\}|\). Define \(Z\) by \(P(Z=k-1)\propto kp_k\). Let \(t^*=(vd)^{-1}\ln n\), where \(v\) and \(d\) are the speed of random walk and dimension of harmonic measure on a Galton-Watson tree with offspring distribution \(Z\). Set \(w_n=\sqrt{\ln n}\) and suppose that for some \(K\) and \(\delta>0\), \(EZ<K\), \(2\leq Z\leq \Delta=\exp((\ln n)^{0.5-\delta})\). For any \(\varepsilon>0\), there exists some \(\gamma>0\) such that if \(n\) is large enough with high probability, \(d_{TV}(t^*-\gamma w_n)>1-\varepsilon\), whereas \(d_{TV}(t^*+\gamma w_n)<\varepsilon\).

Recommendations

Cites work

Cited in

(79)

This page was built for publication: Random walks on the random graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1747756)