The power of averaging at two consecutive time steps: Proof of a mixing conjecture by Aldous and Fill

Abstract

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\ge 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$ 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 Aldous and Fill.

References in corpus (2)

• Characterization of cutoff for reversible Markov chains
• Tight inequalities among set hitting times in Markov chains

Cited by in corpus (2)

• Characterization of cutoff for reversible Markov chains
• Sensitivity of mixing times of Cayley graphs