The simple random walk and max-degree walk on a directed graph

DOI10.1002/RSA.20227zbMATH Open1225.05222arXivmath/0609303OpenAlexW2952154243MaRDI QIDQ3633018FDOQ3633018

Authors: Ravi Montenegro 

Publication date: 16 June 2009

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/math/0609303

Recommendations

• Sensitivity of mixing times in Eulerian digraphs
• Comparing mixing times on sparse random graphs
• Improved mixing rates of directed cycles by added connection
• Comparing mixing times on sparse random graphs
• A polynomial bound on the mixing time of a Markov chain for sampling regular directed graphs

zbMATH Keywords

Markov chaineigenvaluesspectral gapEulerian graphevolving sets

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Random graphs (graph-theoretic aspects) (05C80) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Paths and cycles (05C38) Random walks on graphs (05C81)

Cites Work

• Blocking Conductance and Mixing in Random Walks
• Sharp edge, vertex, and mixed Cheeger inequalities for finite Markov kernels

Cited In (5)

• Random walks on digraphs, the generalized digraph Laplacian and the degree of asymmetry
• Title not available (Why is that?)
• Extreme values of the stationary distribution of random walks on directed graphs
• Sensitivity of mixing times in Eulerian digraphs
• The maximum relaxation time of a random walk

This page was built for publication: The simple random walk and max-degree walk on a directed graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3633018)