3.5 Complete monotonicity

As a quick application, we give bounds on mean hitting times to a single state from a stationary start. Recall $q_{i}=\sum_{j\neq i}q_{ij}$ is the exit rate from $i$, and $\tau_{2}$ is the relaxation time of the chain.

By continuization, the Lemma holds in discrete time, replacing $q_{i}$ by $1-p_{ii}$.

Proof. The mean hitting time formula is

Write $f(t)$ for the integrand. We know $f$ is CM, and here $\lambda\geq\lambda_{2}$ by (3.40), and $f^{\prime}(0)=-q_{i}$, so the extreme bounds of Lemma 3.16 become, after multiplying by $f(0)=1-\pi_{i}$,

Integrating these bounds gives the result.    

We can now give general lower bounds on some basic parameters we will study in Chapter 4.

Remark. These inequalities become equalities for random walk on the complete graph (Chapter 5 ^††margin: 4/22/96 versionExample 9). By examining the proof, it can be shown that this is the only chain where an equality holds.

Proof. We go to the continuized chain, which has $q_{i}=1-p_{ii}\leq 1$. Then

giving (3.53). By the eigentime identity,

and so (3.56) follows from (3.53).

Now fix $i$ and write $\tau_{0}=\sum_{j}\pi_{j}E_{k}T_{j}$, which (by the random target lemma) doesn’t depend on $k$. Then

If the right side were strictly less than $2(n-1)$ for all $i$, then

which implies

contradicting (3.53). Therefore there exists an $i$ such that

and so there exists $j\neq i$ such that $E_{i}T_{j}+E_{j}T_{i}\geq 2(n-1)$. This is (3.54), and (3.55) follows immediately.    

There are several other results in the spirit of Lemma 3.17 and Proposition 3.18. For instance, (22) in Chapter 2 ^††margin: 9/10/99 versionsays that for a general discrete-time chain,

Appealing to Lemma 3.17 gives, after a little algebra,

Again, equality holds for random walk on the complete graph.

We’re going to build some vague discussion around the following simple result.

Proof.

by reversibility. Putting $k=i$, $s=t$ gives (3.58). Rewriting the above equality as

and applying the Cauchy–Schwarz inequality, we get the bound $\sqrt{a_{i}(t)a_{k}(s)}$, where

This proves (3.59). The cruder bound (3.60) is sometimes easier to use than (3.59) and is proved similarly.    

Discussion. Recalling from Chapter 2 ^††margin: 9/10/99 versionSection 4.2 the definition of $L^{2}$ distance between distributions, (3.58) says

In continuous time, we may regard the assertion “$\|P_{i}(X_{t}\in\cdot)-\pi\|_{2}$ is decreasing in $t$” as a consequence of the equality in (3.61) and the CM property of $p_{ii}(t)$. This assertion in fact holds for general chains, as pointed out in Chapter 2 ^††margin: 9/10/99 versionLemma 35. Loosely, the general result of Chapter 2 ^††margin: 9/10/99 versionLemma 35 says that in a general chain the ratios $(P_{\rho}(X_{t}=j)/\pi_{j},\,j\in I)$ considered as an unordered set tend to smooth out as $t$ increases. For a reversible chain, much more seems to be true. There is some “intrinsic geometry” on the state space such that, for the chain started at $i$, the probability distribution as time increases from $0$ “spreads out smoothly” with respect to the geometry. It’s hard to formalize that idea convincingly. On the other hand, (3.61) does say convincingly that the rate of convergence of the single probability $p_{ii}(t)$ to $\pi(i)$ is connected to a rate of convergence of the entire distribution $P_{i}(X_{t}\in\cdot)$ to $\pi(\cdot)$. This intimate connection between the local and the global behavior of reversible chains underlies many of the technical inequalities concerning mixing times in Chapter 4 ^††margin: 10/11/94 versionand subsequent chapters.

We mentioned in Chapter 2 ^††margin: 9/10/99 versionSection 2.2 that most of the simple identities there for mean hitting times $E_{i}T_{j}$ on singletons have no simple analogs for hitting times $T_{A}$ on subsets. One exception is Kac’s formula (Chapter 2 ^††margin: 9/10/99 versionCorollary 24), which says that for a general discrete-time chain

It turns out that for reversible chains there are useful inequalities relating the distributions of $T_{A}$ under different initial distributions. These are simplest in continuous time as consequences of CM: as always, interesting consequences may be applied to discrete-time chains via continuization.

Recall $\pi_{A}$ is the stationary distribution conditioned to $A$:

Trivially

Define the ergodic exit distribution $\rho_{A}$ from $A$ by

where $Q(A,A^{c})$ is the ergodic flow rate out of $A$:

By stationarity, $Q(A,A^{c})=Q(A^{c},A)$.

Remarks. (a) In ^††margin: Concerning (b): The results cited from later require that the chain restricted to $A^{c}$ be irreducible, but I think that requirement can be dropped using a limiting argument. discrete time we can define $\rho_{A}$ and $Q(A,A^{c})$ by replacing $q_{ij}$ by $p_{ij}$ in (3.65)–(3.66), and then (3.69) holds in discrete time. The left equality of (3.69) is then a reformulation of Kac’s formula (3.62), because

