A technical report on hitting times, mixing and cutoff.

*(English)*Zbl 1388.60137Summary: Consider a sequence of continuous-time irreducible reversible Markov chains and a sequence of initial distributions, \(\mu_n\). Instead of performing a worst case analysis, one can study the rate of convergence to the stationary distribution starting from these initial distributions. The sequence is said to exhibit (total variation) \(\mu_n\)-cutoff if the convergence to stationarity in total variation distance is abrupt, w.r.t. this sequence of initial distributions.

In this work we give a characterization of \(\mu_n\)-cutoff (and also of total-variation mixing) for an arbitrary sequence of initial distributions \(\mu_n\) (in the above setup). Our characterization is expressed in terms of hitting times of sets which are “worst” (in some sense) w.r.t. \(\mu_n\).

Consider a Markov chain on \(\Omega\) whose stationary distribution is \(\pi\). Let \(t_{\mathrm{H}}(\alpha) :=\max_{x\in\Omega, A\subseteq \Omega:\pi(A)\geqslant\alpha}\mathbb E_x[T_A]\) be the expected hitting time of the set of stationary probability at least \(\alpha\) which is “worst in expectation” (starting from the worst starting state). The connection between \(t_{\mathrm{H}}(\cdot)\) and the mixing time of the chain was previously studied by D. J. Aldous [J. Lond. Math. Soc., II. Ser. 25, 564–576 (1982; Zbl 0489.60077)] and later by L. Lovász and P. Winkler [DIMACS, Ser. Discrete Math. Theor. Comput. Sci. 41, 85–133 (1998; Zbl 0908.60065)], and was recently refined by Y. Peres and P. Sousi [J. Theor. Probab. 28, No. 2, 488–519 (2015; Zbl 1323.60094)] and independently by R. I. Oliveira [Electron. J. Probab. 17, Paper No. 70, 12 p. (2012; Zbl 1251.60059)]. In this work we further refine this connection and show that \(\mu_n\)-cutoff can be characterized in terms of concentration of hitting times (starting from \(\mu_n\)) of sets which are worst in expectation w.r.t. \(\mu_n\). Conversely, we construct a counter-example which demonstrates that in general cutoff (as opposed to cutoff w.r.t. a certain sequence of initial distributions) cannot be characterized in this manner.

Finally, we also prove that there exists an absolute constant \(C\) such that for any Markov chain \(_\varepsilon(t_{\mathrm{H}}(\varepsilon) - t_{\mathrm{H}}(1 -\varepsilon))\leqslant C t_{\mathrm{rel}}|\log \varepsilon|\), for all \(0 < \varepsilon < 1/2\), where \(t_{\mathrm{rel}}\) is the inverse of the spectral gap of the additive symmetrization \(\frac{1}{2}(P + P^\ast)\).

In this work we give a characterization of \(\mu_n\)-cutoff (and also of total-variation mixing) for an arbitrary sequence of initial distributions \(\mu_n\) (in the above setup). Our characterization is expressed in terms of hitting times of sets which are “worst” (in some sense) w.r.t. \(\mu_n\).

Consider a Markov chain on \(\Omega\) whose stationary distribution is \(\pi\). Let \(t_{\mathrm{H}}(\alpha) :=\max_{x\in\Omega, A\subseteq \Omega:\pi(A)\geqslant\alpha}\mathbb E_x[T_A]\) be the expected hitting time of the set of stationary probability at least \(\alpha\) which is “worst in expectation” (starting from the worst starting state). The connection between \(t_{\mathrm{H}}(\cdot)\) and the mixing time of the chain was previously studied by D. J. Aldous [J. Lond. Math. Soc., II. Ser. 25, 564–576 (1982; Zbl 0489.60077)] and later by L. Lovász and P. Winkler [DIMACS, Ser. Discrete Math. Theor. Comput. Sci. 41, 85–133 (1998; Zbl 0908.60065)], and was recently refined by Y. Peres and P. Sousi [J. Theor. Probab. 28, No. 2, 488–519 (2015; Zbl 1323.60094)] and independently by R. I. Oliveira [Electron. J. Probab. 17, Paper No. 70, 12 p. (2012; Zbl 1251.60059)]. In this work we further refine this connection and show that \(\mu_n\)-cutoff can be characterized in terms of concentration of hitting times (starting from \(\mu_n\)) of sets which are worst in expectation w.r.t. \(\mu_n\). Conversely, we construct a counter-example which demonstrates that in general cutoff (as opposed to cutoff w.r.t. a certain sequence of initial distributions) cannot be characterized in this manner.

