Premium
The cutoff phenomenon for random birth and death chains
Author(s) -
Smith Aaron
Publication year - 2017
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20693
Subject(s) - markov chain , cutoff , tridiagonal matrix , mathematics , phenomenon , statistical physics , distribution (mathematics) , birth–death process , combinatorics , statistics , physics , mathematical analysis , quantum mechanics , sociology , demography , eigenvalues and eigenvectors , population
For any distribution π on [ n ] = { 1 , 2 , … , n } , we study elements drawn at random from the setA π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 fromA πand use results from this analysis to draw conclusions about the Markov chains corresponding to typical elements ofA π . 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