A technical report on hitting times, mixing and cutoff

21 Mar 2018

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 \subset \Omega :\,\pi(A) \geq \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 Aldous and later by Lov\'asz and Winkler, and was recently refined by Peres and Sousi and independently by Oliveira. 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 $\epsilon( t_{\h}(\epsilon)-t_{\h}(1-\epsilon)) \leq C\rel |\log \epsilon|$, for all $0< \epsilon < 1/2$, where $\rel$ is the inverse of the spectral gap of the additive symmetrization $\half(P+P^*)$.