2Classification of chains and states

IB Markov Chains

2.1 Communicating classes

Suppose we have a Markov chain

X

over some state space

S

. While we would

usually expect the different states in

S

to be mutually interacting, it is possible

that we have a state

i ∈ S

that can never be reached, or we might get stuck in

some state

j ∈ S

and can never leave. These are usually less interesting. Hence

we would like to rule out these scenarios, and focus on what we call irreducible

chains, where we can freely move between different states.

We start with an some elementary definitions.

Definition (Leading to and communicate). Suppose we have two states

i, j ∈ S

.

We write

i → j

(

i

leads to

j

) if there is some

n ≥

0 such that

p

i,j

(

n

)

>

0, i.e.

it is possible for us to get from

i

to

j

(in multiple steps). Note that we allow

n = 0. So we always have i → i.

We write i ↔ j if i → j and j → i. If i ↔ j, we say i and j communicate.

Proposition. ↔ is an equivalence relation.

Proof.

(i) Reflexive: we have i ↔ i since p

i,i

(0) = 1.

(ii) Symmetric: trivial by definition.

(iii)

Transitive: suppose

i → j

and

j → k

. Since

i → j

, there is some

m >

0

such that

p

i,j

(

m

)

>

0. Since

j → k

, there is some

n

such that

p

j,k

(

n

)

>

0.

Then p

i,k

(m + n) =

P

r

p

i,r

(m)p

rk

(n) ≥ p

i,j

(m)p

j,k

(n) > 0. So i → k.

Similarly, if

j → i

and

k → j

, then

k → i

. So

i ↔ j

and

j ↔ k

implies

that i ↔ k.

So we have an equivalence relation, and we know what to do with equivalence

relations. We form equivalence classes!

Definition (Communicating classes). The equivalence classes of

↔

are commu-

nicating classes.

We have to be careful with these communicating classes. Different commu-

nicating classes are not completely isolated. Within a communicating class

A

,

of course we can move between any two vertices. However, it is also possible

that we can escape from a class

A

to a different class

B

. It is just that after

going to

B

, we cannot return to class

A

. From

B

, we might be able to get to

another space

C

. We can jump around all the time, but (if there are finitely

many communicating classes) eventually we have to stop when we have visited

every class. Then we are bound to stay in that class.

Since we are eventually going to be stuck in that class anyway, often, we can

just consider this final communicating class and ignore the others. So wlog we

can assume that the chain only has one communicating class.

Definition (Irreducible chain). A Markov chain is irreducible if there is a unique

communication class.

From now on, we will mostly care about irreducible chains only.

More generally, we call a subset closed if we cannot escape from it.

Definition (Closed). A subset C ⊆ S is closed if p

i,j

= 0 for all i ∈ C, j ∈ C.

Proposition. A subset C is closed iff “i ∈ C, i → j implies j ∈ C”.

Proof.

Assume

C

is closed. Let

i ∈ C, i → j

. Since

i → j

, there is some

m

such

that p

i,j

(m) > 0. Expanding the Chapman-Kolmogorov equation, we have

p

i,j

(m) =

X

i

1

,··· ,i

m−1

p

i,i

1

p

i

1

,i

2

, ··· , p

i

m−1

,j

> 0.

So there is some route

i, i

1

, ··· , i

m−1

, j

such that

p

i,i

1

, p

i

1

,i

2

, ··· , p

i

m−1

,j

>

0.

Since

p

i,i

1

>

0, we have

i

1

∈ C

. Since

p

i

1

,i

2

>

0, we have

i

2

∈ C

. By induction,

we get that j ∈ C.

To prove the other direction, assume that “

i ∈ C, i → j

implies

j ∈ C

”. So

for any i ∈ C, j ∈ C, then i → j. So in particular p

i,j

= 0.

Example. Consider S = {1, 2, 3, 4, 5, 6} with transition matrix

P =

1

2

1

2

0 0 0 0

0 0 1 0 0 0

1

3

0 0

1

3

1

3

0

0 0 0

1

2

1

2

0

0 0 0 0 0 1

0 0 0 0 1 0

1

2

3

4

5 6

We see that the communicating classes are {1, 2, 3}, {4}, {5, 6}, where {5, 6} is

closed.