Separation cut-offs for birth and death chains

DOI10.1214/105051606000000501MaRDI QIDQ997420zbMATH OpenOpenAlexFDO

Authors Persi Diaconis, Laurent Saloff-Coste

Publication date 6 August 2007

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

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

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)

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.

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

Cites work

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

Cited in

(48)

• Quantitative contraction rates for Markov chains on general state spaces
• Cut-off for \(n\)-tuples of exponentially converging processes
• On limiting characteristics for a non-stationary two-processor heterogeneous system with catastrophes, server failures and repairs
• 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
• Total variation cutoff in birth-and-death chains
• Reflection couplings and contraction rates for diffusions
• Cutoff for the averaging process on the hypercube and complete bipartite graphs
• 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
• Explicit criteria on separation cutoff for birth and death chains
• Mixing trichotomy for an Ehrenfest urn with impurities
• 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
• Spectral computations for birth and death chains
• Comparison of cutoffs between lazy walks and Markovian semigroups
• On the separation cut-off phenomenon for Brownian motions on high dimensional spheres
• 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
• Existence condition of strong stationary times for continuous time Markov chains on discrete graphs
• A criterion on separation cutoff for single-birth processes based on eigenvalues
• 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
• An interruptible algorithm for perfect sampling via Markov chains
• Commutation relations and Markov chains
• Skip-free Markov chains

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)