9. Recurrent and Transient States
9.1 Definitions
(n)
9.2 Relations between fi and pii
9.3 Limiting Theorems for Generating Functions
9.4 Applications to Markov Chains
(n)
9.5 Relations Between fij and pij
9.6 Periodic Processes
9.7 Closed Sets
9.8 Decomposition Theorem
9.9 Remarks on Finite Chains
9.10 Perron-Frobenius Theorem
9.11 Determining Recurrence and Transience when Number of
States is Infinite
9.12 Revisiting Statistical Equilibrium
9.13 Appendix. Limit Theorems for Generating Functions
304

9.1 Definitions
Define

(n)

fii = P {Xn = i, X1 = i, . . . , Xn−1 = i|X0 = i}

= Probability of first recurrence to i is at the nth step.
∞
(n)

fi = fii =

fii = Prob. of recurrence to i. n=1 Def. A state i is recurrent if fi = 1.
Def. A state i is transient if fi < 1.
Define Ti = Time for first visit to i given X0 = 1. This is the same as
Time to first visit to i given Xk = i. (Time homogeneous)
∞

mi = E(Ti |X0 = i) =

(n)

nfii = mean time for recurrence n=1 (n)

Note: fii = P {Ti = n|X0 = i}
305

Similarly we can define
(n)

fij = P {Xn = j, X1 = j, . . . , Xn−1 = j|X0 = i}
= Prob. of reaching state j for first time in n steps starting from X0 = i. fij =

∞ n=1 (n)

fij = Prob. of ever reaching j starting from i.

Consider fii = fi = prob. of ever returning to i.
If fi < 1, 1 − fi = prob. of never returning to i.
i.e.
1 − fi = P {Ti = ∞|X0 = i} fi = P {Ti < ∞|X0 = i}

306

TH. If N is no. of visits to i|X0 = i ⇒ E(N |X0 = i) = 1/(1 − fi )
Proof:

E(N |X0 = i) = E[N |Ti = ∞, X0 = i]P {Ti = ∞|X0 = i}
+E[N |Ti < ∞, X0 = i]P {Ti < ∞|X0 = i}

E(N |Xo = i) = 1 · (1 − fi ) + fi [1 + E(N |X0 = i)]

If Ti = ∞ ⇒ except for n = 0 (X0 = i) , there will never be a visit to ii.e. E(N |Ti = ∞, X0 = i) = 1. If Ti < ∞, there is sure to be one visit, say at Xk (Xk = i). But then
E(N |Ti < ∞, Xk = i) = E(N |Ti < ∞, X0 = i) by Markov property;
i.e.
E[N |Ti < ∞, X0 = i] = 1 + E[N |X0 = i]
.. E[N |X0 = i] = 1 · (1 − fi ) + {1 + E[N |X0 = i]} · (fi )
˙
⇒ E[N |X0 = i] = 1/(1 − fi )
∞

Another expression for E[N |X0 = i] =
307

(n)

pii n=0 Relation to Geometric Distribution
Suppose i is transient (fi < 1) and Ni =no. of visits to i.
P {Ni = k + 1|X0 = i} =fik (1 − fi ), k = 0, 1, . . .
∞

E(Ni |X0 = i) =

k=0

(k + 1)fik (1 − fi ) =

∞

k=0

kfik (1 − fi ) + 1

Since
∞

(1 − fi )−1 =
(1 − fi )−2

fik k=0 d
=
(1 − fi )−1 = dfi ∞

kfik−1 k=0 E(Ni |Xo = i) = fi (1 − fi )(1 − fi )−2 + 1
= fi (1 − fi )−1 + 1 = 1/(1 − fi )
308

∞

TH. E[N |X0 = i] =

Proof.

Let Yn =

(n)

pii n=0 
 1 if Xn = i


 0 otherwise

∞

N=

Yn

n=0
(n)

Since P {Yn = 1|X0 = i} = P {Xn = i|X0 = i} = pii
∞

