Stochastic Processes and Time Series

Module 5
Markov Chains - V
Dr. Alok Goswami, Professor, Indian Statistical Institute, Kolkata

1 Identifying the Decomposition

We have seen the following decomposition of the state space of any MC:
S = ST ∪ C1 ∪ C2 · · · ,
where C1 , C2 , . . . are the disjoint equivalence classes, under the equivalence relation , partitioning
the set SR of recurrents states. We have also seen that if we can identify this decomposition, it will
help us get a clearer picture of the evolution of the chain.
Recall that this decomposition is completely based on the quantities ρxy , x, y ∈ S, which, in turn,
are completely determined by the transition probabilities pxy , x, y ∈ S of the MC (and, in no way,
on the initial distribution).
So, in principle, given the transition probability matrix P for a chain, we should be able to get the
decomposition.
But, in practice, it is not at all easy (in fact, may often be almost impossible!) to get the decom-
position by really computing the ρxy .

To clarify this point, how do we actually go about computing the various ρxy from the transition
probabilties?
The simplest idea that may come to mind is to observe that ρxy = 1 − Px (Ty = ∞) = 1 −
limn Px (Ty > n).
So, we could try compute Px (Ty > n) for every n, using the transition probabilities. But, the
formula for Px (Ty > n) in terms of the transition probabilities is :
X
Px (Ty > n) = px,x1 px1 ,x2 · · · pxn−1 ,xn ,
P
where the sum is over all x1 , x2 , . . . , xn , different from y.
This is clearly quite complicated and it is highly unlikely that we would be able to compute these
for every n, except possibly in some very simple situations.
However, there is a way to get around this. In particular, when the state space is finite, there is a
simple way to identify not only the recurrent and transient states, but also the full decomposition,
without doing any computations whatsoever!!

We start with a definition.

Definition 1. A subset C ⊂ S is called a closed, irreducible class if

• pxy = 0 for every x ∈ C and y ∈

/C

1
 • no proper subset of C has the above property.

The first condition simply means that the C ×C submatrix of P, namely, ((pxy ))x,y∈C is a transition
matrix in itself and the second condition says that no proper submatrix of this has the property.
(n)
Exercise: The first condition implies that pxy = 0 ∀ x ∈ C, y ∈/ C for all n ≥ 1. In particular,
x ∈ C, x y⇒y∈C
The second condition means that no proper subset of C has this property. In particular, x y for
all x, y ∈ C.

Note that if C ⊂ S is any closed, irreducible class in S, then we can restrict the original process to
a reduced state space C and that becomes a MC, in its own right, with state space C and transition
matrix PC = ((pxy ))x,y∈C .
This MC (on the reduced state space C) will have the special property that x y for every
x, y ∈ C.

Definition 2. A MC with the property that x y for every pair x, y of its states, is called an
irreducible Markov Chain.

Thus, for each closed irreducible class C ⊂ S, the chain on the reduced state space C becomes an
irreducible MC.

Here is an useful fact (and can be seen as easy consequence of what we have already done) :
(a) For an irreducible MC, either all states are recurrent or all states are transient. (Accordingly,
the chain itself is called a “recurrent MC” or a “transient MC”.)
(b) For an irredducible MC with a finite state space, all states are recurrent. (That is, any irre-
ducible finite state MC is a recurrent chain.)
Suppose by examining the S × S transition matrix P (but without doing any computation!), we
can identify such subsets C ⊂ S which are closed irreducible classes, that is,

• the sub-matrix of P restricted to each such C is itself a transition matrix, and,

• these are the “smallest” such in the sense that none of the Cs can be reduced any further to
yield a submatrix which is a transition matrix

We then know that the original chain, when restricted to any such C, is an irreducible MC and
therefore, for each such C, either all states in C are recurrent or all are transient.
But even this uncertainty disappears in case we have a finite C.
All states in a finite C must be recurrent! This becomes particularly useful when the original chain
has a finite state space.

2 Finite State Space MC

To understand how all these work wonderfully for a finite state space MC, let us start with an
example:

2
Example 1: Consider a MC with state space S = {1, 2, . . . , 6} and transition matrix
 1 3 
4 4 0 0 0 0
 2 1
 3 3 0 0 0 0 

 1
 4 0 14 38 18 0 

P = 
1

1 
 0 0 0 2 0 2 
 0 13 16 16 13 0 
 

0 0 0 25 0 35
A quick scrutiny of the matrix P (but no computations!) tells us that C1 = {1, 2} and C2 = {4, 6}
are two closed irreducible classes and these are the only ones.
By above proposition, we conclude: 1, 2, 4, 6 are recurrent states.

Example...contd What about the states 3 and 5? They are both transient. Why?
See that 3 1 (in fact, p13 > 0!), but 1 ∈ C1 and so 1 doesn’t lead to any state outside C1 ! This
would be impossible if 3 were recurrent. The argument is similar for the other state 5.
What we saw in the above example is, in fact, true for any finite state space MC. Here is the general
algorithm:

