An entropic proof of cutoff on Ramanujan graphs

DOI10.1214/20-ECP358zbMath1462.05329arXiv2009.00837MaRDI QIDQ829365

Narutaka Ozawa

Publication date: 5 May 2021

Published in: Electronic Communications in Probability (Search for Journal in Brave)

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

zbMATH Keywords

entropycutoffrandom walkRamanujan graph

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Measures of information, entropy (94A17) Random walks on graphs (05C81)

Related Items (1)

Universality of cutoff for graphs with an added random matching

Cites Work

• Unnamed Item
• Cutoff on all Ramanujan graphs
• Random walks on discrete groups: Boundary and entropy
• Discrete groups, expanding graphs and invariant measures. Appendix by Jonathan D. Rogawski
• Cutoff at the ``entropic time for sparse Markov chains
• Random walks on the random graph
• Cutoff for nonbacktracking random walks on sparse random graphs
• Comparing mixing times on sparse random graphs
• Cutoff for Ramanujan graphs via degree inflation
• A proof of Alon’s second eigenvalue conjecture and related problems

This page was built for publication: An entropic proof of cutoff on Ramanujan graphs