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

$\max_{v}E_{v}C^{+}\leq n^{3}\mbox{ in general; }\max_{v}E_{v}C^{+}\leq 6n^{2}% \mbox{ on a regular balanced digraph. }$ |

(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

$p(i,j)=0,\ j\geq i$ |

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

$c(A)=\frac{|A||A^{c}|}{n\ \sum_{i\in A}\sum_{j\in A^{c}}p(i,j)}$ |

and then define

$\kappa=\max_{A}c(A).$ |

Prove that $\max_{i}E_{i}T_{1}$ is bounded by a polynomial function of $\kappa\log n$.

Generated on Mon Jun 2 14:23:48 2014 by LaTeXML