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
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