The cutoff phenomenon for random birth and death chains. Issue 2 (1st November 2016)

• Record Type: Journal Article
• Authors: Smith, Aaron
• Is Part Of: Random structures & algorithms. Volume 50:Issue 2(2017)
• Page Start: 287
• Page End: 321
• Publication Date: 2016-11-01
• Subjects: Markov chains mixing times -- cutoff phenomenon -- birth and death chain -- random matrix; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20693
• Languages: English
• ISSNs: 1042-9832

Abstract

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