Skip to content



Cutoff in total variation for birth-and-death chains

Lubetzky, E (Microsoft Research)
Wednesday 26 March 2008, 14:00-14:30

Seminar Room 1, Newton Institute


We prove that a family of continuous-time or lazy discrete-time birth-and-death chains, exhibits the cutoff phenomenon if and only if the product of the mixing-time and spectral-gap tends to infinity; in this case, the cutoff window of at most the geometric mean between the relaxation-time and mixing-time. An analogous result for convergence in separation was proved earlier by Diaconis and Saloff-Coste (2006) for birth-and-death chains started at an endpoint; 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. (Joint with J. Ding and Y. Peres).




The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.

Back to top ∧