A.3 Time-Homogeneous Markov Chains
The time-homogeneous Markov chain X is completely specified by its initial proba-
bility distribution, q0, and state transition matrix, P. The probability distribution of
Xk,k 1 is given by
The following definitions and theorems concern the asymptotic behavior of the chain and
some conditions on the state space which make the asymptotic behavior independent of
qo. In the following, let the i,j e E element of P be denoted by p')(i,j).
Definition A6: A subset Eo of the state space E of the Markov chain X is called closed if
Vi EO Vj e E Eo it follows that p(i,j) = 0. If the closed set Eo contains the single state
i, so that p(i,i) = 1, then the state i is called an absorbing state.
Definition A7: A Markov chain is called irreducible if there exists no nonempty closed
subset of its state space E other than E itself.
Definition A8: The states i andj are said to intercommunicate if
3ki, kj E K 3 p)(i,j) > 0 and pn(j, i) > 0.
Theorem Al: A Markov chain is irreducible if and only if all pairs of states intercommu-
nicate.
Definition A9: State i e E of the Markov chain X has period d if the following two condi-
tions hold:
(1) pk)(i,i) = 0 unless k = md for some positive integer m and