3.6 Extremal characterizations of eigenvalues

A reversible chain has an associated Dirichlet form ${\cal E}$, defined as follows. For functions $g:I\rightarrow R$ write

in discrete time, and substitute $q_{ij}$ for $p_{ij}$ in continuous time. One can immediately check the following equivalent definitions. In discrete time

In continuous time

where the sum includes $j=i$. Note also that for random walk on a weighted graph, (3.74) becomes

Recall from Chapter 2 ^††margin: 9/10/99 versionSection 6.2 the discussion of $L^{2}$ norms for functions and measures. In particular

The relevance of ${\cal E}$ can be seen in the following lemma.

Proof. $\|\rho(t)-\pi\|_{2}^{2}=\sum_{j}\pi^{-1}_{j}\rho^{2}_{j}(t)\,-1$, so using the forward equations

we get

and the result follows from (3.76).    

For ease of comparison we state below three results which will be proved in subsequent sections. These results are commonly presented “the other way up” using infs rather than sups, but our presentation is forced by our convention of consistently defining parameters to have dimensions of “time” rather than “$1/\mbox{time}$”. The sups are over functions $g:I\rightarrow R$ satisfying specified constraints, and excluding $g\equiv 0$. The results below are the same in continuous and discrete time—that is, continuization doesn’t change the numerical values of the quantities we consider. We shall give the proofs in discrete time.

Extremal characterization of relaxation time. The relaxation time $\tau_{2}$ satisfies

Extremal characterization of quasistationary mean hitting time. Given a subset $A$, let $\alpha_{A}$ be the quasistationary distribution on $A^{c}$ defined at (3.82). Then the quasistationary mean exit time is

Extremal characterization of mean commute times. For distinct states $i,j$ the mean commute time satisfies

Because the state space is finite, the sups are attained, and there are theoretical descriptions of the $g$ attaining the extrema in all three cases. An immediate practical use of these characterizations in concrete examples is to obtain lower bounds on the parameters by inspired guesswork, that is by choosing some simple explicit “test function” $g$ which seems qualitatively right and computing the right-hand quantity. See Chapter 14 ^††margin: 3/10/94 versionExample 32 for a typical example. Of course we cannot obtain upper bounds this way, but extremal characterizations can be used as a starting point for further theoretical work (see in particular the bounds on $\tau_{2}$ in Chapter 4 ^††margin: 10/11/94 versionSection 4).

The first two extremal characterizations are in fact just reformulations of the classical Rayleigh–Ritz extremal characterization of eigenvalues, which goes as follows ([183] Theorem 4.2.2 and eq. 4.2.7). Let $S$ be a symmetric matrix with eigenvalues $\mu_{1}\geq\mu_{2}\geq\cdots$. Then

and an ${\bf x}$ attaining the sup is an eigenvalue corresponding to $\mu_{1}$ (of course sups are over ${\bf x}\not\equiv 0$). And

and a ${\bf y}$ attaining the sup is an eigenvalue corresponding to $\mu_{2}$.

As observed in Section 3.4, given a discrete-time chain with transition matrix $P$, the symmetric matrix $(s_{ij}=\pi^{1/2}_{i}p_{ij}\pi^{-1/2}_{j})$ has maximal eigenvalue $1$ with corresponding eigenvector $(\pi^{1/2}_{i})$. So applying (3.79) and writing $y_{i}=\pi^{1/2}_{i}g(i)$, the second-largest eigenvalue (of $S$ and hence of $P$) is given by

In probabilistic notation the fraction is

Since $\tau_{2}=1/(1-\lambda_{2})$ in discrete time we have proved the first of our extremal characterizations.

A function $g_{0}$, say, attaining the sup in the extremal characterization is, by examining the argument above, a right eigenvector associated with $\lambda_{2}$:

(From this point on in the discussion, we assume $g_{0}$ is normalized so that $\|g_{0}\|_{2}=1$.)  The corresponding left eigenvector $\theta$ :

is the signed measure $\theta$ such that $\theta_{i}=\pi_{i}g_{0}(i)$. To continue a somewhat informal discussion of the interpretation of $g_{0}$, it is convenient to switch to continuous time (to avoid issues of negative eigenvalues) and to assume $\lambda_{2}$ has multiplicity $1$. The equation which relates distribution at time $t$ to initial distribution,

can also be used to define signed measures evolving from an initial signed measure. For the initial measure $\theta$ we have

For any signed measure $\nu=\nu(0)$ with $\sum_{i}\nu_{i}(0)=0$ we have