Finally, we also prove that there exists an absolute constant \(C\) such that for any Markov chain \(_\varepsilon(t_{\mathrm{H}}(\varepsilon) - t_{\mathrm{H}}(1 -\varepsilon))\leqslant C t_{\mathrm{rel}}|\log \varepsilon|\), for all \(0 < \varepsilon < 1/2\), where \(t_{\mathrm{rel}}\) is the inverse of the spectral gap of the additive symmetrization \(\frac{1}{2}(P + P^\ast)\).

##### MSC:

60J27 | Continuous-time Markov processes on discrete state spaces |

60J10 | Markov chains (discrete-time Markov processes on discrete state spaces) |

##### Keywords:

mixing-time; hitting times; cutoff; finite reversible Markov chains; maximal inequality; counter-example
PDF
BibTeX
XML
Cite

\textit{J. Hermon}, ALEA, Lat. Am. J. Probab. Math. Stat. 15, No. 1, 101--120 (2018; Zbl 1388.60137)

**OpenURL**

##### References:

[1] | D. Aldous and J. Fill. Reversible Markov chains and random walks on graphs(2002). Unfinished manuscript |

[2] | D. J. Aldous. Some inequalities for reversible Markov chains. J. London Math. Soc.(2) 25 (3), 564-576 (1982) · Zbl 0489.60077 |

[3] | R. Basu, J. Hermon and Y. Peres. Characterization of cutoff for reversible Markovchains. Ann. Probab. 45 (3), 1448-1487 (2017) · Zbl 1374.60129 |

[4] | G.-Y. Chen. The cutoff phenomenon for finite Markov chains. ProQuest LLC, AnnArbor, MI (2006). ISBN 978-0542-71243-2. Thesis (Ph.D.)-Cornell University |

[5] | G.-Y. Chen and L. Saloff-Coste. Comparison of cutoffs between lazy walks andMarkovian semigroups. J. Appl. Probab. 50 (4), 943-959 (2013) · Zbl 1288.60088 |

[6] | S. Goel, R. Montenegro and P. Tetali. Mixing time bounds via the spectral profile.Electron. J. Probab. 11, no. 1, 1-26 (2006) · Zbl 1109.60061 |

[7] | S. Griffiths, R. J. Kang, R. I. Oliveira and V. Patel. Tight inequalities amongset hitting times in Markov chains. Proc. Amer. Math. Soc. 142 (9), 3285-3298(2014) · Zbl 1300.60083 |

[8] | D. A. Levin, Y. Peres and E. L. Wilmer. Markov chains and mixing times. Amer-ican Mathematical Society, Providence, RI (2017). ISBN 978-1-4704-2962-1 · Zbl 1390.60001 |

[9] | L. Lov´asz and P. Winkler. Mixing times. In Microsurveys in discrete probability(Princeton, NJ, 1997), volume 41 of DIMACS Ser. Discrete Math. Theoret. Com-put. Sci., pages 85-133. Amer. Math. Soc., Providence, RI (1998) |

[10] | R. Montenegro and P. Tetali. Mathematical aspects of mixing times in Markovchains. Found. Trends Theor. Comput. Sci. 1 (3), x+121 (2006) |

[11] | 120J. Hermon |

[12] | R. I. Oliveira. Mixing and hitting times for finite Markov chains. Electron. J.Probab. 17, no. 70, 12 (2012) · Zbl 1251.60059 |

[13] | Y. Peres and P. Sousi. Mixing times are hitting times of large sets. J. Theoret.Probab. 28 (2), 488-519 (2015) · Zbl 1323.60094 |

[14] | N. Starr. Operator limit theorems. Trans. Amer. Math. Soc. 121, 90-115 (1966) · Zbl 0147.15601 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.