Many Markov chains exhibit a sharp cutoff in convergence to stationarity. In terms of total variation distance, the distance stays close to $1$ and then rapidly drops to $0$ at a certain time.

Every definition I have seen for the cutoff phenomenon involves sequences of Markov chains. For example, from Markov Chains and Mixing Times (by Levin, Peres, and Wilmer):

Suppose for a sequence of Markov Chains indexed by $n = 1, 2, \cdots$, the mixing time for the $n$-th chain is denoted by $t_{mix}^{n}(\epsilon)$. The sequence of chains has a $\textbf{cutoff}$ if for all $\epsilon > 0$ , $$\lim_{n\to\infty} \displaystyle\frac{t_{mix}^{n}(\epsilon)}{t_{mix}^{n}(1 - \epsilon)} = 1$$

I am struggling to understand this definition. Can someone please provide some insight into where it comes from? The cutoff phenomenon refers to what happens over iterations of a fixed chain, so what is the sequence of chains supposed to represent here? In all mixing time results from that book, $n$ refers to the number of steps of a given chain, but here each $n$ refers to an entirely separate chain.

  • $\begingroup$ It often happens that $n$ measures the size of the $n$th chain, for example the $n$th chain could be defined on $\{1,2,\ldots,n\}$, and that the $(n+1)$th Markov chain corresponds to a kind of extension of the $n$th Markov chain. Did you look at the **examples** given by Levin et al.? In any case, indeed $n$ does not refer to the time here... $\endgroup$ – Did Apr 12 '17 at 13:53
  • $\begingroup$ I understand that $n$ often refers to the size of the chain - the motivating example they use is the top-to-random shuffle and here $n$ refers to the size of the deck. I did look at some examples but they are pretty computation-heavy and didn't help clarify the definition for me. I still do not understand why, to explain a phenomenon that occurs over many iterations of a fixed Markov chain, we would take a limit over a sequence of different Markov chains $\endgroup$ – pwerth Apr 12 '17 at 14:00
  • $\begingroup$ You might want to start with Figure 8.5 on page 111: draw on the same plot the graph of the distance $d_n(t)$ in total variation between the chain of size $n$ at time $t$ and its stationary distribution, for every $n$, the time $t$ being rescaled by $\tau_n$ defined by $d_n(\tau_n)=\frac12$, say. Then the cut-off corresponds to the case when, for large $n$, these graphs go down from nearly $1$ to nearly $0$ more and more "abruptly", that is, in a vanishingly small time interval around $t=\tau_n$. Thus, when $n$ is very large, $d_n(.99\cdot\tau_n)\approx1$ and $d_n(1.01\cdot\tau_n)\approx0$. $\endgroup$ – Did Apr 12 '17 at 14:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.