The max-`ℓ^2` mixing of reversible Markov chains

Guan-Yu Chen

Department of Applied Mathematics

National Chiao Tung University

gychen@math.nctu.edu.tw

    The `ℓ^2`-distance is one frequently used measurement to analyze the convergence of Markov chains to their stationarity. For reversible Markov chains, their `ℓ^2`-distances can be formulated by the spectral information of their transition matrices. The corresponding mixing time and cutoff phenomenon for reversible Markov chains were first systemically studied by C. and Saloff-Coste in [3]. Later in [1], C., Hsu and Sheu revealed more intrinsic mechanisms of `ℓ^2`-cutoffs and polished the cutoff criterion of C. and Saloff-Coste. Such a refinement makes some further theoretical analyses feasible including the comparison of `ℓ^2`-cutoffs between discrete time chains and continuous time chains.
The max-`ℓ^2` distance was first considered by C. and Saloff-Coste in [2]. An equivalent condition for the max-`ℓ^2` cutoff was then built on the product of the max-`ℓ^2` mixing time and the spectral gap of the transition matrix. Based on the theoretical work in [1], we derive another proof for the max-`ℓ^2` cutoff criterion in [2] and provide a formula of its cutoff time using the spectral information.

Keyword: Markov chains, reversibility, `ℓ^2`-distance