9 A Second Look at General Markov Chains (April 21, 1995)

9.6 Miscellany

9.6.1 Mixing times for irreversible chains

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

xxx state some of this ?

9.6.2 Balanced directed graphs

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 (=rv=r_{v}, say) at each vertex vv. Random walk on a balanced digraph clearly retains the “undirected” property that the stationary probabilities πv\pi_{v} are proportional to rvr_{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+C^{+} satisfies

maxvEvC+n3 in general; maxvEvC+6n2 on a regular balanced digraph. \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).

9.6.3 An absorption time problem

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

p(i,j)=0,  jip(i,j)=0,\ j\geq i

and p(1,1)=1p(1,1)=1. The chain is ultimately absorbed in state 11. 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 AA of {1,,n}\{1,\ldots,n\} with 1A1\not\in A define

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

and then define

Open Problem 9.27

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