Mixing times are hitting times of large sets
From MaRDI portal
Publication:495704
DOI10.1007/S10959-013-0497-9zbMATH Open1323.60094arXiv1108.0133OpenAlexW1989183425MaRDI QIDQ495704FDOQ495704
Authors: Yuval Peres, Perla Sousi 
Publication date: 15 September 2015
Published in: Journal of Theoretical Probability (Search for Journal in Brave)
Abstract: We consider irreducible reversible discrete time Markov chains on a finite state space. Mixing times and hitting times are fundamental parameters of the chain. We relate them by showing that the mixing time of the lazy chain is equivalent to the maximum over initial states x and large sets A of the hitting time of A starting from x. We also prove that the first time when averaging over two consecutive time steps is close to stationarity is equivalent to the mixing time of the lazy version of the chain.
Full work available at URL: https://arxiv.org/abs/1108.0133
Recommendations
Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Stopping times; optimal stopping problems; gambling theory (60G40)
Cites Work
- Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
- Title not available (Why is that?)
- Some Inequalities for Reversible Markov Chains
- Title not available (Why is that?)
- Mixing and hitting times for finite Markov chains
- Stopping times for recurrent Markov processes
- Tight inequalities among set hitting times in Markov chains
- Sensitivity of mixing times
Cited In (39)
- Leader election in well-connected graphs
- Mixing times for uniformly ergodic Markov chains
- Hitting, mixing and tunneling asymptotics of Metropolis-Hastings reversiblizations in the low-temperature regime
- Metastable Markov chains: from the convergence of the trace to the convergence of the finite-dimensional distributions
- Title not available (Why is that?)
- Mixing of the square plaquette model on a critical length scale
- Time scale separation and dynamic heterogeneity in the low temperature East model
- Hitting time and mixing time bounds of Stein's factors
- Mixing and average mixing times for general Markov processes
- No cutoff in spherically symmetric trees
- Tight inequalities among set hitting times in Markov chains
- On sensitivity of mixing times and cutoff
- The power of averaging at two consecutive time steps: proof of a mixing conjecture by Aldous and Fill
- Mixing time bounds via bottleneck sequences
- The cutoff phenomenon for random birth and death chains
- Excessive symmetry can preclude cutoff
- Sensitivity of mixing times of Cayley graphs
- Mixing and hitting times for finite Markov chains
- On Coalescence Time in Graphs: When Is Coalescing as Fast as Meeting?
- Hitting time in regular sets and logarithm law for rapidly mixing dynamical systems
- A characterization of \(L_{2}\) mixing and hypercontractivity via hitting times and maximal inequalities
- Cutoff phenomenon for nearest Lamperti's random walk
- On sensitivity of uniform mixing times
- Multiple random walks on graphs: mixing few to cover many
- The distribution of mixing times in Markov chains
- The mixing time of the giant component of a random graph
- Bounds on lifting continuous-state Markov chains to speed up mixing
- A spectral characterization for concentration of the cover time
- Mixing time for the repeated balls into bins dynamics
- Mixing and hitting times for Gibbs samplers and other non-Feller processes
- Mixing of the upper triangular matrix walk
- Elementary bounds on mixing times for decomposable Markov chains
- Sensitivity of Mixing Times in Eulerian Digraphs
- Mixing times for a constrained Ising process on the two-dimensional torus at low density
- A technical report on hitting times, mixing and cutoff
- Some inequalities for reversible Markov chains and branching random walks via spectral optimization
- Cutoff for the square plaquette model on a critical length scale
- Cutoff on trees is rare
- A threshold for cutoff in two-community random graphs
This page was built for publication: Mixing times are hitting times of large sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q495704)