E(N ) =

∞
(n)

E(Yn ) = n=0 pii n=0 E(N ) may be finite or infinite
309

Def: A positive recurrent state is defined by fi = 1, mi < ∞.
A null recurrent state is defined by fi = 1, mi = ∞
Ex:

(n)

fii =

1
1
1
= − n(n + 1) n n+1
∞

fi = n=1 ∞

∞
(n)

But mi =

nfii = n=1 not converge.

1

1
1
− n n+1
∞

=1

n
1
=
= ∞ as series does
(n + 1)n n=1 n + 1

310

Classification of States fi mi

Positive recurrent state

1

<∞

Null recurrent state

1

Transient

<1

∞

<∞

where mi = Expected no. of visits to i given X0 = i.
In addition the recurring and transient states may be characterized by being periodic or aperiodic.
A state is ergodic if it is aperiodic and positive recurrent.

311

(n)

9.2 Relations Between fi and pii
(n)

Consider pii . Starting from X0 = i, the first recurrence to i may be at k = 1, 2, . . . , n. Consider the first visit is at time k and at X n , Xn = i
(k) (n−k)
. Summing over all k another visit is made. This probability is fii pii results in n (n)

(k) (n−k)

pii =

(∗)

fii pii k=1 (o)

where pii = 1 = P {X0 = i|X0 = i}
Multiplying (∗) by sn and summing
∞

∞

n

(n)

(k) (n−k) n

pii sn = n=1 ∞

∞

fii pii

(k)

n=1 k=1

k=1

312

(n−k) n−k

fii sk

s =

pii n=k s

∞

∞

n

(n)

(k) (n−k) n

pii sn = n=1 ∞

∞

fii pii

(k)

n=1 k=1

(n−k) n−k

fii sk

s = k=1 pii n=k Pii (s) − 1 = Fii (s)Pii (s)
∞

where

∞
(n)

(n)

pii sn , Fii (s) =

Pii (s) = n=0 fii sn n=1 Pii (s) =

1
1 − Fii (s)

Note:
∞
(n)

lim Fii (s) = Fii (1) =

s→1

fii = fi n=1 ∞
(n)

lim Fii (s) = Fii (1) =

s→1

nfii = mi n=1 313

s

Theorems

∞
(n)

(a) If Pii (1) =
0

pii = ∞ ⇒ fi = 1.

Conversely if fi = 1, Pii (1) = ∞
∞
(n)

(b) If Pii (1) =
0

pii < ∞ ⇒ fi < 1.

Conversely if fi < 1, Pii (1) < ∞

314

9.3 Limiting Theorems for Generating Functions
∞

Consider A(s) = n=0 an sn , |s| ≤ 1 with an ≥ 0.

n

1. lim

n→∞

k=0

ak = lim A(s) where s → 1 means s → 1−. s→1 2. Define n a∗ (n) =

ak /(n + 1) k=0 lim a∗ (n) = lim (1 − s)A(s)

n→∞

s→1

3. Cesaro Limit
The Cesaro limit is defined by lim a∗ (n) If the sequence {an } has a limit Π = lim an then n→∞ n→∞ lim a∗ (n) n→∞ = Π.

The Cesaro limit may exist without the existence of the ordinary limit.
315

Ex. an : 0, 1, 0, 1, 0, 1, . . . lim an does not exist.

n→∞

However a∗ (n) =







1
2
1
2 (1

if n even
1
− n ) if n is odd

1 lim a (n) = n→∞ 2
∗

316

9.4 Application to Markov Chains n Consider p∗ (n) = ii k=0

(k)

pii n+1 n
(k)

pii

is expected no. of visits to i starting from X0 = i (p0 = 1). ii k=0

Dividing by (n + 1), p∗ (n) is expected no. of visits per unit time. ii Ex. n = 29 days, p∗ (29) = 2/30; i.e. 2 visits per 30 days or 1 visit per ii 15 days. One would expect mean time between visits = 15 days.

