The power of averaging at two consecutive time steps: proof of a mixing conjecture by Aldous and Fill. (English. French summary) Zbl 1382.60095

Summary: Let \((X_{t})_{t=0}^{\infty}\) be an irreducible reversible discrete-time Markov chain on a finite state space \(\Omega\). Denote its transition matrix by \(P\). To avoid periodicity issues (and thus ensuring convergence to equilibrium) one often considers the continuous-time version of the chain \((X_{t}^{\mathrm{c}})_{t\geq 0}\) whose kernel is given by \(H_{t}:=e^{-t}\sum_{k}(tP)^{k}/k!\). Another possibility is to consider the associated averaged chain \((X_{t}^{\mathrm{ave}})_{t=0}^{\infty}\), whose distribution at time \(t\) is obtained by replacing \(P^{t}\) by \(A_{t}:=(P^{t}+P^{t+1})/2\).{
} A sequence of Markov chains is said to exhibit (total-variation) cutoff if the convergence to stationarity in total-variation distance is abrupt. Let \((X_{t}^{(n)})_{t=0}^{\infty}\) be a sequence of irreducible reversible discrete-time Markov chains. In this work we prove that the sequence of associated continuous-time chains exhibits total-variation cutoff around time \(t_{n}\) iff the sequence of the associated averaged chains exhibits total-variation cutoff around time \(t_{n}\). Moreover, we show that the width of the cutoff window for the sequence of associated averaged chains is at most that of the sequence of associated continuous-time chains. In fact, we establish more precise quantitative relations between the mixing-times of the continuous-time and the averaged versions of a reversible Markov chain, which provide an affirmative answer to a problem raised by D. Aldous and J. Fill [Reversible Markov Chains and Random Walks on Graphs. Berkeley: University of California (2002)].


60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
Full Text: DOI arXiv Euclid


[1] D. Aldous and J. Fill.Reversible Markov Chains and Random Walks on Graphs. University of California, Berkeley, 2002. Available athttps://www.stat.berkeley.edu/ aldous/RWG/book.pdf.
[2] N. Alon and J. H. Spencer.The Probabilistic Method. John Wiley & Sons, New York, 2004. · Zbl 1333.05001
[3] R. Basu, J. Hermon and Y. Peres. Characterization of cutoff for reversible Markov chains.Ann. Probab.45(3) (2017) 1448-1487. · Zbl 1374.60129
[4] G.-Y. Chen and L. Saloff-Coste. Comparison of cutoffs between lazy walks and Markovian semigroups.J. Appl. Probab.50(4) (2013) 943-959. · Zbl 1288.60088
[5] S. Griffiths, R. Kang, R. Oliveira and V. Patel. Tight inequalities among set hitting times in Markov chains.Proc. Amer. Math. Soc.142(2014) 3285-3298. · Zbl 1300.60083
[6] C. Le Merdy and Q. Xu. Maximal theorems and square functions for analytic operators on \(L^{p}\)-spaces.J. Lond. Math. Soc.86(2) (2012) 343-365. · Zbl 1264.47036
[7] D. A. Levin, Y. Peres and E. L. Wilmer.Markov Chains and Mixing Times. Amer. Mathematical Society, Providence, 2009. · Zbl 1160.60001
[8] E. Lubetzky and A. Sly. Cutoff phenomena for random walks on random regular graphs.Duke Math. J.153(3) (2010) 475-510. · Zbl 1202.60012
[9] Y. Peres and P. Sousi. Mixing times are hitting times of large sets.J. Theoret. Probab.28(2) (2015) 488-519. · Zbl 1323.60094
[10] E. M. Stein. On the maximal ergodic theorem.Proc. Natl. Acad. Sci. USA47(12) (1961) 1894. · Zbl 0182.47102
[11] D. V. Widder.An Introduction to Transform Theory, Vol. 42. Academic Press, San Diego, 1971. · Zbl 0219.44001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.