Premium
The simple random walk and max‐degree walk on a directed graph
Author(s) -
Montenegro Ravi
Publication year - 2009
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.20227
Subject(s) - random walk , mathematics , spectral gap , markov chain , degree (music) , combinatorics , eigenvalues and eigenvectors , mixing (physics) , simple (philosophy) , graph , directed graph , heterogeneous random walk in one dimension , statistical physics , discrete mathematics , mathematical analysis , statistics , physics , quantum mechanics , philosophy , epistemology , acoustics
We bound total variation and L ∞ mixing times, spectral gap and magnitudes of the complex valued eigenvalues of general (nonreversible nonlazy) Markov chains with a minor expansion property. The resulting bounds for the (nonlazy) simple and max‐degree walks on a (directed) graph are of the optimal order. It follows that, within a factor of two or four, the worst case of each of these mixing time and eigenvalue quantities is a walk on a cycle with clockwise drift. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009