• Given the S × S transiition matrix P of the chain, try to identify all the “minimal” subsets
C ⊂ S such that the C × C sub-matrix of P , corresponding to states in C, is a transition
matrix (but no proper sub-matrix is). For a finite state space MC, there will always be at
least one such C ⊂ S − why?

• Then each such C is a finite closed irreducible class and therefore all the states belonging to
such Cs are recurrent.

• States, if any, not belonging to any such C are all transient.

Let us just see one more example.

Example 2: The state space is S = {1, 2,
3, 4} and the transition matrix is
1 1 1 
4 2 0 4
 1 0 1 1 
P =  1 1 3 13 
 3 
 3 2 0 6 
1 1 1
3 3 3 0
It is easy to see that here x y for every x, y ∈ S.
Just see that 1 2 3 4 1.

What that means is that there is no proper subset of S which is closed and irreducible.
In other words, the given MC itself is irreducible and since the state space is finite all the four states are recurrent

What we saw in the above example can happen at times. When this happens, that is, x y for
all x, y ∈ S, the given chain itself is irreducible, and since the state space is finite, all states are
recurrent. Thus such a chain, irrespective of how it starts, will visit every state in S an infinite
number of times with probability one.
Another example of such a finite state space irreducible chain is :

3
Example 3: Recall the Ehrenfest Diffusion Chain where d balls are distributed between two boxes
and at each turn, one ball is selected at random and transferred from the box where it was, to the
other box. Xn denotes the no. of balls in Box 1 at time n. The state space is S = {0, 1, . . . , d} and
the transition probabilities are given by px,x−1 = x/d = 1 − px,x+1 . One can easily verify that this
is also an irreducible chain (why?) and therefore all states are recurrent.

3 Some Infinite state space examples

In all the examples so far, we have only considered MC with finite state space. The finiteness of
the state space was crucial in making definite conclusions that we could, because of the following
reasons:

• When the state space is finite, there has to be at least one recurrent state.

• As a consequence of the above, all states in a finite state space irreducible MC are recurrent.

Unfortunately, none of the above hold for chains with infinite state space. Therefore, unlike finite
state space case, one cannot have any general algorithm leading to easy identification of recurrent
and transient states. Each chain has to be analyzed separately.
We proceed to examine some specific examples to get some idea of how to go about analyzing
infinite state space cases.

3.1 Infinite state space examples

Example 4: We start with Simple Random Walk. Recall that it is a MC with S = Z and transition
probabilities given by px,x+1 = θ, px,x−1 = 1 − θ. Here θ, 0 < θ < 1, represents the “win” proba-
bility at each stage.
Observe that x (x + 1) and x (x − 1) from definition.
Now, use transitivity to conclude that x y for every x, y ∈ S.
We conclude that the chain is irreducible. However, unlike in the case of finite state space, we
cannot immediately conclude that all states are recurrent (!!). So, what can we do?
Let us first observe one thing. Since the chain is irreducible, only one of two possibiliites exist:
Either all states are recurrent Or all states are transient!!
It therefore suffices to focus attention on any one state and try and see if that state is recur-
rent/transient.
In fact, we will take the state 0 and examine whether 0 is recurrent or transient.

The criterion that we will use to decide on recurrence/transience of the state 0 is to consider the
P (n)
infinite series n p00 and examine its divergence/transience.
However difficult this may seem at first sight, we will actually be able to do it without having to
engage in too much tedious computations!
First observe that, this chain, having started from 0, cannot return to 0 in an odd number of steps
(why?).
P (2n)
Therefore, the above series reduces to n p00 .

4
Now, from the dynamics of the chain, one can easily see that
(2n)
p00 = 2n n


n [θ(1 − θ)] , ∀ n ≥ 1

(Returning to 0 from 0 in 2n steps means exactly n wins and n losses!)

2n
[θ(1−θ)]n, we use the following fact from
P

To decide on divergence/convergence of the series n
n
calculus:
Given two sequences {an } and {bn } of positive real numbers, we say that an ∼ bn if an /bn → 1.
Fact: If {an } and {bn } are positive sequences with an ∼ bn , then
P P
n an converges/diverges, according as n bn converges/diverges.

We will find a positive sequence {bn } such that 2n n

P n [θ(1−θ)] ∼ bn and then use convergence/divergence
of n bn to conclude about transience/recurrence of 0.
We use “Stirling’s Formula”:

1
n!∼ α · e−n n(n+ 2 ) where α > 0 is a constant.

Using this one can deduce that: for some constant β > 0
(2n)
p00 = n 2n n √1 n
P

n [θ(1 − θ)] ∼ β · n · [4θ(1 − θ)]

X 1
So the question now is about convergence/divergence of the series: √ · [4θ(1 − θ)]n
n
n
This clearly depends on the value of the quanity 4θ(1 − θ).

