Comparing limit profiles of reversible Markov chains
type: Item
instance of: scholarly article
title: Comparing limit profiles of reversible Markov chains
author: Evita Nestoridi
published in: Electronic Journal of Probability
publication date: 2024-05-29T00:00:00Z
review text: The article introduces a technique for comparing the limit profile of two Markov chains under certain conditions. More precisely, let \(X\) and \(X'\) be an ergodic Markov chain on a finite state space \(\Omega\), with implicit parameter \(n\), with the same equilibrium distribution \(\pi\). Assume that the transition matrices corresponding to \(X\) and \(X'\) commute. Let \(d_\mathsf{TV}(t)\) resp. \(d'_\mathsf{TV}(t)\) denote the total-variation distance between the time-\(t\) law of \(X\) resp. \(X'\) and \(\pi\). Suppose that there exist \(t_0\), \(t'_0\), \(w\) and \(w'\), all implicit functions of \(n\), such that\N\[\N\Phi(\alpha) := \lim_{n\to\infty} d_\mathsf{TV}(t_0 + \alpha w) \ \ \ \text{and} \ \ \ \Phi'(\alpha) := \lim_{n\to\infty} d'_\mathsf{TV}(t'_0 + \alpha w')\N\]\Nboth exist for all \(\alpha \in \mathbb R\); the function \(\Phi\) resp. \(\Phi'\) is the \textit{limit profile} of \(X\) resp. \(X'\). Theory is developed to compare \(\Phi\) and \(\Phi'\) in terms of the eigenvalues, see Lemma 1.4.\N\NThe author points out that \textit{any} of the usual random-transpositions shuffles, generated by the set of all transpositions in a symmetric group \(S_n\), commutes with any other symmetric random walk \(S_n\). This allows her to use the limit profile for the random-transposition shuffle, found recently by \textit{L. Teyssier} [Ann. Probab. 48, No. 5, 2323--2343 (2020; Zbl 1468.60091)], to bound the limit profile of other shuffles. Particularly, an analogous Poissonian limit for the star-transpositions shuffle at time \(n (\log n + c)\) is established as Theorem~1.3:\N\[\N\lim_{n\to\infty} d_\mathsf{TV}\bigl( n (\log n + c) \bigr) = d_\mathsf{TV}\bigl( \operatorname{Pois}(1 + e^{-c}), \operatorname{Pois}(1) \bigr).\N\]
reviewed by: Sam Thomas
Mathematics Subject Classification ID: 60J10
Mathematics Subject Classification ID: 60C05
zbMATH DE Number: 7854746
zbMATH Keywords: Markov chains
zbMATH Keywords: cutoff
zbMATH Keywords: limit profiles
zbMATH Keywords: mixing
zbMATH Keywords: star transpositions
MaRDI profile type: MaRDI publication profile
cites work: Trailing the dovetail shuffle to its lair
cites work: Cutoff for random to random card shuffle
cites work: Cutoff profile of ASEP on a segment
cites work: Q3811424
cites work: Q3995195
cites work: Q4426038
cites work: Comparison techniques for random walk on finite groups
cites work: Comparison theorems for reversible Markov chains
cites work: Walks on generating sets of Abelian groups
cites work: Bounds for Kac's master equation
cites work: Generating a random permutation with random transpositions
cites work: Time to Reach Stationarity in the Bernoulli–Laplace Diffusion Model
cites work: Cutoff for the Bernoulli-Laplace urn model with \(o(n)\) swaps
cites work: Random shuffles and group representations
cites work: Generating random elements in \(SL_ n(F_ q)\) by random transvections
cites work: Cut-off phenomenon in the uniform plane Kac walk
cites work: KAZHDAN CONSTANTS FOR SLn(ℤ)
cites work: The cutoff profile for the simple exclusion process on the circle
cites work: Q3549475
cites work: Cutoff on all Ramanujan graphs
cites work: A strong uniform time for random transpositions
cites work: Limit profiles for reversible Markov chains
cites work: On the mixing time of Kac's walk and other high-dimensional Gibbs samplers with constraints
cites work: Improved bounds for the mixing time of the random-to-random shuffle
cites work: Random rotations: Characters and random walks on \(SO(N)\)
cites work: Cutoff for non-negatively curved Markov chains
cites work: Refined estimates for some basic random walks on the symmetric and alternating groups
cites work: A lower bound for the mixing time of the random-to-random insertions shuffle
cites work: Limit profile for random transpositions
DOI: 10.1214/24-EJP1110
description: scientific article; zbMATH DE number 7854746