The Cutoff Phenomenon for Random Birth and Death Chains

Abstract

For any distribution $\pi$ with support equal to $[n]=\{1,2,...,n\}$, we study the set ${\mathcal{A}}_{\pi }$ of tridiagonal stochastic matrices $K$ satisfying $\pi (i)K[i,j]=\pi (j)K[j,i]$ for all $i,j\in [n]$. These matrices correspond to birth and death chains with stationary distribution $\pi$. We study matrices $K$ drawn uniformly from ${\mathcal{A}}_{\pi }$, following the work of Diaconis and Wood on the case $\pi (i)=\frac{1}{n}$. We analyze a `block sampler' version of their algorithm for drawing from ${\mathcal{A}}_{\pi }$ at random, and use results from this analysis to draw conclusions about typical matrices. The main result is a soft argument comparing cutoff for sequences of random birth and death chains to cutoff for a special family of birth and death chains with the same stationary distributions.

34 Pages