The cutoff phenomenon for random birth and death chains. Issue 2 (1st November 2016) - Smith, Aaron
Abstract : For any distribution π on [ n ] = 1, 2, …, n , we study elements drawn at random from the set A π of tridiagonal stochastic matrices K satisfying π ( i ) K [ i, j ] = π ( j ) K [ j, i ] for all i, j ∈ [ n ] . These matrices correspond to birth and death chains with stationary distribution π . We analyze an algorithm for sampling from A π and use results from this analysis to draw conclusions about the Markov chains corresponding to typical elements of A π . Our main interest is in determining when certain sequences of random birth and death chains exhibit the cutoff phenomenon . © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 287–321, 2017