Mixing reversible Markov chains in the max-\(\ell^2\)-distance (Q6634823)

In this paper, the tripe \((\mathcal{X},K,\pi)\) stands for a discrete time finite Markov chain on \(\mathcal{X}\) with irreducible transition matrix \(K\) and stationary distribution \(\pi\). The max-\(\ell^2\)-distance is defined by \N\[\Nd_2(m)=\max_{x\in \mathcal{X}}\|K^m(x,\cdot)/\pi-1\|_2=\max_{x\in \mathcal{X}} \left(\sum_{y\in \mathcal{X}}\left\|\frac{K^m(x,y)}{\pi(y}-1\right\|^2\pi(y)\right)^{1/2}. \N\]\NThe max-\(\ell^2\)-mixing time is defined by \N\[\NT_2(\epsilon)=\min\{m\geq 0|d_2(m)\leq \epsilon\},\quad \forall \epsilon>0.\N\]\NLet \(\mathcal{F}=(\mathcal{X}_n,K_n,\pi_n)_{n=1}^{\infty}\) be a family of finite Markov chains, and \(d_{n,2}\) and \(T_{n,2}\) be the max-\(\ell^2\)-distance and max-\(\ell^2\)-mixing time of \((\mathcal{X}_n,K_n,\pi_n)\). \(\mathcal{F}\) is said to has a max-\(\ell^2\)-cutoff if there is a sequence of positive reals, \((t_n)_{n=1}^{\infty}\) such that \N\[\N\lim_{n\to\infty}d_{n,2}(\lceil ct_n\rceil)=0,\ \forall c>1;\quad \lim_{n\to\infty}d_{n,2}(\lfloor ct_n\rfloor)\to\infty, \quad \forall 0<c<1.\N\]\NThis paper considered the max-\(\ell^2\)-distances of reversible finite Markov chains and studied their mixing times and cutoff phenomena. The theoretical developments generalized the frameworks of \textit{G.-Y. Chen} and \textit{L. Saloff-Coste} [J. Funct. Anal. 258, No. 7, 2246--2315 (2010; Zbl 1192.60088)] and \textit{G.-Y. Chen} et al. [Ann. Appl. Probab. 27, No. 4, 2305--2341 (2017; Zbl 1374.60130)]. Based on the precise spectral information of transition matrices, the author provided tight bounds on the mixing time, criteria on the existence of cutoffs, and formulas computing cutoff times. For an illustration, birth and death chains with constant rates, random walks on hypercubes and clustering chains were introduced and discussed in detail.