Total variation cutoff in birth-and-death chains
type: Item
instance of: scholarly article
title: Total variation cutoff in birth-and-death chains
zbMATH Open document ID: 1190.60005
author: Jian Ding
author: Eyal Lubetzky
author: Yuval Peres
publication date: 2010-01-15T00:00:00Z
full work available at URL: https://arxiv.org/abs/0801.2625
review text: The authors investigate the cutoff phenomenon for sequences of Markov chains where these chains exhibit sharp transitions in their convergence to their stationary distributions. It was observed recently by \textit{Y. Peres} [``Sharp thresholds for mixing times'', in: American Institute of Mathematics (AIM) Research Workshop, Palo Alto; \url{http://www.aimath.org/WWN/mixingtimes} (2004)] that a necessary condition for cutoff phenomena for sequences of reversible chains is that the products of mixing-times and spectral gaps tend to infinity. Moreover, it was shown recently by \textit{P. Diaconis} and \textit{L. Saloff-Coste} [Ann. Appl. Probab. 16, No.~4, 2098--2122 (2006; Zbl 1127.60081)] that this condition is also sufficient for continuous-time birth-and-death chains starting in end points when convergence is measured in separation. In the paper under review it is shown that the condition is also sufficient with respect to total variation distance for certain chains, namely for continuous-time birth-and-death chains as well as for socalled lazy discrete time birth-and-death chains where \(P(x,x)\geq1/2\) holds for all states \(x\). The main ingredient for the proof is a a sharp estimate for the difference for the mixing times \(t_{\text{mix}}(\varepsilon)-t_{\text{mix}}(1-\varepsilon)\) for \(\varepsilon\in]0,1/2[\) in terms of the product of the spectral gap and \(t_{\text{mix}}(1/4)\).
reviewed by: Michael Voit
Mathematics Subject Classification ID: 60B10
Mathematics Subject Classification ID: 60J27
Mathematics Subject Classification ID: 60J05
zbMATH DE Number: 5659491
zbMATH Keywords: sufficient condition for cutoff-phenomenon
zbMATH Keywords: birth-and-death chains
zbMATH Keywords: spectral gap
zbMATH Keywords: total variation distance
MaRDI profile type: Publication
OpenAlex ID: W2043236011
arXiv ID: 0801.2625
cites work: Q3660628
cites work: Shuffling Cards and Stopping Times
cites work: The cutoff phenomenon for ergodic Markov processes
cites work: The cutoff phenomenon in finite Markov chains.
cites work: Strong stationary times via a new form of duality
cites work: On times to quasi-stationarity for birth and death processes
cites work: Separation cut-offs for birth and death chains
cites work: Generating a random permutation with random transpositions
cites work: The mixing time evolution of Glauber dynamics for the mean-field Ising model
cites work: The passage time distribution for a birth-and-death chain: Strong stationary duality gives a first stochastic proof
cites work: On hitting times and fastest strong stationary times for skip-free and more general chains
cites work: Maximal coupling
cites work: A maximal coupling for Markov chains
cites work: Q4775958
cites work: Coincidence properties of birth and death processes
cites work: Markov chain models - rarity and exponentiality
cites work: Glauber dynamics for the mean-field Ising model: cut-off, critical power law, and metastability
cites work: Q4863617
cites work: On coupling of Markov chains
cites work: Q4450069
DOI: 10.1007/S00440-008-0185-3
Recommended article: Separation cut-offs for birth and death chains
Recommended article: Characterization of cutoff for reversible Markov chains
Recommended article: The cutoff phenomenon for ergodic Markov processes
Recommended article: Cutoff for Markov chains: some examples and applications
Recommended article: The power of averaging at two consecutive time steps: proof of a mixing conjecture by Aldous and Fill
Recommended article: The \(L^{2}\)-cutoff for reversible Markov processes
Recommended article: Comparison of Cutoffs Between Lazy Walks and Markovian Semigroups
Recommended article: On the mixing time and spectral gap for birth and death chains
Recommended article: A technical report on hitting times, mixing and cutoff
published in: Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete
description: scientific article