CUTOFF AT THE ENTROPIC TIME FOR RANDOM WALKS ON COVERED EXPANDER GRAPHS

DOI10.1017/S1474748020000663zbMath1496.05177arXiv1812.06769MaRDI QIDQ5102213

Hubert Lacoin, Charles Bordenave

Publication date: 6 September 2022

Published in: Journal of the Institute of Mathematics of Jussieu (Search for Journal in Brave)

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

zbMATH Keywords

spectral gapmixing timeexpander graphsRamanujan graphentropic time

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Probability measures on groups or semigroups, Fourier transforms, factorization (60B15) Random walks on graphs (05C81) Expander graphs (05C48)

Related Items

Cutoff for permuted Markov chains ⋮ On Sarnak’s Density Conjecture and Its Applications ⋮ \(L^p\)-expander graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Cutoff on all Ramanujan graphs
• Free probability and random matrices
• Random graph coverings. I: General theory and graph connectivity
• Cutoff phenomena for random walks on random regular graphs
• Local limits and harmonic functions for nonisotropic random walks on free groups
• Random walks on discrete groups: Boundary and entropy
• Eigenvalues and expanders
• An example of a non nuclear C*-algebra, which has the metric approximation property
• Relative expanders or weakly relatively Ramanujan graphs.
• Brown's spectral distribution measure for \(R\)-diagonal elements in finite von Neumann algebras
• Random walks on the random graph
• Weighted expanders and the anisotropic Alon-Boppana theorem
• Characterization of cutoff for reversible Markov chains
• Cutoff for nonbacktracking random walks on sparse random graphs
• Cutoff for random lifts of weighted graphs
• Eigenvalues of random lifts and polynomials of random permutation matrices
• Cutoff for Ramanujan graphs via degree inflation
• Random walk on sparse random digraphs
• Asymptotic entropy and Green speed for random walks on countable groups
• A strengthening and a multipartite generalization of the Alon-Boppana-Serre theorem
• Full Banach Mean Values on Countable groups.
• Symmetric Random Walks on Groups
• A new proof of Friedman's second eigenvalue theorem and its extension to random lifts
• NON-BACKTRACKING RANDOM WALKS MIX FASTER
• Random matrices, nonbacktracking walks, and orthogonal polynomials
• Shuffling Cards and Stopping Times
• Generating a random permutation with random transpositions
• Computing Norms in Group C ∗ -Algebras
• Harmonic analysis for anisotropic random walks on homogeneous trees
• A technical report on hitting times, mixing and cutoff
• Introduction to the Rapid Decay property
• The cutoff phenomenon in finite Markov chains.
• Random Lifts of Graphs: Edge Expansion
• On the computation of spectra in free probability

This page was built for publication: CUTOFF AT THE ENTROPIC TIME FOR RANDOM WALKS ON COVERED EXPANDER GRAPHS