The simple random walk and max‐degree walk on a directed graph |
| |
Authors: | Ravi Montenegro |
| |
Affiliation: | Department of Mathematical Sciences, University of Massachusetts Lowell, Lowell, Massachusetts 01854 |
| |
Abstract: | 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 |
| |
Keywords: | Markov chain evolving sets Eulerian graph spectral gap eigenvalues |
|
|