Page 130 - A First Course In Stochastic Models

122 DISCRETE-TIME MARKOV CHAINS

state i is aperiodic, there are integers a ∈ A and b ∈ A whose greatest common
divisor is equal to 1. An elementary result in number theory states that there exist
integers r and s such that gcd (a, b) = ar + bs. The integers r and s are not
necessarily non-negative. Let p and q be any positive integers such that both p and
q are larger than a×max(|r|, |s|). Take m = pa+qb. Since m+a = (p+1)a+qb,
part (b) of the lemma follows by proving that m + k ∈ A for k = 0, . . . , a − 1.
(n)
We then have p > 0 for all n ≥ m. Noting that ar + bs = 1, it follows that
ii
m + k = pa + qb + k(ar + bs) = (p + kr)a + (q + ks)b. The integers p + kr
and q + ks are positive. Hence, by the closedness of A, the integers (p + kr)a and
(q + ks)b belong to A and so the integer m + k ∈ A for any k = 0, . . . , a − 1.

Finite state space
There are a number of basic results that hold for finite-state Markov chains but not
for Markov chains with infinitely many states. In an infinite-state Markov chain
it may happen that there is no recurrent state, as is demonstrated by the Markov
chain example with state space I = {1, 2, . . . } and one-step transition probabilities
with p i,i+1 = 1 for all i ≥ 1. In this example all states are transient. The next
lemma shows that a finite-state Markov chain always has recurrent states.

Lemma 3.5.6 Each finite closed set of states has at least one recurrent state.
Proof Let C be a closed set of states. Then, for any i ∈ C,

(n)
p = 1, n = 1, 2, . . . . (3.5.2)
ij
j∈C
Assume now that all states j ∈ C are transient. In Lemma 3.2.3 it was shown that
(n)
lim n→∞ p = 0 for all i ∈ I if state j is transient. Let n → ∞ in (3.5.2). By the
ij
finiteness of C, it is permissible to interchange the order of limit and summation.
Hence we obtain the contradiction 0 = 1 when all states in C are transient. This
ends the proof.

In most applications the Markov chain has no two disjoint closed sets (usually
there is a state that is accessible from any other state). The next theorem summarizes
a number of useful results for finite-state Markov chains having no two disjoint
closed sets.

Theorem 3.5.7 Let {X n } be a finite-state Markov chain. Suppose that the Markov
chain has no two disjoint closed sets. Denote by R the set of recurrent states. Then

(a) f ij = 1 for all i ∈ I and j ∈ R.
(b) µ ij < ∞ for all i ∈ I and j ∈ R, where the mean first-passage times µ ij are

(n)
∞
defined by µ ij = n=1 nf ij .