Proof.
As noted at (3.28), form (3.90) follows
(in either discrete or continuous time)
from form (3.91) with .
To prove (3.91), consider satisfying the specified
boundary conditions.
Inspecting (3.74),
the contribution to involving a fixed state is
|
|
|
(3.92) |
As a function of this is minimized by
|
|
|
(3.93) |
Thus the which minimizes subject to the prescribed boundary
conditions
on must satisfy (3.93) for all ,
and by Chapter 2 ††margin: 9/10/99 versionLemma 27 the unique solution of
these equations
is .
Now apply to this the general expression (3.75):
|
|
|
For the factor equals zero,
and for we have , so only the term
contributes. Thus
|
|
|
|
|
(3.94) |
|
|
|
|
|
|
|
|
|
|
giving (3.91).
The analogous result for two disjoint subsets and is a little
complicated to state.
The argument above shows that
|
|
|
is attained by
and that this satisfies
|
|
|
(3.95) |
We want to interpret the reciprocal of this quantity as a mean time
for the chain to commute from to and back.
Consider the stationary chain
.
We can define what is technically called a “marked point process”
which records the times at which is first visited after a visit to
and vice versa.
Precisely, define taking values in by
|
|
|
So the times when are the times of first return to
after visiting ,
and the times when are the times of first return to
after visiting .
Now is a stationary process.
By considering the time-reversal of ,
we see that for
|
|
|
So (3.95) shows
.
If we define , “the typical time to go from to and
back to ”, to have the conditional distribution of
††margin: (discrete time chain)
given ,
then Kac’s formula for the (non-Markov) stationary process
(see e.g. [133] Theorem 6.3.3)
says that .
So we have proved
3.7.1 Thompson’s principle and leveling networks
Theorem 3.36 was stated in terms of (reversible) Markov chains. Rephrasing in terms of discrete-time random walk on a weighted graph
gives the usual “electrical
network” formulation of the Dirichlet principle stated below,
using (3.77),(3.91) and (3.94).
Recall from Proposition 3.10 that the effective resistance
between
and is, in terms of the random walk,
|
|
|
(3.96) |
Proposition 3.38 (The Dirichlet principle)
Take a weighted graph
and fix a vertex and a subset of vertices not containing .
Then the quantity
is minimized,
over all functions with and on ,
by the function
(where probabilities refer to random walk on the weighted graph),
and the minimum value equals ,
where is the effective resistance (3.96).
There is a dual form of the Dirichlet principle, which following
Doyle and Snell [131] we call
Proposition 3.39 (Thompson’s principle)
Take a weighted graph
and fix a vertex and a subset of vertices not containing .
Let denote a unit flow from to .
Then is minimized,
over all such flows, by the flow [defined at (3.18)] associated with the random walk from
to , and the
minimum value equals the effective resistance appearing in (3.96).
Recall that a flow is required to have whenever ,
and interpret sums as sums over ordered pairs
with .
Proof.
Write
.
By formula (3.25) relating the random walk notions of “flow” and
“potential”, the fact that
is immediate from the corresponding equality in the
Dirichlet principle.
So the issue is to prove that for a unit flow , say, attaining the
minimum of , we have .
To prove this, consider two arbitrary paths and from
to , and let denote the flow
modified by adding flow rates along the edges
and by adding flow rates along the edges .
Then is still a unit flow from to .
So the function
must have derivative zero at ,
and this becomes the condition that
|
|
|
So the sum is the same for all paths from to .
Fixing , the sum must be the same for all paths from to ,
because two paths from to could be extended to paths from
to by appending a common path from to .
It follows that we can define as the sum
over some path from to , and the sum does not depend on
the path chosen. So
††margin: (This is essentially the same argument used in
Section 3.3.2.)
|
|
|
(3.97) |
The fact that is a flow means that, for ,
|
|
|
So is a harmonic function outside , and on . So by
the uniqueness result (Chapter 2 ††margin: 9/10/99 versionLemma 27) we have
that must
be proportional to ,
the minimizing function in Proposition 3.38.
So is proportional to ,
because the relationship (3.97) holds for both,
and then because both are unit
flows.
A remarkable statistical interpretation was discussed in a monograph
of Borre and Meissl [57].
Imagine a finite set of locations such as hilltops.
For each pair of locations with a clear line-of-sight,
measure the elevation difference (height of minus
height of ).
Consider the associated graph [whose edges are such pairs ],
and suppose it is connected.
Take one location as a benchmark “height ”.
If our measurements were exact we could determine the height of
location by adding the ’s along a path from to ,
and the sum would not depend on the path chosen.
But suppose our measurements contain random errors.
Precisely, suppose equals the true height difference
plus an error which has mean and variance
and is independent for different measurements.
Then it seems natural to estimate the height of by taking
some average over paths from to ,
and it turns out that the “best” way to average is to use the
random walk from to and average (over realizations of the
walk) the net height climbed by the walk.
In mathematical terms, the problem is to choose weights ,
not depending on the function , such that
|
|
|
has and minimal variance.
It is not hard to see that the former “unbiased” property holds iff
is a unit flow from to .
Then
|
|
|
and Proposition 3.39 says this is minimized when we use the
flow from to obtained from the random walk on the weighted graph.
But then
|
|
|
the expectation referring to the random walk.
3.7.2 Hitting times and Thompson’s principle
Using the commute interpretation of resistance (Corollary 3.11)
to translate Thompson’s principle into an assertion about mean commute times
gives the following.
Corollary 3.40
For random walk on a weighted graph and distinct vertices and ,
|
|
|
and the is attained by the flow associated with the
random walk.
Comparing with Theorem 3.36 we have two different extremal
characterizations of mean commute times, as a sup over
potential functions and as an inf over flows.
In practice this “flow” form is less easy to use than the “potential” form,
because writing down a flow is harder
than writing down a function .
But, when we can write down and calculate with some plausible flow,
it gives upper bounds on mean commute times.
One-sided mean hitting times don’t have simple extremal
characterizations of the same kind,
with the exception of hitting times from stationarity.
To state the result, we need two definitions. First,
given a probability distribution on vertices, a
unit flow from to
is a flow satisfying
|
|
|
(3.98) |
more generally, a unit flow from a set to is
defined to satisfy
|
|
|
Now fix a state and define the special flow
by
|
|
|
(3.99) |
with the usual convention in the periodic case.
So is the mean excess of transitions compared to
transitions ,
for the chain started at and run forever.
This is a unit flow from to , in the above sense.
Equation (6) (the definition of ) in Chapter 2 ††margin: 9/10/99 versionand
reversibility give the first equality, and Chapter 2
††margin: 9/10/99 versionLemma 12
gives the last equality, in
|
|
|
|
|
(3.100) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(3.101) |
switching to “weighted graphs” notation.
Note also that the first-step recurrence for the function
is
|
|
|
(3.102) |
Proposition 3.41
For random walk on a weighted graph
and a subset of vertices,
|
|
|
|
|
|
|
|
|
|
When is a singleton , the minimizing flow
is the flow defined above,
and the maximizing function is
.
For general
the maximizing function is
.
††margin: Added the final observation about general
Proof.
Suppose first that .
We start by showing that the extremizing flow, say,
is the asserted .
By considering adding to a flow of size along a directed
cycle, and copying the argument for (3.97) in the proof of Proposition
3.39,
there must exist a function such that
|
|
|
(3.103) |
The fact that is a unit flow from to says that
|
|
|
which implies
|
|
|
Since and ,
this becomes
|
|
|
Now these equations have a unique solution , up to an
additive constant, because the difference between two solutions
is a harmonic function. (Recall Chapter 2 ††margin: 9/10/99 versionCorollary 28.)
On the other hand, a solution is
,
by considering the first-step recurrence for .
So by (3.103)
,
and so by (3.101).
Now consider the function which minimizes
under the constraints and .
By introducing a Lagrange multiplier we may consider
as minimizing subject to .
Repeating the argument at (3.92), the minimizing
satisfies
|
|
|
Rearranging, and introducing a term to cover
the case , we have
|
|
|
for some .
Because we have
|
|
|
allowing us to rewrite the equation as
|
|
|
By the familiar “harmonic function” argument this has a unique
solution, and (3.102) shows the solution is
.
Then the constraint gives .
Next consider the relationship between the flow and the function
.
We have
††margin: Chapter 2 reference in following display is
to 9/10/99 version.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Thus it is enough to prove
|
|
|
(3.104) |
and it will then follow that
|
|
|
To prove (3.104),
introduce a parameter
(which will later go to )
and a new vertex and edge-weights .
Writing superscripts to refer to this new graph and its
random walk, the equation becomes
and Corollary 3.40 says
|
|
|
(3.105) |
where is the special unit flow from to associated with
the new graph (which has vertex set ).
We want to interpret the ingredients to (3.105) in terms of the original
graph.
Clearly .
The new walk has chance to jump to from each
other vertex, so .
Starting from , after one step the new walk has the stationary
distribution on the original graph, and it follows easily that
.
We can regard the new walk up to time as the old walk sent to
at a random time with Geometric() distribution,
so for and the flow is the
expected net number
of transitions by the old walk up to time .
From the spectral representation it follows easily that . Similarly, for we have ; noting that , the total contribution of such terms to the double sum in (3.105) is
|
|
|
|
|
|
|
|
|
|
So (3.105) becomes
|
|
|
Subtracting from both sides and letting gives the
desired (3.104).
This concludes the proof for the case , once we use
the mean hitting time formula to verify
|
|
|
Finally, the extension to general is an exercise in use of the
chain, say , in
which the set is collapsed to a single state . Recall
Chapter 2
††margin: 9/10/99 versionSection 7.3. In particular,
|
|
|
We now sketch the extension.
First, . Then the natural one-to-one correspondence between
functions
on with
on and and
functions on
with and gives a
trivial proof of
|
|
|
It
remains to show that
|
|
|
(3.106) |
|
|
|
|
|
where
|
|
|
Indeed, given a unit flow from to , define
as
if and as if and . One can
check that is a unit flow from to (the key observation
being that ) and, using the
Cauchy–Schwarz
inequality, that . Conversely,
given a unit
flow from to , define as
if ,
as if and , and as
if . One can check that is a unit flow
from to and
that . We have thus
established (3.106),
completing the proof.
Corollary 3.42
For
chains with transition matrices and the
same stationary distribution ,
|
|
|
Proof.
Plug the minimizing flow
for the -chain into Proposition 3.41 for the -chain to
get the second inequality. The first follows by reversing the roles of
and .