3.4 The spectral representation
Use the transition matrix to define
|
|
|
From definition (3.1), is a symmetric matrix.
So we can apply the elementary diagonalization theorem.
The authors find it helpful to distinguish between the state space
, of size say, and the index set of integers
,
the point being that the state space may have a lot of extra structure,
whereas the index set has no obvious structure.
The spectral theorem ([183] Theorem 4.1.5) gives a representation
|
|
|
where is an orthonormal matrix,
and
is a diagonal real matrix.
We can write the diagonal entries of as ,
and arrange them in decreasing order. Then
|
|
|
(3.30) |
The classical fact that follows easily from the
fact that the entries of are bounded as
by (3.31) below.
These ’s are the eigenvalues of ,
as well as of .
That is, the solutions with
of
|
|
|
are exactly the pairs
|
|
|
for , where is arbitrary.
And the solutions of
|
|
|
are exactly the pairs
|
|
|
Note that an eigenvector of corresponding to the
eigenvalue is
|
|
|
Uniqueness of the stationary distribution now implies .
Now consider matrix powers.
We have
|
|
|
and
|
|
|
(3.31) |
so
|
|
|
(3.32) |
This is the spectral representation formula.
In continuous time, the analogous formula is
|
|
|
(3.33) |
As before, is an orthonormal matrix
and ,
and now the ’s are the eigenvalues of .
In the continuous-time setting, the eigenvalues satisfy
|
|
|
(3.34) |
Rather than give the general proof, let us consider the effect
of continuizing the discrete-time chain (3.32).
The continuized chain can be represented as
where has distribution,
so by conditioning on ,
|
|
|
|
|
|
|
|
|
|
So when we compare the spectral representations (3.32),(3.33)
for a discrete-time chain and its continuization,
the orthonormal matrices are identical, and the eigenvalues are related by
|
|
|
(3.35) |
superscripts (c) and (d) indicating continuous or discrete time.
In particular, this relation holds for the basic
discrete and continuous time random walks on a graph.
Let us point out some interesting simple consequences of the spectral representation.
For these purposes continuous time is simpler.
First,
|
|
|
(3.36) |
where and where “typically” .
(A precise statement is this: there exists such that
|
|
|
(3.37) |
by considering such that .)
Thus has the interpretation of
“asymptotic rate of convergence to the stationary distribution”.
The authors find it simpler to interpret parameters measuring “time”
rather than “”, and so prefer to
work with the
relaxation time
defined by
|
|
|
|
|
(3.38) |
|
|
|
|
|
(3.39) |
Note that by (3.35) the value of is unchanged by
continuizing a discrete-time chain.
Still in continuous time, the spectral representation gives
|
|
|
(3.40) |
so the right side is decreasing with ,
and in fact is completely monotone, a subject pursued in
Section 3.5.
Thus defined in ††margin: 9/10/99 versionChapter 2 Section 2.3
satisfies
|
|
|
|
|
(3.41) |
|
|
|
|
|
Using the orthonormal property of ,
|
|
|
Applying Corollary 13 of ††margin: 9/10/99 versionChapter 2, we
obtain a fundamental result relating average hitting times to
eigenvalues.
Proposition 3.13 (The eigentime identity)
For each ,
|
|
|
|
|
|
|
|
|
|
[The discrete-time version follows from (3.35).]
Proposition 3.13 expands upon the random target lemma,
which said that (even for non-reversible chains)
does not depend on .
3.4.1 Mean hitting times and reversible chains
In ††margin: 9/10/99 versionChapter 2 Section 2.2 we listed identities for
general chains such as the mean hitting time formulas
|
|
|
There are a number of more complicated identities for general chains
in which one side becomes zero for any reversible chain
(by the symmetry property )
and which therefore simplify to give identities for reversible chains.
We have already seen one example, the cyclic tour lemma, and
the following result may be considered
an extension of that lemma. [Indeed, sum the following equation over
successive pairs along a cycle to recapture the cyclic tour lemma.]
Corollary 3.14
.
This identity follows immediately from the mean hitting time
formulas and the symmetry property.
Note the following interpretation of the corollary.
Define an ordering
on the states by
|
|
|
Then Corollary 3.14 implies
|
|
|
Warning.
Corollary 3.14 does not imply
|
|
|
|
|
|
Here
††margin: I haven’t tried to find counterexamples with more than three states.
is a counterexample. Choose arbitrarily and let
|
|
|
We invite the reader to perform the computations necessary to verify
that is reversible with and
|
|
|
so that . Thus is
minimized uniquely by , while is
attained only by the
pairs and .
As a second instance of what reversibility implies,
note,
from (3.33) and the definition of , that
|
|
|
This implies
|
|
|
(3.42) |
Note that a symmetric positive semidefinite
matrix has
the property .
This gives
|
|
|
(3.43) |
which enables us to upper-bound mean hitting times from arbitrary
starts in terms of mean hitting times from stationary starts.
Lemma 3.15
.
Proof.
Using (3.43),
|
|
|
and so
|
|
|
So the mean hitting time formula gives the two equalities in
|
|
|