Using basic calculus (or even the A.M.-G.M. inequality!), one can see that,
4θ(1 − θ) ≤ 1 for all 0 ≤ θ ≤ 1

with strict inequality holding if and only if θ 6= 1/2.

X 1
This implies that the series √ · [4θ(1 − θ)]n converges if θ 6= 1/2 and diverges if θ = 1/2. We
n
n
conclude:
0 is recurrent or transient, according as, θ = 12 or θ 6= 12

Using irreducibilty, we finally conclude that Simple Random walk is recurrent or transient, accord-
ing as, θ = 1/2 or θ 6= 1/2.

The transience of Simple Random Walk for the case θ 6= 1/2 is not so unexpected. It can easily be
seen as a consequence of what is called “Strong Law of Large Numbers”:
For i.i.d. random variables ξ1 , ξ2 , . . . with finite common mean µ,
ξ1 + · · · + ξn
→ µ with probability 1
n

5
Recall that Simple Random Walk is defined as Xn = X0 + ξ1 + · · · + ξn , where X0 is the initial
state and ξ1 , ξ2 , . . . are i.i.d. r.v.s, each taking values ±1 with probabilities θ and 1 − θ respectively.
Given that X0 = 0, strong law of large numbers implies that Xn /n → µ with probability 1, that
is, P0 [Xn /n → µ] = 1.
Now, the common mean is µ = 2θ − 1; so when θ 6= 1/2, we have µ 6= 0, which would imply
P0 [ Xn → ±∞ (according as µ > 0 or µ < 0) ] = 1
What this says is: the chain starting from 0 will, with probability 1, eventually get out of any finite
bounds for good.
So, there is no way that the chain starting from 0 will return to 0 “infinitely often”, which is
required to happen (in fact, with probability one) if 0 were to be recurrent.
So, 0 (and hence all states, because of irreducibility) must be transient (Convinced?).
What is not so easy to understand is the recurrence of simple random walk when θ = 1/2 (!!).
In this case, µ = 0; so an application of strong law of large numbers will now yield that, given that
Xn
the walk starts at 0, → 0, with probability 1.
n
But for Xn /n → 0, it is not at all necessary that Xn has to become equal to (or, even come close
to) 0 for infinitely many n. Thus, infinitely many returns to 0 (happening with probability 1) is,
by no means, an obvious fallout of law of large numbers in this case!
In fact, even for general random walk on integers, the above phenomenon is fairly common, namely,
the random walk is recurrent or transient according as the common mean of the underlying ξ-
sequence equals 0 or not. (we don’t prove this!)
Once again, transience in case of non-zero mean is easy to understand from strong law of large
numbers, but recurrence in case of zero mean doesn’t have an easy explanation based on law of
large numbers.

3.2 Renewal Chain

Example 5: Recall the renewal chain where every time an item in operation breaks down, it is
replaced by a fresh item at the start of the next day. (Xn )n≥0 is the MC with S = N, where Xn
denotes the age of the item in operation on day n.
Denoting life of a typical item by the random variable L with values in N, the transition probabilities
of the chain are given by
px,x+1 = P(L ≥ x + 1)/P(L ≥ x), px,1 = P(L = x)/P(L ≥ x),
and pxy = 0 for y 6= x + 1, 1
Note that, by declaring the state space of the chain to be all of N, we have tacitly assumed that
L is not a bounded random variable, that is, P(L ≥ x) > 0 for every x ∈ N. Because, had that
not been the case, that is, had L been a bounded random variable, with M being the maximum
possible value of L, the state space would have been S = {1, 2, . . . , M }.

We will continue with the assumption of L not being bounded, that is, P(L ≥ x) > 0 for all x ∈ N.
This will, in particular, ensure that pxy as given above are all well-defined and further, px,x+1 > 0
for all x and px,1 > 0 for infinitely many x.

6
Thus, on one hand, x x + 1 for all x, and, on the other, given any x ∈ N, there is x0 > x such
that x0 1.
These, in conjunction with transitivity, can be easily seen to imply that that the chain is irreducible.

So, as in case of simple random walk, it is enough to focus on any one state, say, state 1, and
determine if it is recurrent or transient. To this end, we will try to compute P1 (T1 > n) and then
take limit as n → ∞.

From the dynamics of the chain, it is clear that

P1 (T1 > n) = P(X2 = 2, . . . , Xn = n | X0 = 1) = P(L ≥ n) (why?)
It follows from the above that
P1 (T1 = ∞) = lim P1 (T1 > n) = lim P(L ≥ n) = 0
n→∞ n→∞
(tail probabilities!)
This leads to ρ11 = P1 (T1 < ∞) = 1, implying that 1 is recurrent. By the irreducibility of the
chain, we conclude that all states are recurrent.
The analysis in case L is bounded, say, when the maximum possible value of L is M , is even easier,
because then the state space S = {1, . . . , M } is finite and so, from irreducibility, we can directly
conclude recurrence of the chain.