Sensitivity of mixing times in Eulerian digraphs

Understand

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.