317

n

TH. lim

n→∞

fi = 1

k=0

(k)

1 pii =
, where mi = expected no. of visits and n+1 mi

Proof: Consider Pii (s) =

1
1 − Fii (s)

lim (1 − s)Pii (s) = lim

n→∞

s→1

p∗ (n) ii (1 − s)
= lim
.
s→1 1 − Fii (s)

Since Fii (1) = fi , if fi = 1, the r.h.s. is indeterminate. Using
L’Hopital’s rule lim n→∞

p∗ (n) ii 1
1
=
=
Fii (1) mi Recall a positive recurrent state has mi < ∞ ⇒
A null recurrent state has mi = ∞
⇒

lim p∗ (n) = 0 or ii n→∞

(n)

lim pii = 0

n→∞

318

lim p∗ (n) > 0 ii n→∞

(n)

9.5 Relations Between fij and pij

(i = j)

(n)

fij = P {Xn = j, Xr = j, r = 1, 2, . . . , n − 1|X0 = i}
= Prob. of starting from i and reaching j for first time at nth step.
∞
(n)

fij =

fij

i=j

n=1

Proceeding as before (i = j)
(n)

pij

(1) (n−1)

= fij pjj

(2) (n−1)

(n)

+ fij pjj

+ . . . + fij

n
(k) (n−k)

=

fij pjj

(0)

(pjj = 1)

k=1

Multiplying by sn and summing over n
∞

∞
(n)
pij sn

n=1

n
(k) (n−k) n

=

fij pjj n=1 k=1

319

s

∞

∞
(k)
fij sk

Pij (s) = k=1 (n−k) n−k

pjj

s

n=k

Pij (s) = Fij (s)Pjj (s)

i=j

lim (1 − s)Pjj (s) = lim p∗ (n) = lim (1 − s)Pij (s)/Fij (1) jj n→∞

s→1

lim

n→∞

p∗ (n) jj s→1

p∗ (n)
1
ij
=
= lim or n→∞ Fij (1) mi ∞

∞
(n)
pij

Also Pij (1) =

lim

n→∞

p∗ (n) ij (n)

= Fij (1)

n=1
∞

pjj . n=0 ∞
(n)

Hence if n=0 pjj = ∞ ⇒

(n)

n=0

∞

pij = ∞
∞

(n)

Similarly if n=0 pjj < ∞ ⇒

(n)

n=0

pij < ∞
320

(0)

(pij = 0).

Fij (1)
=
mi

Summary
∞
(n)

Transient n=0 pii < ∞, fi < 1, mi = 1/(1 − fi )
∞

(n)

(n)

lim pii = 0,

n→∞

n=1

pij < ∞,

(n)

lim pij = 0

n→∞

∞
(n)

Positive Recurrent n=0 pii = ∞, fi = 1, mi < ∞

lim p∗ (n) > 0 (= 1/mi ) ii Negative Recurrent

n→∞ lim p∗ (n) > 0 (= Fij (1)/mi ) ij n→∞
∞
(n) pii = ∞, fi = 1, mi = ∞ n=0 lim p∗ (n) = 0, ii n→∞

321

(n)

lim pii = 0

n→∞

9.6 Periodic Processes
Suppose transition probabilities have period d.
Then
(n)

(n)

pij = 0, pii = 0 if n = rd r = 1, 2, . . .
(n)

(n)

pij ≥ 0, pii ≥ 0 if n = rd
∞

∞
(rd)

(rd)

pii srd =

Pii (s) = r=0 pii z r , z = sd r=0 ∞

∞
(rd)
fii srd

Fii (s) = r=1 (rd) r

=

fii r=1 322

z

We now have a power series in z
∞

lim Pii (Z)

z→1

(rd)

=

pii r=0 n

lim (1 − z)Pii (z)

z→1

= n→∞ r=0

(rd)

pii n+1 ∞

∞
(n)
nfii

