TY - GEN
T1 - Comparing mixing times on sparse random graphs
AU - Ben-Hamou, Anna
AU - Lubetzky, Eyal
AU - Peres, Yuval
N1 - Publisher Copyright:
© Copyright 2018 by SIAM.
PY - 2018
Y1 - 2018
N2 - It is natural to expect that nonbacktracking random walk will mix faster than simple random walks, but so far this has only been proved in regular graphs. To analyze typical irregular graphs, let G be a random graph on n vertices with minimum degree 3 and a degree distribution that has exponential tails. We determine the precise worst-case mixing time for simple random walk on G, and show that, with high probability, it exhibits cutof at time h-1 log n, where h is the asymptotic entropy for simple random walk on a Galton-Watson tree that approximates G locally. (Previously this was only known for typical starting points.) Furthermore, we show this asymptotic mixing time is strictly larger than the mixing time of nonbacktracking walk, via a delicate comparison of entropies on the Galton-Watson tree.
AB - It is natural to expect that nonbacktracking random walk will mix faster than simple random walks, but so far this has only been proved in regular graphs. To analyze typical irregular graphs, let G be a random graph on n vertices with minimum degree 3 and a degree distribution that has exponential tails. We determine the precise worst-case mixing time for simple random walk on G, and show that, with high probability, it exhibits cutof at time h-1 log n, where h is the asymptotic entropy for simple random walk on a Galton-Watson tree that approximates G locally. (Previously this was only known for typical starting points.) Furthermore, we show this asymptotic mixing time is strictly larger than the mixing time of nonbacktracking walk, via a delicate comparison of entropies on the Galton-Watson tree.
UR - http://www.scopus.com/inward/record.url?scp=85045572944&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85045572944&partnerID=8YFLogxK
U2 - 10.1137/1.9781611975031.113
DO - 10.1137/1.9781611975031.113
M3 - Conference contribution
AN - SCOPUS:85045572944
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 1734
EP - 1740
BT - 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018
A2 - Czumaj, Artur
PB - Association for Computing Machinery
T2 - 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018
Y2 - 7 January 2018 through 10 January 2018
ER -