Page 129 - A First Course In Stochastic Models

THEORETICAL CONSIDERATIONS 121

would be a positive probability of never returning to state r, contradicting the fact
(v)
that state r is recurrent. Hence there is a positive integer v such that p sr > 0. For
any integer k,
(v+k+1) (v) (k)
p ≥ p p p rs ,
ss sr rr

∞ (n) (v)
∞ (k)
implying that n=1 p ss ≥ p sr p rs k=1 p rr . Since state r is recurrent, it now
follows from Lemma 3.5.1 that state s is recurrent. Hence s ∈ R.
(b) We first observe that the following two properties hold:
(P1) If state i communicates with state j and state i communicates with state k,
then the states j and k communicate.
(P2) If state j is recurrent and state k is accessible from state j, then state j is
accessible from state k.
The first property is obvious. The second property was in fact proved in part (a).
Define now for each i ∈ R the set C(i) as the set of all states j that communicate
with state i. The set C(i) is not empty since i communicates with itself by definition.
Further, by part (a), C(i) ⊆ R. To prove that the set C(i) is closed, let j ∈ C(i)
and let k be any state with p jk > 0. Then we must verify that i → k and k → i.
From i → j and j → k it follows that i → k. Since j → i, the relation k → i
follows when we can verify that k → j. The relation k → j follows directly
from property P2, since j is recurrent by the proof of part (a) of Theorem 3.5.3.
Moreover, the foregoing arguments show that any two states in C(i) communicate.
It now follows from Lemma 3.5.2 that C(i) is an irreducible set. Also, using the
properties P1 and P2, it is readily verified that C(i) = C(j) if i and j communicate
and that C(i) ∩ C(j) is empty otherwise. This completes the proof of part (b).
Definition 3.5.2 Let i be a recurrent state. The period of state i is said to be d if
(n)
d is the greatest common divisor of the indices n ≥ 1 for which p > 0. A state i
ii
with period d = 1 is said to be aperiodic.
Lemma 3.5.5 (a) Let C be an irreducible set consisting of recurrent states. Then
all states in C have the same period.
(n)
(b) If state i is aperiodic, then there is an integer n 0 such that p > 0 for all
ii
n ≥ n 0 .
Proof (a) Denote by d(k) the period of state k ∈ C. Choose i, j ∈ C with j = i.
By Lemma 3.5.2 we have i → j and j → i. Hence there are integers v, w ≥ 1
(v) (w) (n)
such that p > 0 and p > 0. Let n be any positive integer with p > 0. Then
ij ji jj
(n+v+w)
the first inequality in (3.5.1) implies that p > 0 and so n+v+w is divisible
ii
(n)
by d(i). Thus we find that n is divisible by d(i) whenever p > 0. This implies
jj
that d(i) ≤ d(j). For reasons of symmetry, d(j) ≤ d(i). Hence d(i) = d(j) which
verifies part (a).
(n)
(b) Let A = {n ≥ 1 | p > 0}. The index set A is closed in the sense that
ii
(n+m) (n) (m)
n + m ∈ A when n ∈ A and m ∈ A. This follows from p ≥ p p . Since
ii ii ii