Sensitivity of mixing times in Eulerian digraphs

DOI10.1137/16M1073376MaRDI QIDQ4609786zbMATH OpenOpenAlexFDO

Authors Lucas Boczkowski, Yuval Peres, Perla Sousi

Publication date 26 March 2018

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

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 3504208 (Why is no real title available?)
• scientific article; zbMATH DE number 3440485 (Why is no real title available?)
• Card shuffling and Diophantine approximation
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Mathematical aspects of mixing times in Markov chains.
• Mixing time bounds via the spectral profile
• Mixing times are hitting times of large sets
• On the cover time of random walks on graphs
• Random walk: A modern introduction
• Sharp bounds on random walk eigenvalues via spectral embedding
• Short random walks on graphs

Cited in

(12)

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

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)