We classify states in Markov chains according to several key
state properties, and then classify Markov chains according to
properties that are shared by all states in the chain. Several
of the classification properties are based of the idea of
first passage times. The first passage
time from state ii to state
jj is the number of transitions to
reach state jj the first time from
state ii.
f
i
j
(
n
)
=Prfirst passage time i → j is n
f
i
j
(
n
)
first passage time i → j is n
Using this definition, we can identify states as
transient or recurrent.
state i is recurrent⇔∑n=1∞
f
i
j
(
n
)
=1
⇔
state i is recurrent
n
1
f
i
j
(
n
)
1
state i is transient⇔∑n=1∞
f
i
j
(
n
)
<1
⇔
state i is transient
n
1
f
i
j
(
n
)
1
A state is transient if there is a non-zero probability that
once the chain leaves that state, it will not return.
The mean time to return to recurrent state
ii is
∑n=1∞
f
i
j
(
n
)
n
1
f
i
j
(
n
)
.
If a state is recurrent, it can be recurrent
nonnull or recurrent null.
recurrent state i is recurrent nonnull⇔∑n=1∞n
f
i
j
(
n
)
<∞
⇔
recurrent state i is recurrent nonnull
n
1
n
f
i
j
(
n
)
recurrent state i is recurrent null⇔∑n=1∞n
f
i
j
(
n
)
=∞
⇔
recurrent state i is recurrent null
n
1
n
f
i
j
(
n
)
The following is an example of a Markov chain with states that
are recurrent null.
Consider state 0. It is easy to see that
f
0
0
(
1
)
=0
f
0
0
(
1
)
0
f
0
0
(
2
)
=12
f
0
0
(
2
)
1
2
f
0
0
(
3
)
=1213=16
f
0
0
(
3
)
1
2
1
3
1
6
f
0
0
(
4
)
=122314=1314=112
f
0
0
(
4
)
1
2
2
3
1
4
1
3
1
4
1
12
and in general
∀n,n>1:
f
0
0
(
n
)
=1n-11n
n
n
1
f
0
0
(
n
)
1
n
1
1
n
The probability of eventually returning to state 0 is
∑n=1∞
f
0
0
(
n
)
=∑n=2∞1n-11n=∑n=1∞1n1n+1
n
1
f
0
0
(
n
)
n
2
1
n
1
1
n
n
1
1
n
1
n
1
Using induction, we can verify that
∑n=1∞1n1n+1=k-1k
n
1
1
n
1
n
1
k
1
k
and hence
∑n=1∞
f
0
0
(
n
)
=limk→∞k-1k=1
n
1
f
0
0
(
n
)
k
k
1
k
1
Thus, state 0 is recurrent. To determine if it is recurrent
nonnull or recurrent null, compute the expected time to return:
∑n=1∞n
f
0
0
(
n
)
=∑n=2∞n1n-11n=∑n=1∞1n=∞
n
1
n
f
0
0
(
n
)
n
2
n
1
n
1
1
n
n
1
1
n
Since the expected time to return to state 0 is infinite, the
state must be recurrent null.
Recurrent nonnull states can be periodic or
aperiodic.
recurrent state i is periodic with period k>1⇔
f
i
j
(
n
)
≠0⇔∀m,m∈123…:n=km
⇔
recurrent state i is periodic with period k>1
⇔
f
i
j
(
n
)
0
m
m
1
2
3
…
n
k
m
Otherwise, ii is aperiodic.
In other words, a state is periodic if the probability of
returning to the state is zero except at regular intervals. An
example of a Markov chain with states that are periodic is the
following:
f
0
0
(
1
)
=0
f
0
0
(
1
)
0
f
0
0
(
2
)
=1-p
f
0
0
(
2
)
1
p
f
0
0
(
3
)
=0
f
0
0
(
3
)
0
f
0
0
(
4
)
=p1-p
f
0
0
(
4
)
p
1
p
f
0
0
(
5
)
=0
f
0
0
(
5
)
0
f
0
0
(
6
)
=p21-p
f
0
0
(
6
)
p
2
1
p
⋮
⋮
In general, for
j∈123…
j
1
2
3
…
,
f
0
0
(
2
j
)
=pj-11-p
f
0
0
(
2
j
)
p
j
1
1
p
f
0
0
(
2
j
-
1
)
=0
f
0
0
(
2
j
-
1
)
0
Hence state 0 is periodic with period 2.
If all of the states of a Markov chain are recurrent nonnull, we
say that the chain is recurrent nonnull. If all states are
periodic (aperiodic), the chain is periodic (aperiodic).
