The simple random walk and max-degree walk on a directed graph
| dc.creator | Montenegro, Ravi | |
| dc.date | 2006-09-11 | |
| dc.date.accessioned | 2026-07-07T12:59:45Z | |
| dc.date.available | 2026-07-07T12:59:45Z | |
| dc.description | We show bounds on total variation and $L^{\infty}$ mixing times, spectral gap and magnitudes of the complex valued eigenvalues of a general (non-reversible non-lazy) Markov chain with a minor expansion property. This leads to the first known bounds for the non-lazy simple and max-degree walks on a (directed) graph, and even in the lazy case they are the first bounds of the optimal order. In particular, it is found 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. | |
| dc.identifier | https://arxiv.org/abs/math/0609303 | |
| dc.identifier | http://arxiv.org/abs/math/0609303 | |
| dc.identifier | Random Structures and Algorithms, vol 34:3, pp. 395-407, 2009. | |
| dc.identifier | doi:10.1002/rsa.20227 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/225670 | |
| dc.subject | Combinatorics | |
| dc.subject | Probability | |
| dc.subject | 60J10; 68W20 | |
| dc.title | The simple random walk and max-degree walk on a directed graph | |
| dc.type | text |