On sensitivity of uniform mixing times

DOI10.1214/16-AIHP802zbMATH Open1396.60085arXiv1607.01672MaRDI QIDQ1635969FDOQ1635969

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)

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.

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

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

zbMATH Keywords

sensitivityhitting timesmixing-timesensitivity of mixing times

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (14)

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

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)