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

##### Publication Date

2017-11##### Journal Title

ANNALES DE L INSTITUT HENRI POINCARE-PROBABILITES ET STATISTIQUES

##### ISSN

0246-0203

##### Publisher

Institute of Mathematical Statistics

##### Volume

53

##### Issue

4

##### Pages

2030-2042

##### Type

Article

##### This Version

AM

##### Metadata

Show full item record##### Citation

Hermon, J., & Peres, Y. (2017). The power of averaging at two consecutive time steps: Proof of a mixing conjecture by Aldous and Fill. ANNALES DE L INSTITUT HENRI POINCARE-PROBABILITES ET STATISTIQUES, 53 (4), 2030-2042. https://doi.org/10.1214/16-AIHP782

##### 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.

##### Keywords

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

##### Sponsorship

None

##### Identifiers

External DOI: https://doi.org/10.1214/16-AIHP782

This record's URL: https://www.repository.cam.ac.uk/handle/1810/274075

##### Rights

Licence:

http://www.rioxx.net/licenses/all-rights-reserved

##### Statistics

**Total file downloads**(since January 2020). For more information on metrics see the IRUS guide.