2Classification of chains and states

IB Markov Chains

2.5 Further classification of states

So far, we have classified chains in say, irreducible and reducible chains. We

have also seen that states can be recurrent or transient. By definition, a state

is recurrent if the probability of returning to it is 1. However, we can further

classify recurrent states. Even if a state is recurrent, it is possible that the

expected time of returning is infinite. So while we will eventually return to the

original state, this is likely to take a long, long time. The opposite behaviour is

also possible — the original state might be very attracting, and we are likely to

return quickly. It turns out this distinction can affect the long-term behaviour

of the chain.

First we have the following proposition, which tells us that if a state is

recurrent, then we are expected to return to it infinitely many times.

Theorem. Suppose

X

0

=

i

. Let

V

i

=

|{n ≥

1 :

X

n

=

i}|

. Let

f

i,i

=

P

i

(

T

i

< ∞

).

Then

P

i

(V

i

= r) = f

r

i,i

(1 − f

i,i

),

since we have to return

r

times, each with probability

f

i,i

, and then never return.

Hence, if

f

i,i

= 1, then

P

i

(

V

i

=

r

) = 0 for all

r

. So

P

i

(

V

i

=

∞

) = 1.

Otherwise,

P

i

(

V

i

=

r

) is a genuine geometric distribution, and we get

P

i

(

V

i

<

∞) = 1.

Proof. Exercise, using the strong Markov property.

Definition (Mean recurrence time). Let

T

i

be the returning time to a state

i

.

Then the mean recurrence time of i is

µ

i

= E

i

(T

i

) =

(

∞ i transient

P

∞

n=1

nf

i,i

(n) i recurrent

Definition (Null and positive state). If

i

is recurrent, we call

i

a null state if

µ

i

= ∞. Otherwise i is non-null or positive.

This is mostly all we care about. However, there is still one more technical

consideration. Recall that in the random walk starting from the origin, we can

only return to the origin after an even number of steps. This causes problems for

a lot of our future results. For example, we will later look at the “convergence”

of Markov chains. If we are very likely to return to 0 after an even number of

steps, but is impossible for an odd number of steps, we don’t get convergence.

Hence we would like to prevent this from happening.

Definition (Period). The period of a state i is d

i

= gcd{n ≥ 1 : p

i,i

(n) > 0}.

A state is aperiodic if d

i

= 1.

In general, we like aperiodic states. This is not a very severe restriction. For

example, in the random walk, we can get rid of periodicity by saying there is a

very small chance of staying at the same spot in each step. We can make this

chance is so small that we can ignore its existence for most practical purposes,

but will help us get rid of the technical problem of periodicity.

Definition (Ergodic state). A state

i

is ergodic if it is aperiodic and positive

recurrent.

These are the really nice states.

Recall that recurrence is a class property — if two states are in the same

communicating class, then they are either both recurrent, or both transient. Is

this true for the properties above as well? The answer is yes.

Theorem. If i ↔ j are communicating, then

(i) d

i

= d

j

.

(ii) i is recurrent iff j is recurrent.

(iii) i is positive recurrent iff j is positive recurrent.

(iv) i is ergodic iff j is ergodic.

Proof.

(i)

Assume

i ↔ j

. Then there are

m, n ≥

1 with

p

i,j

(

m

)

, p

j,i

(

n

)

>

0. By the

Chapman-Kolmogorov equation, we know that

p

i,i

(m + r + n) ≥ p

i,j

(m)p

j,j

(r)p

j,i

(n) ≥ αp

j,j

(r),

where

α

=

p

i,j

(

m

)

p

j,i

(

n

)

>

0. Now let

D

j

=

{r ≥

1 :

p

j,j

(

r

)

>

0

}

. Then

by definition, d

j

= gcd D

j

.

We have just shown that if

r ∈ D

j

, then we have

m

+

r

+

n ∈ D

i

. We

also know that

n

+

m ∈ D

i

, since

p

i,i

(

n

+

m

)

≥ p

i,j

(

n

)

p

ji

(

m

)

>

0. Hence

for any

r ∈ D

j

, we know that

d

i

| m

+

r

+

n

, and also

d

i

| m

+

n

. So

d

i

| r

. Hence

gcd D

i

| gcd D

j

. By symmetry,

gcd D

j

| gcd D

i

as well. So

gcd D

i

= gcd D

j

.

(ii) Proved before.

(iii) This is deferred to a later time.

(iv) Follows directly from (i), (ii) and (iii) by definition.

We also have the following proposition we will use later on:

Proposition. If the chain is irreducible and j ∈ S is recurrent, then

P(X

n

= j for some n ≥ 1) = 1,

regardless of the distribution of X

0

.

Note that this is not just the definition of recurrence, since recurrence says

that if we start at

i

, then we will return to

i

. Here we are saying wherever we

start, we will eventually visit i.

Proof. Let

f

i,j

= P

i

(X

n

= j for some n ≥ 1).

Since

j → i

, there exists a least integer

m ≥

1 with

p

j,i

(

m

)

>

0. Since

m

is least,

we know that

p

j,i

(m) = P

j

(X

m

= i, X

r

= j for r < m).

This is since we cannot visit

j

in the path, or else we can truncate our path and

get a shorter path from j to i. Then

p

j,i

(m)(1 − f

i,j

) ≤ 1 − f

j,j

.

This is since the left hand side is the probability that we first go from

j

to

i

in

m

steps, and then never go from

i

to

j

again; while the right is just the probability

of never returning to

j

starting from

j

; and we know that it is easier to just not

get back to

j

than to go to

i

in exactly

m

steps and never returning to

j

. Hence

if f

j,j

= 1, then f

i,j

= 1.

Now let λ

k

= P(X

0

= k) be our initial distribution. Then

P(X

n

= j for some n ≥ 1) =

X

i

λ

i

P

i

(X

n

= j for some n ≥ 1) = 1.