Page 186 - Applied Probability

9. Descent Graph Methods
171
(n ij )
a positive integer n ij such that p
ij
reachable from every other state. Said yet another way, all states commu-
nicate. For an irreducible chain, Problem 5 states that the integer n ij can
be chosen independently of the particular pair (i, j) if and only if the chain
is also aperiodic. Thus, we can merge the two ergodic assumptions into the
has all entries positive. Under this
single assumption that some power P n > 0. In other words, every state is
single ergodic condition, a unique equilibrium distribution π exists with all
entries positive.
Equally important is the ergodic theorem [6, 11]. This theorem permits
one to run a chain and approximate theoretical means by sample means.
More precisely, let f(z) be some function defined on the states of an ergodic
1 n−1
chain. Then lim n→∞ f(Z i ) exists and equals the theoretical mean
n i=0

E π [f(Z)] = π z f(z)
z
of f(Z) under the equilibrium distribution π. This result generalizes the
law of large numbers for independent sampling.
The equilibrium condition π = πP can be restated as the system of
equations

π j = π i p ij (9.1)
i
for all j. In many Markov chain models, the stronger condition
π j p ji = π i p ij (9.2)
holds for all pairs (i, j). If this is the case, then the probability distribution
π is said to satisfy detailed balance. Summing equation (9.2) over i yields
the equilibrium condition (9.1). An irreducible Markov chain with equilib-
rium distribution π satisfying detailed balance is said to be reversible.
Irreducibility is imposed to guarantee that all entries of π are positive.
If i 1,...,i m is any sequence of states in a reversible chain, then detailed
balance implies

p p
π i 1 i 1 i 2 = π i 2 i 2 i 1
p p
π i 2 i 2 i 3 = π i 3 i 3 i 2
.
.
.
p p
π i m−1 i m−1 i m = π i m i m i m−1
p p .
π i m i m i 1 = π i 1 i 1 i m
Multiplying these equations together and canceling the common positive
from both sides of the resulting equality gives Kolmo-
factor π i 1 ··· π i m
gorov’s circulation criterion [15]
p p p p . (9.3)
p i 1 i 2 i 2 i 3 ··· p i m−1 i m i m i 1 = p i 1 i m i m i m−1 ··· p i 3 i 2 i 2 i 1