Reversible Markov Chains and Random Walks on Graphs

Chapter 4 Hitting and Convergence Time, and Flow Rate, Parameters for Reversible Markov Chains (October 11, 1994)

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

τ*=maxi⁢j⁡(Ei⁢Tj+Ej⁢Ti)\tau^{*}=\max_{ij}(E_{i}T_{j}+E_{j}T_{i})

(ii) The average hitting time

τ0=∑i∑jπj⁢πi⁢Ei⁢Tj.\tau_{0}=\sum_{i}\sum_{j}\pi_{j}\pi_{i}E_{i}T_{j}.

(iii) The variation threshold time

τ1=inf⁡{t>0:d¯⁢(t)≤e-1}\tau_{1}=\inf\{t>0:\bar{d}(t)\leq e^{-1}\}

where as in Chapter 2 section yyy

d¯(t)=maxi⁢j||Pi(Xt∈⋅)-Pj(Xt∈⋅)||\bar{d}(t)=\max_{ij}||P_{i}(X_{t}\in\cdot)-P_{j}(X_{t}\in\cdot)||

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

(v) A “flow” parameter

τc=supA⁡π⁢(A)⁢π⁢(Ac)∑i∈A∑j∈Acπi⁢pi⁢j=supA⁡π⁢(Ac)Pπ(X1∈Ac|X0∈A)\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

τc=supA⁡π⁢(A)⁢π⁢(Ac)∑i∈A∑j∈Acπi⁢qi⁢j=supA⁡π⁢(Ac)⁢d⁢tPπ(Xd⁢t∈Ac|X0∈A)\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.

worst-caseaverage-casehitting timesτ*τ0mixing timesτ1τ2flowτc\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 (τ*,τ0,τ1,τ2,τc)(\tau^{*},\tau_{0},\tau_{1},\tau_{2},\tau_{c}): precisely,

12⁢τ*≥τ0≥τ2≥τc\frac{1}{2}\tau^{*}\geq\tau_{0}\geq\tau_{2}\geq\tau_{c}
66⁢τ0≥τ1≥τ266\tau_{0}\geq\tau_{1}\geq\tau_{2}

and perhaps the constant 6666 can be reduced to 11. 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 nn-vertex graphs each parameter may be as large as Θ⁢(n2)\Theta(n^{2}) but no larger; and τ*,τ0\tau^{*},\tau_{0} may be as small as Θ⁢(n)\Theta(n) and the other parameters as small as Θ⁢(1)\Theta(1), but no smaller. The property (for a sequence of chains) “τ0=O⁢(n)\tau_{0}=O(n)” is an analog of the property “transience” for a single infinite-state chain, and the property “τ2=O⁢(poly⁢(log⁡n))\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 τ1\tau_{1}, the numerical values of the parameters are unchanged by continuizing a discrete-time chain. And the results of this Chapter not involving τ1\tau_{1} hold for either discrete or continuous-time chains.

Bibliography