Mixing reversible Markov chains in the max-^2-distance
Mixing reversible Markov chains in the max-\(\ell^2\)-distance
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.
- The \(L^{2}\)-cutoffs for reversible Markov chains
- A characterization of \(L_{2}\) mixing and hypercontractivity via hitting times and maximal inequalities
- The \(L^{2}\)-cutoff for reversible Markov processes
- A technical report on hitting times, mixing and cutoff
- Mixing and hitting times for finite Markov chains
- A characterization of \(L_{2}\) mixing and hypercontractivity via hitting times and maximal inequalities
- Bounds for left and right window cutoffs
- Characterization of cutoff for reversible Markov chains
- Comparison of cutoffs between lazy walks and Markovian semigroups
- Computing cutoff times of birth and death chains
- Cutoff at the ``entropic time for sparse Markov chains
- Cutoffs for product chains
- Equation of state calculations by fast computing machines
- Generating a random permutation with random transpositions
- scientific article; zbMATH DE number 431548 (Why is no real title available?)
- scientific article; zbMATH DE number 1069282 (Why is no real title available?)
- On sensitivity of mixing times and cutoff
- Separation cut-offs for birth and death chains
- The \(L^{2}\)-cutoff for reversible Markov processes
- The \(L^{2}\)-cutoffs for reversible Markov chains
- The cutoff phenomenon for ergodic Markov processes
- Total variation cutoff in birth-and-death chains
- What do we know about the Metropolis algorithm?
This page was built for publication: Mixing reversible Markov chains in the max-\(\ell^2\)-distance
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6634823)
