Fetching the paper…

Reading the bibliography…

Mixing times are hitting times of large sets · Around

2011

Mixing times are hitting times of large sets

Peres, Yuval, Sousi, Perla

Original
PDF
Post on X

Understand

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.

Built on

Stopping times for recurrent Markov processes
J. R. Baxter and R. V. Chacon · 1976
Earlier work this paper cites.
Some inequalities for reversible Markov chains
David J. Aldous · 1982
Earlier work this paper cites.
Efficient stopping rules for markov chains
László Lovász and Peter Winkler · 1995
Earlier work this paper cites.

Similar

Mixing times
László Lovász and Peter Winkler · 1998
Cited alongside, same era.
Markov chains and mixing times
David A. Levin, Yuval Peres, and Elizabeth L. Wilmer · 2009
Cited alongside, same era.
Tight inequalities among set hitting times in Markov chains, 2012
S. Griffiths, R. J. Kang, R. Imbuzeiro Oliveira, and V. Patel · 2012
Cited alongside, same era.
Reversible Markov Chains and Random Walks on Graphs
David Aldous and J. Fill
Cited in the paper.

Then

Mixing and hitting times for finite Markov chains
Roberto Imbuzeiro Oliveira · 2012
Closest in time.
Sensitivity of mixing times, 2013
Original
J. Ding and Y. Peres · 2013
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…