The cutoff phenomenon for ergodic Markov processes

By Guan-Yu Chen, L. Saloff‐Coste. 2008

102 citations recorded by the source corpus.

We consider the cutoff phenomenon in the context of families of ergodic Markov transition functions. This includes classical examples such as families of ergodic finite Markov chains and Brownian motion on families of compact Riemannian manifolds. We give criteria for the existence of a cutoff when convergence is measured in $L^p$-norm, $1 < p < \infty$. This allows us to prove the existence of a cutoff in cases where the cutoff time is not explicitly known. In the reversible case, for $1 < p\le \infty$, we show that a necessary and sufficient condition for the existence of a max-$L^p$ cutoff is that the product of the spectral gap by the max-$L^p$ mixing time tends to infinity. This type of condition was suggested by Yuval Peres. Illustrative examples are discussed.

Subfields: Mathematical Physics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/94229767c6cdb207c2c1085708edb1d99cac2b4e

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Mathematical Physics

In Statistics and Probability

Citations in the corpus

Cutoff on all Ramanujan graphs (2015, background): “(On the notable exception of p = 1, it is said in [10] that there “the question is more subtle and no good general answer is known.”
Random walk on sparse random digraphs (2015, unknown): “We refer the reader to [10,20,38] for more details.”
Markov Chains and Mixing Times: Second Edition (2017, background): “Is it true that there is cutoff in separation distance if and only if there is cutoff in total variation distance? That this is true for birth-and-death chains follows from combining results in Ding, Lubetzky, and Peres (2010a) and Diaconis and Saloff-Coste (2006). Update: For general reversible cha”
Cutoff phenomena for random walks on random regular graphs (2008, background): “Let (Xt) be an aperiodic irreducible Markov chain on a finite state space Ω with transition kernel P (x, y) and stationary distribution π.”
Total variation cutoff in birth-and-death chains (2008, background): “Diaconis) have constructed relevant examples (see also [5],[6] and [21]).”