Page 139 - A First Course In Stochastic Models

THEORETICAL CONSIDERATIONS 131

Proof Assume first that the initial state of the process is the regeneration state r
from Assumptions 3.3.1 and 3.3.2. The Markov chain can be seen as a regenerative
process with the epochs at which the process visits state r as regeneration epochs.
Define a cycle as the time elapsed between two successive visits to state r. The
expected cycle length equals the mean recurrence time µ rr and is finite. By the
renewal-reward theorem from Chapter 2,

n
1 E(reward earned during one cycle)
lim f (X k ) =
n→∞ n E(length of one cycle)
k=1
with probability 1. Lemma 3.5.10 states that E (number of visits to state j in one
cycle) = π j /π r for any recurrent state j. This relation is also valid for a transient
state j, since a transient state is not accessible from a recurrent state and π j = 0
for j transient. Hence

π j
E(reward earned during one cycle) = f (j) .
π r
j∈I
Since E(length of one cycle) = µ rr = 1/π r by (3.5.5), the assertion of the theorem
is now proved when X 0 = r. Take next any initial state X 0 = i. As in the proof
of Lemma 3.5.10, let ω = (i 0 , i 1 , i 2 , . . . ) be any realization of the Markov chain
with i 0 = i and let i k denote the realized state at the kth state transition. Since
f ir = 1, we have for almost all ω that there is a finite integer t = t(ω) such that
i t = r. Hence
n t(ω) n
1 1 1
f (X k (ω)) = f (X k (ω)) + f (X k (ω)).
n n n
k=1 k=1 k=t(ω)+1
Letting n → ∞, it follows from part (b) of Assumption 3.3.2 that the first term
on the right-hand side of the equation tends to zero, while by the above proof the
second term converges to
f (j)π j . This completes the proof.
j∈I

Markov’s proof and exponential convergence
It is interesting to examine the original proof of Markov (1906) for the existence
of a limiting distribution in a finite-state Markov chain. The proof is not just of
historical interest and the ideas it uses are still very much alive. The proof also
establishes the rate of convergence to the limiting distribution. An aperiodic finite-
state Markov chain with no two disjoint closed sets is assumed. The Markov chain
is said to be aperiodic when the period of the recurrent states is equal to 1; see
Lemma 3.5.5.

Theorem 3.5.12 Let {X n } be a finite-state Markov chain with no two disjoint
closed sets. Suppose that the Markov chain is aperiodic. Then there exists a proba-
bility distribution {π j , j ∈ I} and numbers α > 0 and 0 < β < 1 such that for all