So $\theta$ can be regarded as “the signed measure which relaxes to $0$ most slowly”. For a probability measure $\rho(0)$, considering $\rho(0)-\pi$ gives

So $\theta$ has the interpretation of “the asymptotic normalized difference between the true distribution at time $t$ and the stationary distribution”. Finally, from (3.80) with $\rho(0)$ concentrated at $i$ (or from the spectral representation)

So $g_{0}$ has the interpretation of “the asymptotic normalized size of deviation from stationarity, as a function of the starting state”. When the state space has some geometric structure – jumps go to nearby states – one expects $g_{0}$ to be a “smooth” function, exemplified by the cosine function arising in the $n$-cycle (Chapter 5 ^††margin: 4/22/96 versionExample 7).

Here is a fundamental “finite-time” result. ^††margin: Good name for Lemma 3.26 – looks good to DA !

Proof. Write $f_{j}(t)=\rho_{j}(t)/\pi_{j}$. Then

Integrating, $\|\rho(t)-\pi\|_{2}^{2}\leq e^{-2t/\tau_{2}}\|\rho(0)-\pi\|_{2}^{2}$, and the result follows.    

Alternatively, Lemma 3.26 follows by observing that

and applying Lemma 3.16. The fact (3.81) can be established directly from the spectral representation, but we will instead apply the observation at (3.50)–(3.51). Indeed, with $g(i):\equiv\rho_{i}(0)/\pi_{i}$, we have

Thus by (3.51)

Our main use of the extremal characterization is to compare relaxation times of different chains on the same (or essentially the same) state space. Here are three instances. The first is a result we have already exploited in Section 3.5.

Proof. Any function $g$ on the states of the collapsed chain can be extended to the original state space by setting $g=g(a)$ on $A$, and $\mbox{${\cal E}$}(g,g)$ and $\sum_{i}\pi_{i}g(i)$ and $||g||_{2}^{2}$ are unchanged. So consider a $g$ attaining the sup in the extremal characterization of $\tau^{A}_{2}$ and use this as a test function in the extremal characterization of $\tau_{2}$.    

Remark. An extension of Corollary 3.27 will be provided by the contraction principle (Chapter 4 ^††margin: 10/11/94 versionProposition 44).

Proof. Each stationary distribution is uniform, so $\|g\|_{2}^{2}=\|g\|_{2}^{*2}$ while $\mbox{${\cal E}$}^{*}(g,g)\geq\mbox{${\cal E}$}(g,g)$. So the result is immediate from the extremal characterization.    

The next result is a prototype for more complicated “indirect comparison” arguments later. ^††margin: refer to not-net-written Poincare chapter It is convenient to state it in terms of random walk on a weighted graph. Recall (Section 3.2) that a reversible chain specifies a weighted graph with edge-weights $w_{ij}=\pi_{i}p_{ij}$, vertex-weights $w_{i}=\pi_{i}$, and total weight $w=1$.

Proof. For any $g$, by (3.77)

And since $w\|g\|_{2}^{2}=\sum_{i}w_{i}g^{2}(i)$,

So if $g$ has $\pi^{*}$-mean $0$ and $\pi$-mean $b$ then

By considering the $g$ attaining the extremal characterization of $\tau_{2}^{*}$,

This is the lower bound in the lemma, and the upper bound follows by reversing the roles of $w_{e}$ and $w^{*}_{e}$.    

Remarks. Sometimes $\tau_{2}$ is very sensitive to apparently-small changes in the chain. Consider random walk on an unweighted graph. If we add extra edges, but keeping the total number of added edges small relative to the number of original edges, then we might guess that $\tau_{2}$ could not increase or decrease much. But the examples outlined below show that $\tau_{2}$ may in fact change substantially in either direction.

As these examples suggest, comparison arguments are most effective when the stationary distributions coincide. Specializing Lemma 3.29 to this case, and rephrasing in terms of (reversible) chains, gives

Remarks. The hypothesis can be rephrased as ${\bf P}=\delta{\bf P}^{*}+(1-\delta){\bf Q}$, where ${\bf Q}$ is a (maybe not irreducible) reversible transition matrix with stationary distribution $\pi$. When ${\bf Q}={\bf I}$ we have $\tau_{2}=\delta^{-1}\tau^{*}_{2}$, so an interpretation of the lemma is that “combining transitions of ${\bf P}^{*}$ with noise can’t increase mixing time any more than combining transitions with holds”.

