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.