Note: E(N |X0 = i) =

(rd)

=d

1

rfii r=1 ∞
(rd)

However Fii (1) =

fii

r = mi /d

r=1

Since Pii (Z) = 1/[1 − Fii (z)] lim p∗ (n) = d/mi or ii n→∞

(nd)

lim pii

n→∞

323

= d/mi

= mi

9.7 Closed Sets
Def. A set of states C is closed if no state outside C can be reached from
/
any state in C; i.e., pij = 0 if i ∈ C and j ∈ C.
Absorbing state: Closed set consisting of a single state.
Irreducible Chain: If only closed set is the set of all states. (Every state can be reached from any other state).
This means that we can study the behavior of states in C by omitting all other states.

324

Th. i ↔ j, i is recurrent ⇒ j recurrent i ↔ j, i is transient ⇒ j transient
∞

∞

(r)

pjj

≥

r=0

∞

(r+n+m)

pjj

(m) (r) (n)

=

r=0

pjk pkk pkj r=0 k∈S
∞

∞

≥

(m) (n) (n) pji pii pij r=0 ∞

r=0

(r)

pii r=0 ∞
(r)

Thus if

=

(m) (n) pji pij

pii = ∞,

(r)

r=0

pjj = ∞

Suppose i is transient, i ↔ j and assume j is recurrent. By theorem just proved i then must be recurrent. However this is a contradiction
⇒ j is transient.

325

Summary (Aperiodic, irreducible)
1. If i ↔ j and j is positive recurrent ⇒ i is positive recurrent
(n)

(n)

lim pij = lim pjj = Πj = 1/mj .

n→∞

n→∞

2. If i ↔ j and j is null recurrent ⇒ i is null recurrent
(n)

lim pjj = 0,

n→∞

(n)

lim pij = 0

n→∞

or P (∞) = lim P (n) = lim P n = 0. n→∞ n→∞

3. If i ↔ j and j is transient ⇒ i is transient
(n)

(n)

lim pjj = 0, lim pij = 0

n→∞

n→∞

326

9.8 Decomposition Theorem
(a) The states of a Markov Chain may be divided into two sets (one of which may be empty). One set is composed of all the recurring states, the other of all the transient states.
(b) The recurrent states may be decomposed uniquely into two closed sets. Within each closed set all states inter-communicate and they are all of the same type and period. Between any two closed sets no communication is possible.

327

Ex. Decomposition of a Finite Chain
C0
C0
P =
C1
C2
C3
C0 :
C1 :
C2 :
C3 :

.
1 0 .
.
.
0 0 .
.
.
.
.
O
.
.
.
O
.
.
A .

C1
0 ··· 0
0 ··· 0
P1
O
B

C2
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

0 ··· 0
0 ··· 0
O
P1
C

Consists of two absorbing states
Consists of closed recurrent states
Consists of closed recurrent states
Consists of transient states

A: Transitions C3 → C0
C: Transitions C3 → C2

B: Transitions C3 → C1
D: Transitions C3 → C3
328

C3
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

0 ··· 0
0 ··· 0
O
O
D

9.9 Remarks on Finite Chains
1. A finite chain cannot consist only of transient states.
If i, j are transient

(n)

lim pij = 0,

n→∞

However
(n)

pij = 1 j∈S leading to a contradiction as n → ∞.
2. A finite chain cannot have any null recurrent states.
The one step transition probabilities within a closed set of null recurrent states form a stochastic matrix P such that
(n)
pij = 1.
P n → 0 as n → ∞. This is impossible as j∈S 329

9.10 Perron-Frobenius Theorem
Earlier we had seen that if P has a characteristic root (eigenvalue) = 1 of multiplicity 1, and all other |λi | < 1, then
P (∞) = E1 .
The conditions under which this is true are proved by the
Perron-Frobenius Theorem. The necessary and sufficient conditions are:
P :
P :
(∞)

Then P1

