Mixing reversible Markov chains in the max-\(\ell^2\)-distance
type: Item
instance of: scholarly article
title: Mixing reversible Markov chains in the max-\(\ell^2\)-distance
author: Guan-Yu Chen
published in: ALEA. Latin American Journal of Probability and Mathematical Statistics
publication date: 2024-11-08T00:00:00Z
review text: 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.
reviewed by: Ze-Chun Hu
Mathematics Subject Classification ID: 60J10
Mathematics Subject Classification ID: 60J27
zbMATH DE Number: 7940626
zbMATH Keywords: Markov chain
zbMATH Keywords: reversibility
zbMATH Keywords: cutoff
MaRDI profile type: Publication
cites work: Bounds for left and right window cutoffs
cites work: Characterization of cutoff for reversible Markov chains
cites work: Cutoff at the ``entropic time'' for sparse Markov chains
cites work: The \(L^{2}\)-cutoffs for reversible Markov chains
cites work: Cutoffs for product chains
cites work: The cutoff phenomenon for ergodic Markov processes
cites work: The \(L^{2}\)-cutoff for reversible Markov processes
cites work: Comparison of Cutoffs Between Lazy Walks and Markovian Semigroups
cites work: Computing cutoff times of birth and death chains
cites work: Q3138330
cites work: What do we know about the Metropolis algorithm?
cites work: Separation cut-offs for birth and death chains
cites work: Generating a random permutation with random transpositions
cites work: Total variation cutoff in birth-and-death chains
cites work: A characterization of \(L_{2}\) mixing and hypercontractivity via hitting times and maximal inequalities
cites work: On sensitivity of mixing times and cutoff
cites work: Equation of State Calculations by Fast Computing Machines
cites work: Q4358811
DOI: 10.30757/ALEA.V21-65
description: scientific article; zbMATH DE number 7940626