Premium
A semidefinite bound for mixing rates of Markov chains
Author(s) -
Kahale Nabil
Publication year - 1997
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/(sici)1098-2418(199712)11:4<299::aid-rsa2>3.0.co;2-u
Subject(s) - bounding overwatch , markov chain , semidefinite programming , mixing (physics) , mathematics , upper and lower bounds , spectral gap , combinatorics , markov chain mixing time , order (exchange) , discrete mathematics , markov model , computer science , variable order markov model , mathematical optimization , statistics , mathematical analysis , physics , finance , quantum mechanics , artificial intelligence , economics
We study general geometric techniques for bounding the spectral gap of a reversible Markov chain. We show that the best bound obtainable using these techniques can be computed in polynomial time via semidefinite programming, and is off by at most a factor of order log 2 n , where n is the number of states. © 1997 John Wiley & Sons, Inc. Random Struct. Alg. , 11 , 299–313 (1997)