Page 104 - A First Course In Stochastic Models

96 DISCRETE-TIME MARKOV CHAINS

3.3 THE EQUILIBRIUM PROBABILITIES

This section deals with the long-run behaviour of the Markov chain {X n }. In partic-
ular, we discuss the characterization of the equilibrium distribution of the process
and a formula for the long-run average cost per time unit when a cost structure is
imposed on the Markov chain. In this section the emphasis is on giving insights
into the long-run behaviour of the Markov chain. Most of the proofs are deferred
to Section 3.5.

3.3.1 Preliminaries
A natural question for a Markov chain {X n } is whether the n-step probabilities
(n)
p always have a limit as n → ∞. The answer to this question is negative
ij
as shown by the following counterexample. Consider a Markov chain with state
space I = {1, 2} and one-step transition probabilities p ij with p 12 = p 21 = 1 and
(n)
p 11 = p 22 = 0. In this example the n-step transition probabilities p alternate
ij
between 0 and 1 for n = 1, 2, . . . and hence have no limit as n → ∞. The reason
is the periodicity in this Markov chain example. In our treatment of Markov chains
we will not give a detailed discussion on the relation between the limiting behaviour
(n)
of the p and the issue of periodicity. The reason is that our treatment of Markov
ij
chains emphasizes the study of long-run averages. As explained in Section 2.2,
the long-run average behaviour of a stochastic process is in general much easier to
handle than its limiting behaviour. More importantly, long-run averages are usually
required in the analysis of practical applications. In the next theorem we prove that
for each Markov chain {X n } the Cesaro limit of the n-step transition probabilities
always exists.

Theorem 3.3.1 For all i, j ∈ I, lim n→∞ (1/n)
n p (k) always exists. For any
k=1 ij
j ∈ I,
n 1
1 (k) if state j is recurrent,
lim p = µ jj (3.3.1)
n→∞ n jj 0 if state j is transient,
k=1
where µ jj denotes the mean recurrence time from state j to itself. Also,
n n
1 (k) 1 (k)
lim p = f ij lim p (3.3.2)
n→∞ n ij n→∞ n jj
k=1 k=1
for any i, j ∈ I, where f ij is the probability that the process ever makes a transition
into state j when the process starts in state i.
(n)
Proof For a transient state j we have by Lemma 3.2.3 that lim n→∞ p = 0
ij
for all i ∈ I. Using the well-known result that the Cesaro limit is equal to the
ordinary limit whenever the latter limit exists, the results (3.3.1) and (3.3.2) follow