Separation cut-offs for birth and death chains

DOI10.1214/105051606000000501zbMATH Open1127.60081arXivmath/0702411OpenAlexW1986979025MaRDI QIDQ997420FDOQ997420

Authors: Persi Diaconis, Laurent Saloff-Coste 

Publication date: 6 August 2007

Published in: The Annals of Applied Probability (Search for Journal in Brave)

Abstract: This paper gives a necessary and sufficient condition for a sequence of birth and death chains to converge abruptly to stationarity, that is, to present a cut-off. The condition involves the notions of spectral gap and mixing time. Y. Peres has observed that for many families of Markov chains, there is a cut-off if and only if the product of spectral gap and mixing time tends to infinity. We establish this for arbitrary birth and death chains in continuous time when the convergence is measured in separation and the chains all start at 0.

Full work available at URL: https://arxiv.org/abs/math/0702411

Recommendations

• Total variation cutoff in birth-and-death chains
• Characterization of cutoff for reversible Markov chains
• Explicit criteria on separation cutoff for birth and death chains
• On the mixing time and spectral gap for birth and death chains
• Computing cutoff times of birth and death chains

zbMATH Keywords

mixing timestrong stationary timeergodic Markov chainsbirth and death chains

Mathematics Subject Classification ID

Convergence of probability measures (60B10) Discrete-time Markov processes on general state spaces (60J05) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80) Continuous-time Markov processes on discrete state spaces (60J27)

Cites Work

• Title not available (Why is that?)
• Analysis of systematic scan Metropolis algorithms using Iwahori-Hecke algebra techniques
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Shuffling Cards and Stopping Times
• Generating a random permutation with random transpositions
• Title not available (Why is that?)
• Title not available (Why is that?)
• Strong uniform times and finite random walks
• Markov chain models - rarity and exponentiality
• Title not available (Why is that?)
• Strong stationary times via a new form of duality
• The cutoff phenomenon in finite Markov chains.
• Comparison techniques for random walk on finite groups
• Logarithmic Sobolev inequalities for finite Markov chains
• Ehrenfest urn models
• A Note on the Theory of Moment Generating Functions
• What do we know about the Metropolis algorithm?
• Identifying Coefficients in the Spectral Representation for First Passage Time Distributions
• Rates of convergence of random walk on distance regular graphs
• Time to Reach Stationarity in the Bernoulli–Laplace Diffusion Model
• Title not available (Why is that?)
• Title not available (Why is that?)
• On mixing of certain random walks, cutoff phenomenon and sharp threshold of random matroid processes
• Strong stationary duality for continuous-time Markov chains. I: Theory
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• An inverse problem in birth and death processes
• The nearest neighbor random walk on subspaces of a vector space and rate of convergence

Cited In (48)

• On limiting characteristics for a non-stationary two-processor heterogeneous system with catastrophes, server failures and repairs
• Cut-off for \(n\)-tuples of exponentially converging processes
• No cut-off phenomenon for the ``Insect Markov chain
• Random doubly stochastic tridiagonal matrices
• Entropy-driven cutoff phenomena
• On hitting time, mixing time and geometric interpretations of Metropolis-Hastings reversiblizations
• Cutoff for the averaging process on the hypercube and complete bipartite graphs
• Total variation cutoff in birth-and-death chains
• Reflection couplings and contraction rates for diffusions
• Cutoff at the ``entropic time for sparse Markov chains
• Glauber dynamics for the mean-field Ising model: cut-off, critical power law, and metastability
• Hitting time and mixing time bounds of Stein's factors
• Cut-off and exit from metastability: Two sides of the same coin
• The cutoff phenomenon for Ehrenfest chains
• On times to quasi-stationarity for birth and death processes
• The passage time distribution for a birth-and-death chain: Strong stationary duality gives a first stochastic proof
• Antiduality and Möbius monotonicity: generalized coupon collector problem
• Lower bounds for the rate of convergence for continuous-time inhomogeneous Markov chains with a finite state space
• A product chain without cutoff
• The cutoff phenomenon for random birth and death chains
• Mixing trichotomy for an Ehrenfest urn with impurities
• Explicit criteria on separation cutoff for birth and death chains
• Mixing times for the commuting chain on CA groups
• Analysis of non-reversible Markov chains via similarity orbits
• Separation cutoff for upward skip-free chains
• Gibbs sampling, exponential families and orthogonal polynomials
• Fluctuations analysis of finite discrete birth and death chains with emphasis on Moran models with mutations
• Hitting time distributions for denumerable birth and death processes
• Mixing reversible Markov chains in the max-\(\ell^2\)-distance
• On the separation cut-off phenomenon for Brownian motions on high dimensional spheres
• Comparison of cutoffs between lazy walks and Markovian semigroups
• Spectral computations for birth and death chains
• On the mixing time and spectral gap for birth and death chains
• Cutoff for the Ising model on the lattice
• Computing cutoff times of birth and death chains
• A criterion on separation cutoff for single-birth processes based on eigenvalues
• Existence condition of strong stationary times for continuous time Markov chains on discrete graphs
• Separation and coupling cutoffs for tuples of independent Markov processes
• The \(L^{2}\)-cutoff for reversible Markov processes
• On absorption times and Dirichlet eigenvalues
• Strong stationary duality for diffusion processes
• Separation cutoffs for random walk on irreducible representations
• Cut-off and escape behaviors for birth and death chains on trees
• Abrupt convergence and escape behavior for birth and death chains
• Skip-free Markov chains
• An interruptible algorithm for perfect sampling via Markov chains
• Commutation relations and Markov chains
• Quantitative contraction rates for Markov chains on general state spaces

This page was built for publication: Separation cut-offs for birth and death chains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q997420)