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
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom