Sensitivity of mixing times in Eulerian digraphs

DOI10.1137/16M1073376zbMATH Open1390.05219arXiv1603.05639OpenAlexW2964161458MaRDI QIDQ4609786FDOQ4609786

Authors: Lucas Boczkowski, Yuval Peres, Perla Sousi 

Publication date: 26 March 2018

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: Let $X$ be a lazy random walk on a graph $G$. If $G$ is undirected, then the mixing time is upper bounded by the maximum hitting time of the graph. This fails for directed chains, as the biased random walk on the cycle $mathbb{Z}_n$ shows. However, we establish that for Eulerian digraphs, the mixing time is $O(mn)$, where $m$ is the number of edges and $n$ is the number of vertices. In the reversible case, the mixing time is robust to the change of the laziness parameter. Surprisingly, in the directed setting the mixing time can be sensitive to such changes. We also study exploration and cover times for random walks on Eulerian digraphs and prove universal upper bounds in analogy to the undirected case.

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

Recommendations

• The simple random walk and max-degree walk on a directed graph
• Sensitivity of mixing times
• On sensitivity of uniform mixing times
• Mixing times are hitting times of large sets
• Improved mixing rates of directed cycles by added connection

zbMATH Keywords

random walkmixing timeEulerian digraph

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Eulerian and Hamiltonian graphs (05C45) Random walks on graphs (05C81)

Cites Work

• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Random walk: A modern introduction
• Title not available (Why is that?)
• Title not available (Why is that?)
• Mathematical aspects of mixing times in Markov chains.
• Mixing times are hitting times of large sets
• On the cover time of random walks on graphs
• Short random walks on graphs
• Mixing time bounds via the spectral profile
• Sharp Bounds on Random Walk Eigenvalues via Spectral Embedding
• Card shuffling and Diophantine approximation

Cited In (11)

• Analysis of a non-reversible Markov chain speedup by a single edge
• The simple random walk and max-degree walk on a directed graph
• On an epidemic model on finite graphs
• Frogs on trees?
• Stationary distribution and cover time of sparse directed configuration models
• Sensitivity of mixing times of Cayley graphs
• Rapid social connectivity
• A characterization of \(L_{2}\) mixing and hypercontractivity via hitting times and maximal inequalities
• The exclusion process mixes (almost) faster than independent particles
• On sensitivity of uniform mixing times
• The asynchronous DeGroot dynamics

This page was built for publication: Sensitivity of mixing times in Eulerian digraphs

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