9.6 Miscellany

In Chapter 4 yyy we discussed equivalences between different definitions of “mixing time” in the $\tau_{1}$ family. Lovasz and Winkler [240] give a detailed treatment of analogous results in the non-reversible case.

xxx state some of this ?

Any Markov chain can be viewed as random walk on a weighted directed graph, but even on unweighted digraphs it is hard to relate properties on the walk to graph-theoretic properties, because (as we have often observed) it is in general hard to get useful information about the stationary distribution. An exception is the case of a balanced digraph, i.e. when the in-degree equals the out-degree ($=r_{v}$, say) at each vertex $v$. Random walk on a balanced digraph clearly retains the “undirected” property that the stationary probabilities $\pi_{v}$ are proportional to $r_{v}$. Now the proofs of Theorems yyy and yyy in Chapter 6 extend unchanged to the balanced digraph setting, showing that the cover-and-return time $C^{+}$ satisfies

(The proofs rely on the edge-commute inequality (Chapter 3 yyy), rather than any “resistance” property).

Consider a Markov chain on states $\{1,2,\ldots,n\}$ for which the only possible transitions are downward, i.e. for $i\geq 2$ we have

and $p(1,1)=1$. The chain is ultimately absorbed in state $1$. A question posed by Gil Kalai is whether there is a bound on the mean absorption time involving a parameter similar to that appearing in Cheeger’s inequality. For each proper subset $A$ of $\{1,\ldots,n\}$ with $1\not\in A$ define

and then define