Given a subset $A$ of states in a discrete-time chain, let ${\bf P}^{A}$ be ${\bf P}$ restricted to $A^{c}$. Then ${\bf P}^{A}$ will be a substochastic matrix, i.e., the row-sums are at most $1$, and some row-sum is strictly less than $1$. Suppose ${\bf P}^{A}$ is irreducible. As a consequence of the Perron–Frobenius theorem (e.g., [183] Theorem 8.4.4) for the nonnegative matrix ${\bf P}^{A}$, there is a unique $0<\lambda<1$ (specifically, the largest eigenvalue of ${\bf P}^{A}$) such that there is a probability distribution $\alpha$ satisfying

Writing $\alpha_{A}$ and $\lambda_{A}$ to emphasize dependence on $A$, (3.82) implies that under $P_{\alpha_{A}}$ the hitting time $T_{A}$ has geometric distribution

whence

Call $\alpha_{A}$ the quasistationary distribution and $E_{\alpha_{A}}T_{A}$ the quasistationary mean exit time.

Similarly, for a continuous-time chain let ${\bf Q}^{A}$ be ${\bf Q}$ restricted to $A^{c}$. Assuming irreducibility of the substochastic chain with generator ${\bf Q}^{A}$, there is a unique $\lambda\equiv\lambda_{A}>0$ such that there is a probability distribution $\alpha\equiv\alpha_{A}$ (called the quasistationary distribution) satisfying

This implies that under $P_{\alpha_{A}}$ the hitting time $T_{A}$ has exponential distribution

whence the quasistationary mean exit time is

Note that both $\alpha_{A}$ and $E_{\alpha_{A}}T_{A}$ are unaffected by continuization of a discrete-time chain.

The facts above do not depend on reversibility, but invoking now our standing assumption that chains are reversible we will show in remark (c) following Theorem 3.33 that, for continuous-time chains, $\lambda_{A}$ here agrees with the spectral gap $\lambda_{A}$ discussed in Proposition 3.21, and we can also now prove our second extremal characterization.

Proof. As usual, we give the proof in discrete time. The matrix $(s^{A}_{ij}=\pi^{1/2}_{i}p^{A}_{ij}\pi^{-1/2}_{j})$ is symmetric with largest eigenvalue $\lambda_{A}$. Putting $x_{i}=\pi^{1/2}_{i}g(i)$ in the characterization (3.78) gives

Clearly the sup is attained by nonnegative $g$, and though the sums above are technically over $A^{c}$ we can sum over all $I$ by setting $g=0$ on $A$. So

As in the proof of Theorem 3.25 this rearranges to

establishing Theorem 3.33.    

Remarks. (a) These remarks closely parallel the remarks at the end of Section 3.6.3. The sup in Theorem 3.33 is attained by the function $g_{0}$ which is the right eigenvector associated with $\lambda_{A}$, and by reversibility this is

It easily follows from (3.82) that

which explains the name quasistationary distribution for ${\alpha_{A}}$. A related interpretation of ${\alpha_{A}}$ is as the distribution of the Markov chain conditioned on having been in $A^{c}$ for the infinite past. More precisely, one can use Perron–Frobenius theory to prove that

provided $P^{A}$ is aperiodic as well as irreducible.

(b) Relation (3.86) holds in continuous time as well (assuming irreducibility of the chain restricted to $A^{c}$), yielding

Since by Proposition 3.21 the distribution of $T_{A}$ for the stationary chain is CM with spectral gap (say) $\sigma_{A}$, the limit here is $\exp(-\sigma_{A}t)$. Thus $\lambda_{A}=\sigma_{A}$, that is, our two uses of $\lambda_{A}$ refer to the same quantity.

(c) We conclude from remark (b), (3.83), and the final inequality in (3.69) that, ^††margin: This is needed at the bottom of page 27 (9/22/96 version) in Chapter 5. in either continuous or discrete time,

Our fundamental use of quasistationarity is the following.

Proof. As at (3.85) set $g(i)=\alpha_{A}(i)/\pi_{i}$, so

Now $E_{\pi}g(X_{0})=1$, so applying the extremal characterization of relaxation time to $g-1$,

the last equality using (3.88). Since ${\alpha_{A}}$ is a probability distribution on $A^{c}$ we have

and so by Cauchy–Schwarz

Rearranging,

and substituting into (3.89) gives the desired bound.    

Combining Corollary 3.34 with (3.68) and (3.83) gives the result below. ^††margin: DA has deleted discrete-time claim in previous version. It seems true but not worth sweating over.