The elementary theory of general finite Markov chains (cf. Chapter 2) focuses on exact formulas and limit theorems. My view is that, to the extent there is any intermediate-level mathematical theory of reversible chains, it is a theory of inequalities. Some of these were already seen in Chapter 3. This chapter is my attempt to impose some order on the subject of inequalities. We will study the following five parameters of a chain. Recall our standing assumption that chains are finite, irreducible and reversible, with stationary distribution $\pi$.

(i) The maximal mean commute time

$\tau^{*}=\max_{ij}(E_{i}T_{j}+E_{j}T_{i})$ |

(ii) The average hitting time

$\tau_{0}=\sum_{i}\sum_{j}\pi_{j}\pi_{i}E_{i}T_{j}.$ |

(iii) The variation threshold time

$\tau_{1}=\inf\{t>0:\bar{d}(t)\leq e^{-1}\}$ |

where as in Chapter 2 section yyy

$\bar{d}(t)=\max_{ij}||P_{i}(X_{t}\in\cdot)-P_{j}(X_{t}\in\cdot)||$ |

(iv) The relaxation time $\tau_{2}$, i.e. the time constant in the asymptotic rate of convergence to the stationary distribution.

(v) A “flow” parameter

$\tau_{c}=\sup_{A}\frac{\pi(A)\pi(A^{c})}{\sum_{i\in A}\sum_{j\in A^{c}}\pi_{i}% p_{ij}}=\sup_{A}\frac{\pi(A^{c})}{P_{\pi}(X_{1}\in A^{c}|X_{0}\in A)}$ |

in discrete time, and

$\tau_{c}=\sup_{A}\frac{\pi(A)\pi(A^{c})}{\sum_{i\in A}\sum_{j\in A^{c}}\pi_{i}% q_{ij}}=\sup_{A}\frac{\pi(A^{c})\ dt}{P_{\pi}(X_{dt}\in A^{c}|X_{0}\in A)}$ |

in continuous time.

The following table may be helpful. “Average-case” is intended to indicate essential use of the stationary distribution.

$\begin{array}[]{ccc}&\mbox{worst-case}&\mbox{average-case}\\ \mbox{hitting times}&\tau^{*}&\tau_{0}\\ \mbox{mixing times}&\tau_{1}&\tau_{2}\\ \mbox{flow}&&\tau_{c}\end{array}$

The table suggests there should be a sixth parameter, but I don’t have a candidate.

The ultimate point of this study, as will seen in following chapters, is

- •
For many questions about reversible Markov chains, the way in which the answer depends on the chain is related to one of these parameters

- •
so it is useful to have methods for estimating these parameters for particular chains.

This Chapter deals with relationships between these parameters, simple illustrations of properties of chains which are closely connected to the parameters, and methods of bounding the parameters. To give a preview, it turns out that these parameters are essentially decreasing in the order $(\tau^{*},\tau_{0},\tau_{1},\tau_{2},\tau_{c})$: precisely,

$\frac{1}{2}\tau^{*}\geq\tau_{0}\geq\tau_{2}\geq\tau_{c}$ |

$66\tau_{0}\geq\tau_{1}\geq\tau_{2}$ |

and perhaps the constant $66$ can be reduced to $1$. There are no general reverse inequalities, but reverse bounds involving extra quantities provide a rich and sometimes challenging source of problems.

The reader may find it helpful to read this chapter in parallel with the list of examples of random walks on unweighted graphs in Chapter 5. As another preview, we point out that on regular $n$-vertex graphs each parameter may be as large as $\Theta(n^{2})$ but no larger; and $\tau^{*},\tau_{0}$ may be as small as $\Theta(n)$ and the other parameters as small as $\Theta(1)$, but no smaller. The property (for a sequence of chains) “$\tau_{0}=O(n)$” is an analog of the property “transience” for a single infinite-state chain, and the property “$\tau_{2}=O(\mbox{poly}(\log n))$” is an analog of the “non-trivial boundary” property for a single infinite-state chain. These analogies are pursued in Chapter yyy.

The next five sections discuss the parameters in turn, the relationship between two different parameters being discussed in the latter’s section. Except for $\tau_{1}$, the numerical values of the parameters are unchanged by continuizing a discrete-time chain. And the results of this Chapter not involving $\tau_{1}$ hold for either discrete or continuous-time chains.

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