Page 185 - Applied Probability

9. Descent Graph Methods
170
9.2 Review of Discrete-Time Markov Chains
For the sake of simplicity, we will only consider chains with a finite state
space [6, 11]. The movement of such a chain from epoch (or generation) to
epoch is governed by its transition probability matrix P =(p ij ). If Z n
denotes the state of the chain at epoch n, then p ij =Pr(Z n = j | Z n−1 = i).
As a consequence, every entry of P satisfies p ij ≥ 0, and every row of P

satisfies p ij = 1. Implicit in the definition of p ij is the fact that the
j
future of the chain is determined by its present without regard to its past.
This Markovian property is expressed formally by the equation
Pr(Z n = i n | Z n−1 = i n−1 ,...,Z 0 = i 0 )=Pr(Z n = i n | Z n−1 = i n−1).
(n)
The n-step transition probability p =Pr(Z n = j | Z 0 = i)isgiven
ij
n
by the entry in row i and column j of the matrix power P . This follows
because the decomposition
(n)
p ij = ··· p ii 1 ··· p i n−1 j
i 1 i n−1
over all paths i → i 1 →· · · i n−1 → j corresponds to matrix multipli-
cation. A question of fundamental theoretical importance is whether the
n
matrix powers P converge. If the chain eventually forgets its starting state,
then the limit should have identical rows. Denoting the common limiting
row by π, we deduce that π = πP from the calculation
π
 
. n+1
.
 .  = lim P
n→∞
π

= lim P n P
n→∞
π
 
.
=  .  P.
.
π
Any probability distribution π on the states of the chain satisfying the
condition π = πP is termed an equilibrium or stationary distribution
of the chain. For finite-state chains, equilibrium distributions always exist
[6, 11]. The real issue is uniqueness.
Mathematicians have attacked the uniqueness problem by defining ap-
propriate ergodic conditions. For a finite-state chain, two ergodic assump-
tions are invoked. The first is aperiodicity; this means that the greatest
(n)
common divisor of the set {n ≥ 1: p ii > 0} is 1 for every state i. Aperiod-
icity trivially holds when p ii > 0 for all i. The second ergodic assumption
is irreducibility; this means that for every pair of states (i, j) there exists