On sensitivity of uniform mixing times

DOI10.1214/16-AIHP802MaRDI QIDQ1635969zbMATH OpenFDO

Authors Jonathan Hermon

Publication date 1 June 2018

Published in Annales de l'Institut Henri Poincaré. Probabilités et Statistiques (Search for Journal in Brave)

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

zbMATH Keywords

hitting timesmixing-timesensitivitysensitivity of mixing times

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Abstract: We show that the order of the $L_{infty}$-mixing time of simple random walks on a sequence of uniformly bounded degree graphs of size $n$ may increase by an optimal factor of $Theta(loglogn)$ as a result of a bounded perturbation of the edge weights. This answers a question and a conjecture of Kozma.

Recommendations

• Sensitivity of mixing times
• On sensitivity of mixing times and cutoff
• On the mixing time of a simple random walk on the super critical percolation cluster
• Uniform mixing time for random walk on lamplighter graphs
• Comparing mixing times on sparse random graphs

Cites work

• A characterization of \(L_{2}\) mixing and hypercontractivity via hitting times and maximal inequalities
• Characterization of cutoff for reversible Markov chains
• Evolving sets, mixing and heat kernel bounds
• Explicit expanders with cutoff phenomena
• scientific article; zbMATH DE number 1069282 (Why is no real title available?)
• Instability of the Liouville property for quasi-isometric graphs and manifolds of polynomial volume growth
• Logarithmic Sobolev inequalities for finite Markov chains
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Mixing time bounds via bottleneck sequences
• Mixing time bounds via the spectral profile
• Mixing times are hitting times of large sets
• On sensitivity of mixing times and cutoff
• On the precision of the spectral profile
• On the stability of the behavior of random walks on groups
• Sensitivity of mixing times
• Sensitivity of mixing times in Eulerian digraphs

Cited in

(15)

• On sensitivity of mixing times and cutoff
• Correction to: ``Speeding up Markov chains with deterministic jumps
• Some inequalities for reversible Markov chains and branching random walks via spectral optimization
• Speeding up Markov chains with deterministic jumps
• A comparison principle for random walk on dynamical percolation
• A characterization of \(L_{2}\) mixing and hypercontractivity via hitting times and maximal inequalities
• Entry times distribution for mixing systems
• On the precision of the spectral profile
• Sensitivity of mixing times in Eulerian digraphs
• Uniform mixing time for random walk on lamplighter graphs
• On the Relation between Enhanced Dissipation Timescales and Mixing Rates
• Sensitivity of mixing times of Cayley graphs
• Cutoff for random walk on random graphs with a community structure
• Sensitivity of mixing times
• Mixing time bounds via the spectral profile

This page was built for publication: On sensitivity of uniform mixing times

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