Page 127 - A First Course In Stochastic Models

THEORETICAL CONSIDERATIONS 119

3.5 THEORETICAL CONSIDERATIONS

In this section we give some background material. First the state classification of
Markov chains is discussed. Next we prove the results that were used earlier in the
analysis of the long-run behaviour of Markov chains.

3.5.1 State Classification

The concepts of a transient state and a recurrent state were introduced in Section 3.2
and the following lemma was proved for the Markov chain {X n }.

∞ (n)
Lemma 3.5.1 A state i is transient only if n=1 p ii < ∞ and a state i is recur-

∞ (n)
rent only if n=1 p ii = ∞.
To analyse the transient states and recurrent states in more detail, we need the
concept of accessibility.

(n)
Definition 3.5.1 State j is said to be accessible from state i if p > 0 for some
ij
n ≥ 0. Two states i and j are said to communicate if j is accessible from i and i is
accessible from j.
(0)
Since p = 1 by definition, we always have that any state i is accessible
ii
from itself. It is convenient to write i → j if state j is accessible from state i.
The concept of communication enables us to split up the state space in a natural
way into disjoint closed sets of recurrent states and a set of transient states (for
the finite-state Markov chain an algorithm is given at the end of this subsection).
Recall that a non-empty set C of states is called a closed set if p ij = 0 for i ∈ C
and j /∈ C. That is, the Markov chain cannot leave the set C once it is in the set
C. By definition the state space I is always a closed set. A closed set C is called
irreducible when the set C contains no smaller closed set.

Lemma 3.5.2 Let C be a closed set of states. The set C is irreducible if and only
if all states in C communicate with each other.

Proof For each i ∈ C, define the set S(i) by

S(i) = {j | i → j}.
The set S(i) is not empty since i → i. Since the set C is closed, we have S(i) ⊆ C.
First suppose that C is irreducible. The ‘only if’ part of the lemma then follows by
showing that S(i) = C for all i. To do so, it suffices to show that S(i) is closed.
Assume now to the contrary that S(i) is not closed. Then there is a state r ∈ S(i)
(n)
and a state s /∈ S(i) with p rs > 0. Since r ∈ S(i) we have p > 0 for some
ir
(n+1) (n) (n+1)
n ≥ 0 and so p ≥ p p rs > 0; use relation (3.2.2). The inequality p > 0
is ir is
contradicts the fact that s /∈ S(i). This completes the proof of the ‘only if’ part of