Page 128 - A First Course In Stochastic Models

120 DISCRETE-TIME MARKOV CHAINS

the lemma. To prove the other part, assume to the contrary that C is not irreducible.
Then there is a closed set S ⊆ C with S = C. Choose i ∈ S and let the set S(i) be
as above. Since S is closed, we have S(i) ⊆ S. Hence S(i) = C, which contradicts
the assumption that all states in C communicate.

We are now able to prove the following interesting theorem.

Theorem 3.5.3 (a) Let C be an irreducible set of states. Then either all states in
C are recurrent or all states in C are transient.
(b) Let C be an irreducible set consisting of recurrent states. Then f ij = 1 for all
i, j ∈ C. Moreover, either µ jj < ∞ for all j ∈ C or µ jj = ∞ for all j ∈ C.

(n)

Proof (a) By Lemma 3.5.1, state i is transient if and only if ∞ p < ∞.
n=1 ii
Choose now i, j ∈ C with j = i. By Lemma 3.5.2 we have that the states i and j
(v)
communicate. Hence there are integers v ≥ 1 and w ≥ 1 such that p > 0 and
ij
(w)
p > 0. Next observe that for any n ≥ 0,
ji
(n+v+w) (v) (n) (w) (n+v+w) (w) (n) (v)
p ≥ p p p and p ≥ p p p . (3.5.1)
ii ij jj ji jj ji ii ij
These inequalities imply that
∞ p (n) < ∞ if and only if
∞ p ii (n) < ∞. This
n=1
n=1
jj
proves part (a). In fact the proof shows that i → j and j → i implies that both
states i and j are recurrent or that both states i and j are transient.
(b) Since the states of C are recurrent, we have by definition that f ii = 1 for all
i ∈ C. Choose now i, j ∈ C with j = i. By Lemma 3.5.2 j → i. Hence there is
(m)
an integer m ≥ 1 with p > 0. Let r be the smallest integer m ≥ 1 for which
ji
(m)
p > 0. Then
ji
(r)
1 − f jj = P {X n = j for all n ≥ 1 | X 0 = j} ≥ p (1 − f ij ).
ji
Since f jj = 1, we get from this inequality that f ij = 1. The inequalities in (3.5.1)
(k)
imply that the sequence {p , k ≥ 1} has a positive Cesaro limit if and only if the
ii
(k)
sequence {p , k ≥ 1} has a positive Cesaro limit. It now follows from (3.3.1) in
jj
Theorem 3.3.1 that µ jj < ∞ if and only if µ ii < ∞.
Theorem 3.5.4 Let R be the set of recurrent states of the Markov chain. Suppose
that the set R is not empty. Then
(a) the set R is a closed set,
(b) the set R can be uniquely split into disjoint irreducible subsets R 1 , R 2 , . . .
(called recurrent subclasses).
Proof (a) Choose any state r ∈ R. Let s be any state such that p rs > 0. The set
R is closed if we can show that s ∈ R. Since state r is recurrent and state s is
accessible from state r, state r must also be accessible from state s. If not, there