Sensitivity of mixing times

DOI10.1214/ECP.V18-2765zbMATH Open1307.60051arXiv1304.0244MaRDI QIDQ743063FDOQ743063

Authors: Jian Ding, Yuval Peres 

Publication date: 22 September 2014

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

Abstract: In this note, we demonstrate an instance of bounded-degree graphs of size $n$, for which the total variation mixing time for the random walk is decreased by a factor of $logn/loglogn$ if we multiply the edge-conductances by bounded factors in a certain way.

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

Recommendations

• On sensitivity of uniform mixing times
• On sensitivity of mixing times and cutoff
• Faster mixing and small bottlenecks
• Sensitivity of mixing times in Eulerian digraphs
• Comparing mixing times on sparse random graphs

zbMATH Keywords

sensitivityrandom walkmixing timebounded-degree graph

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Sums of independent random variables; random walks (60G50) Random walks on graphs (05C81)

Cited In (14)

• Smoothed Analysis on Connected Graphs
• Correction to: ``Speeding up Markov chains with deterministic jumps
• No cutoff in spherically symmetric trees
• On sensitivity of mixing times and cutoff
• Mixing time bounds via bottleneck sequences
• Sensitivity of mixing times of Cayley graphs
• A characterization of \(L_{2}\) mixing and hypercontractivity via hitting times and maximal inequalities
• On sensitivity of uniform mixing times
• Large scale stochastic dynamics. Abstracts from the workshop held September 11--17, 2022
• Mixing times are hitting times of large sets
• A comparison principle for random walk on dynamical percolation
• Speeding up Markov chains with deterministic jumps
• Mixing times for the interchange process
• Some inequalities for reversible Markov chains and branching random walks via spectral optimization

This page was built for publication: Sensitivity of mixing times

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