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.
Recommendations
Cites work
- scientific article; zbMATH DE number 1195779 (Why is no real title available?)
- scientific article; zbMATH DE number 1263183 (Why is no real title available?)
- Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
- Mixing and hitting times for finite Markov chains
- Sensitivity of mixing times
- Some Inequalities for Reversible Markov Chains
- Stopping times for recurrent Markov processes
- Tight inequalities among set hitting times in Markov chains
Cited in
(42)- On Coalescence Time in Graphs: When Is Coalescing as Fast as Meeting?
- Bounds on lifting continuous-state Markov chains to speed up mixing
- Metastable Markov chains: from the convergence of the trace to the convergence of the finite-dimensional distributions
- The distribution of mixing times in Markov chains
- Mixing time for the repeated balls into bins dynamics
- Hitting time in regular sets and logarithm law for rapidly mixing dynamical systems
- The power of averaging at two consecutive time steps: proof of a mixing conjecture by Aldous and Fill
- Mixing times for uniformly ergodic Markov chains
- Mixing times and moving targets
- Mixing and average mixing times for general Markov processes
- Excessive symmetry can preclude cutoff
- Cutoff on trees is rare
- The cutoff phenomenon for random birth and death chains
- Hitting time and mixing time bounds of Stein's factors
- A characterization of \(L_{2}\) mixing and hypercontractivity via hitting times and maximal inequalities
- Cutoff phenomenon for nearest Lamperti's random walk
- No cutoff in spherically symmetric trees
- A spectral characterization for concentration of the cover time
- Multiple random walks on graphs: mixing few to cover many
- Mixing of the upper triangular matrix walk
- Tight inequalities among set hitting times in Markov chains
- scientific article; zbMATH DE number 7650104 (Why is no real title available?)
- Leader election in well-connected graphs
- Elementary bounds on mixing times for decomposable Markov chains
- On sensitivity of uniform mixing times
- Mixing time bounds via bottleneck sequences
- Mixing and hitting times for Gibbs samplers and other non-Feller processes
- Mixing times for a constrained Ising process on the two-dimensional torus at low density
- Cutoff for the square plaquette model on a critical length scale
- Sensitivity of mixing times of Cayley graphs
- Mixing of the square plaquette model on a critical length scale
- A technical report on hitting times, mixing and cutoff
- Mixing times and hitting times for general Markov processes
- Intersection and mixing times for reversible chains
- Time scale separation and dynamic heterogeneity in the low temperature East model
- On sensitivity of mixing times and cutoff
- Some inequalities for reversible Markov chains and branching random walks via spectral optimization
- Sensitivity of mixing times in Eulerian digraphs
- A threshold for cutoff in two-community random graphs
- The mixing time of the giant component of a random graph
- Mixing and hitting times for finite Markov chains
- Hitting, mixing and tunneling asymptotics of Metropolis-Hastings reversiblizations in the low-temperature regime
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)