aperiodic positive recurrent (mi < ∞).

= P ∞ = E1 = 1y

where y P = y

and 1 = 1

1

···

1

Def. A state is ergodic if it is aperiodic and positive recurrent.

330

9.11 Determining Recurrence and Transience when Number of States is Infinite
Compute fi = P {Ti < ∞|X0 = i} in a closed communicating class.
⇒ All states are recurrent if fi = 1; All states are transient if fi < 1. pi,0 = qi pi,i+1 = pi ,

0 with qi
Xn+1 =
Xn + 1 with pi

Ex. S = {0, 1, 2, . . . },

P {T0 > n|X0 = 0} = P {X1 = 1, X2 = 1, . . . , Xn = n|X0 = 0} n−1 pi

= i=0 ∞

P {T0 < ∞|X0 = 0} = 1 − lim P {T0 > n|x0 = 0} = 1 − n→∞ .. State 0 (and all states in closed class) are recurrent iff
˙
331

∞ i=0 pi i=0 pi = 0

Ex. Random Walk on Integers
S
pi,i+1
(2n+1)

p00

(2n)

p00

= {0, ±1, ±2, . . . }
= p, pi,i−1 = q, p + q = 1
= 0, n ≥ 0 (Go from 0 to 0 in odd number of transitions)
=

2n n n p q n Consider
∞

∞
(n)
p00

n=1

∞

(2n) p00 = n=1 332

(2n)! n n p q
=
n!n! n=1 ∞

Note: Ratio Test: If A =

an and n=0 an+1
< 1 series converges as n → ∞ an an+1
> 1 series diverges as n → ∞ an 2n+2
(2n + 1)(2n + 2) p00 pq → 4pq as n → ∞
=
2n p00 (n + 1)(n + 1)
If p = q

4pq < 1.

If p = q = 1/2 4pq = 1 and test is inconclusive.
2n s 2n−s
∼ N (2np, 2npq) = N (n, n/2) if p = 1/2 p q s ∼e

−(s−n)2 /n

333

n
2π
2

(2n)

Since p00

1
∼√
πn
∞

∞

(2n) p00 n=1

∼
=

1
√
πn n=1 series diverges

.. State 0 is recurrent.
˙
Th. An irreducible Markov Chain with S = {0, 1, 2, . . . } and Transition
Prob. {pij } is transient iff
∞

yi =

pij yj j=1 has a non-zero bounded solution
Proof: P.88

334

i = 1, 2, . . .

Ex. Random walk on S = {0, 1, 2, . . . } pi,i+1 = pi , pi,i−1 = qi pi,i = ri , q0 = 0 (pi + qi + ri = 1)

Equations: q1 y1 = p11 y1 + p12 y2 = r1 y1 + p1 y2 ⇒ y2 = 1 + p1 y2 = p21 y1 + p22 y2 + p23 y3 = q2 y1 + r2 y2 + p2 y3
⇒ y3 =

q1 q1 q2
1+
+ p1 p1 p2

335

y1

y1

In general, n−1 yn = 1 + k=1 n−1

yn =

αk k=0 q1 q2 . . . q k y1 , n ≥ 1 p1 p2 . . . p k

q1 q2 . . . q k
, α0 = 1 y1 , α k = p1 p2 . . . p k
∞

Thus the solution is bounded if k=0 αk < ∞

336

9.12 Revisiting Statistical Equilibrium
Assume the Markov Chain has all states which are irreducible positive recurrent aperiodic. (Called Ergodic Chain).
Earlier we had shown
(n)

(n)

lim pij = lim pjj = 1/mj = Πj

n→∞

n→∞

⇒ Πj is given by the solution
Πj =

Πi pij where i∈S Πj = 1 j∈S or in matrix notation we can write the linear equations as
Π = P Π where Π : k × 1, P : k × k.
Proof aj (n) = P {Xn = j} and we will show that limn→∞ aj (n) = Πj
(n)

aj (n + m) =

