Cutoff at the ``entropic time for sparse Markov chains

DOI10.1007/s00440-018-0834-0zbMath1480.60202arXiv1611.01079OpenAlexW2963720082MaRDI QIDQ1729696

Justin Salez, Charles Bordenave, Pietro Caputo

Publication date: 28 February 2019

Published in: Probability Theory and Related Fields (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Random matrices (probabilistic aspects) (60B20) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Random walks on graphs (05C81)

Related Items

Universality of cutoff for graphs with an added random matching, An entropic proof of cutoff on Ramanujan graphs, Mixing time of PageRank surfers on sparse random digraphs, The cutoff phenomenon for the stochastic heat and wave equation subject to small Lévy noise, Large scale stochastic dynamics. Abstracts from the workshop held September 11--17, 2022, On the meeting of random walks on random DFA, Cutoff for permuted Markov chains, Rankings in directed configuration models with heavy tailed in-degrees, Spectrum of large random Markov chains: Heavy-tailed weights on the oriented complete graph, Stationary distribution and cover time of sparse directed configuration models, The cutoff phenomenon in total variation for nonlinear Langevin systems with small layered stable noise, Mixing time trichotomy in regenerating dynamic digraphs, Linking the mixing times of random walks on static and dynamic random graphs, Mixing time of fractional random walk on finite fields

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Cutoff on all Ramanujan graphs
• Diameter and stationary distribution of random \(r\)-out digraphs
• Total variation cutoff in birth-and-death chains
• A survey of results on random random walks on finite groups
• Cutoff phenomena for random walks on random regular graphs
• Separation cut-offs for birth and death chains
• On tail probabilities for martingales
• The two-parameter Poisson-Dirichlet distribution derived from a stable subordinator
• Random random walks on \(\mathbb{Z}_2^d\)
• Random walks on the random graph
• Characterization of cutoff for reversible Markov chains
• Cutoff for nonbacktracking random walks on sparse random graphs
• Random walk on sparse random digraphs
• Random doubly stochastic tridiagonal matrices
• The cutoff phenomenon for random birth and death chains
• Shuffling Cards and Stopping Times
• Generating a random permutation with random transpositions
• The cutoff phenomenon in finite Markov chains.
• Spectrum of large random Markov chains: Heavy-tailed weights on the oriented complete graph