(b) Equation (3.83) and Corollary 3.34 [together with remark (b) following Theorem 3.33] later show that $1/\lambda_{A}\leq\tau_{2}/\pi(A)$. So (3.70) can be regarded as a consequence of (3.69). Reverse inequalities will be studied in Chapter 4. ^††margin: 10/11/94 version

Proof of Proposition 3.21. First consider the case where $A$ is a singleton $\{a\}$. Then (3.70) is an immediate consequence of Lemma 3.17. The equalities in (3.69) and in (3.67) are general identities for stationary processes [(24) and (23) in Chapter 2]. ^††margin: 9/10/99 versionWe shall prove below that $T_{A}$ is CM under $P_{\pi_{I\setminus\{a\}}}$. Then by (3.63), (3.67), and (3.46), $T_{A}$ is also CM under the other two initial distributions. Then the second inequality of (3.68) is the upper bound in Lemma 3.16, and the first is a consequence of (3.67) and Lemma 3.16. And (3.69) follows from (3.68) by integrating over $t$.

To prove that $T_{A}$ is CM under $P_{\pi_{I\setminus\{a\}}}$, introduce a parameter $0<\varepsilon<1$ and consider the modified chain $(X^{\varepsilon}_{t})$ with transition rates

The modified chain remains reversible, and its stationary distribution is of the form

where the weights $b_{1},b_{2}$ depend only on $\varepsilon$ and $\pi_{a}$. Now as $\varepsilon\rightarrow 0$ with $t$ fixed,

because the chain gets “stuck” upon hitting $a$. But the left side is CM by (3.52), so the right side (which does not depend on $\varepsilon$) is CM, because the class of CM distributions is closed under pointwise limits. (The last assertion is in general the continuity theorem for Laplace transforms [133] p. 83, though for our purposes we need only the simpler fact that the set of functions of the form (3.45) with at most $n$ summands is closed.)

This completes the proof when $A$ is a singleton. We now claim that the case of general $A$ follows from the collapsing principle (Chapter 2 ^††margin: 9/10/99 versionSection 7.3), i.e., by applying the special case to the chain in which the subset $A$ is collapsed into a single state. This is clear for all the assertions of Proposition 3.21 except for (3.70), for which we need the fact that the relaxation time $\tau_{2}^{A}$ of the collapsed chain is at most $\tau_{2}$. This fact is proved as Corollary 3.27 below.    

Remark. Note that the CM property implies a supermultiplicitivity property for hitting times from stationarity in a continuous-time reversible chain:

Contrast with the general submultiplicitivity property (Chapter 2 ^††margin: 9/10/99 versionSection 4.3) which holds when $P_{\pi}$ is replaced by $\max_{i}P_{i}$.

In many circumstances, the distribution of the first hitting time $T_{A}$ on a subset $A$ of states with $\pi(A)$ small (equivalently, with $ET_{A}$ large) can be approximated by the exponential distribution with the same mean. As with the issue of convergence to the stationary distribution, such approximations can be proved for general chains (see Notes), but it is easier to get explicit bounds in the reversible setting. If $T$ has a CM distribution, then [as at (3.47), but replacing $1/\Lambda$ by $\Theta$] we may suppose $T\ \stackrel{d}{=}\ \Theta\xi$. We calculate

and so

with equality iff $\Theta$ is constant, i.e., iff $T$ has exponential distribution. This suggests that the difference $\frac{ET^{2}}{2(ET)^{2}}-1$ can be used as a measure of “deviation from exponentiality”. Let us quote a result of Mark Brown ([72] Theorem 4.1(iii)) which quantifies this idea in a very simple way.

So we can use this bound for hitting times $T_{A}$ in a stationary reversible chain. At first sight the bound seems useful only if we can estimate $E_{\pi}T^{2}_{A}$ and $E_{\pi}T_{A}$ accurately. But the following remarkable variation shows that for the hitting time distribution to be approximately exponential it is sufficient that the mean hitting time be large compared to the relaxation time $\tau_{2}$.

Proof. By the collapsing principle (Chapter 2 ^††margin: 9/10/99 versionSection 7.3) we may suppose $A$ is a singleton $\{j\}$, because (Corollary 3.27 below) collapsing cannot increase the relaxation time. Combining the mean hitting time formula with the expression (3.41) for $Z_{jj}$ in terms of the spectral representation (3.33),

A similar calculation, exhibited below, shows

But $\lambda_{m}^{-2}\leq\lambda_{2}^{-1}\lambda_{m}^{-1}=\tau_{2}\lambda_{m}^{-1}$ for $m\geq 2$, so the right side of (3.73) is bounded by $\pi^{-1}_{j}\tau_{2}\sum_{m\geq 2}u^{2}_{jm}\lambda^{-1}_{m}$, which by (3.72) equals $\tau_{2}E_{\pi}T_{j}$. Applying Proposition 3.22 gives Proposition 3.23.

We give a straightforward but tedious verification of (3.73) (see also Notes). The identity $x^{2}/2=\int_{0}^{\infty}(x-t)^{+}\,dt,\ x\geq 0$ starts the ^††margin: Chapter 2 reference in following display is to 9/10/99 version. calculation

Expanding the square, the cross-term vanishes and the first term becomes $(Z_{jj}/\pi_{j})^{2}=(E_{\pi}T_{j})^{2}$, so

To finish the calculation,

See the Notes for a related result, Theorem 3.43.