Πi pij i∈S 337

Take m → ∞
If n = 1

(n)

Πj =

Πi pij

Πj =

for any n

i∈S

Πi pij i∈S Allow n → ∞ which is true if

Πj =

Πi

Πj

i∈S i∈s Πi = 1

In the above we made use of
(n)

(n)

lim pij = lim pjj = Πj

n→∞

n→∞

which holds for ergodic chains.
If chain was transient or null recurrent
(n)

(n)

pij = pjj → 0 as n → ∞ and Πj = and result does not hold.
338

(n)

i∈S

Πi pij → 0 as n → ∞,

Th: If a0 (j) = P {X0 = j} = Πj then

P {an = j} = Πj for all n.

This theorem states that if the initial probabilities correspond to the limiting probabilities, then for any n p{Xn = j} = Πj .

Proof:
(n)

In general aj (n) = write an = P n a0

a0 (i)pij

and in matrix notation we can

i∈S

If ao = Π, an = P n Π. But Π is defined by Π = P Π. ⇒ an = P Π = Π
This is the reason why Π is sometimes referred to as the stationary distribution. 339

9.13 Appendix. Limit Theorems for Generating Functions
∞

an denote a power series. In our application z z Definition: Let A(z) = n=0 will always be real, however all the results also hold if z is a complex number. Theorem If {an } are bounded, say |an | ≤ B, then A(z) converges for at least |z| < 1.
∞

Proof :

A(z) = |A(z)| ≤

n=0

∞

|an |z n | ≤ B

n=0

|z|n = B/1−|z|

Definition: The number R is called the radius of convergence of the power series A(z) if A(z) converges for |z| > R. Without loss of generality the radius of convergence can be taken as R = 1. Note if R is
∞

bn y n and the

the radius of convergence of A(z) we can write A(z) = radius of convergence of y will be unity.
340

0

Properties of A(z)
(i) If R is the radius of convergence
R−1 = lim sup(an )1/n n→∞ (ii) Within the interval of convergence (−R < z < R), A(z) has derivatives of all orders which may be obtained by term-wise b A(z)dz is given by term-wise

differentiation. Similarly the integral a integration for any (a, b) in (−R, R).
∞

bn z n both converge and are equal for all

(iii) If A(z) and B(z) =
0

|z| < R, then an = bn .
(iv) No general statement can be made about the convergence of the an Rn may or may not be finite. series on the boundary |z| = R; i.e. n 341

Two important theorems on power series are:
Abel’s Theorem Suppose A(z) has a radius of convergence R = 1 and
∞

an is convergent to s. Then
0
∞

lim A(z) =

z→1−

an n=0 If the coefficients {an } are non-negative, the result continues to hold whether or not the sum on the right is convergent.

342

Note:
N

N

an z n =

AN (z) = n=0 n=0

n

(sn − sn−1 )z n ,

N

= n=0 sn =

N −1

sn z n − z

sn z n n=0 N

= (1 − z)

sn z n + s N z N n=0 lim An (z) = sN and taking the limit as N → ∞

z→1−

lim sN = s

N →∞

343

ai i=0 Theorem: If the sequence {bn } converges to a limit b ( lim = b), then n→∞ ∞

lim (1 − z)

z→1−
∞

n=0
N

We can write n=0 where

n=0

∞

bn z n =

(1 − z)

Proof:

bn z n = b

n=0

(bn − bn−1 )z n

(b−1 = 0)

N

(bn − bn−1 )z n = (1 − z)

sn z n + s)nz N n=0 n

sn = i=0 (bi − bi−1 ) = b0 + (b1 − b0 ) + (b2 − b1 ) + . . . + (bn − bn−1 ) = bn
N

Therefore

(1 − z)

n=0
N

and lim (1 − z) z→1− n=0

N

bn an = (1 − z)

sn z n + b n z N n=0 bn z n = bn , so that as N → ∞, lim bN = b.
N →∞

344