Repository logo
 

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

Accepted version
Peer-reviewed

Change log

Authors

Peres, Yuval 

Abstract

Let (Xt)t=0 be an irreducible reversible discrete time Markov chain on a finite state space $\Omega .DenoteitstransitionmatrixbyP.Toavoidperiodicityissues(andthusensuringconvergencetoequilibrium)oneoftenconsidersthecontinuoustimeversionofthechain(X_t^{\mathrm{c}}){t \ge 0} $ whose kernel is given by $H_t:=e^{-t}\sum_k (tP)^k/k! .Anotherpossibilityistoconsidertheassociatedaveragedchain(X_t^{\mathrm{ave}}){t = 0}^{\infty}$, whose distribution at time t is obtained by replacing P by At:=(Pt+Pt+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 (Xt(n))t=0 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 tn iff the sequence of the associated averaged chains exhibits total-variation cutoff around time tn. 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.

Description

Keywords

Mixing-time, Finite reversible Markov chains, Averaged chain, Maximal inequalities, Cutoff

Journal Title

ANNALES DE L INSTITUT HENRI POINCARE-PROBABILITES ET STATISTIQUES

Conference Name

Journal ISSN

0246-0203

Volume Title

53

Publisher

Institute of Mathematical Statistics
Sponsorship
None