Total-variation cutoff in birth-and-death chains

Details Total-variation cutoff in birth-and-death chains Total-variation cutoff in birth-and-death chains

2008-01-17

arxiv.org/abs/0801.2625v4

Mathematics

Probability

25 pages

Scientific paper

The cutoff phenomenon describes a case where a Markov chain exhibits a sharp transition in its convergence to stationarity. In 1996, Diaconis surveyed this phenomenon, and asked how one could recognize its occurrence in families of finite ergodic Markov chains. In 2004, the third author noted that a necessary condition for cutoff in a family of reversible chains is that the product of the mixing-time and spectral-gap tends to infinity, and conjectured that in many settings, this condition should also be sufficient. Diaconis and Saloff-Coste (2006) verified this conjecture for continuous-time birth-and-death chains, started at an endpoint, with convergence measured in separation. It is natural to ask whether the conjecture holds for these chains in the more widely used total-variation distance. In this work, we confirm the above conjecture for all continuous-time or lazy discrete-time birth-and-death chains, with convergence measured via total-variation distance. Namely, if the product of the mixing-time and spectral-gap tends to infinity, the chains exhibit cutoff at the maximal hitting time of the stationary distribution median, with a window of at most the geometric mean between the relaxation-time and mixing-time. In addition, we show that for any lazy (or continuous-time) birth-and-death chain with stationary distribution $\pi$, the separation $1 - p^t(x,y)/\pi(y)$ is maximized when $x,y$ are the endpoints. Together with the above results, this implies that total-variation cutoff is equivalent to separation cutoff in any family of such chains.

Affiliated with

Also associated with

No associations

Rating

Total-variation cutoff in birth-and-death chains does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Total-variation cutoff in birth-and-death chains, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Total-variation cutoff in birth-and-death chains will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-392761