Bhattacharya R., Majumdar M. Random Dynamical Systems: Theory and Applications

Подождите немного. Документ загружается.

2.7 Transient and Recurrent Chains 153

one arrives at

∞



m=1

m−1

(1 − t)

, G(x, y) =

1 − ρ

< ∞, (ρ

< 1).

(ii) Let y be a recurrent state. Then ρ

= 1 and from (7.6) one gets

(N (y) =∞) = lim

m→∞

(N (y) ≥ m) = ρ

In particular, P

(N (y) =∞) = 1. If a nonnegative random variable has

a positive probability of being inﬁnite, then its expectation is inﬁnite.

Thus

G(y, y) = E

(N (y)) =∞.

If ρ

= 0, then p

(n)

= 0 for all n ≥ 1. Thus G(x, y) = 0. If

> 0, then again, P

(N (y) =∞) = ρ

> 0. Hence, G(x, y) =

(N (y)) =∞.

Next, we show that recurrence is a class property:

Proposition 7.1 Let x be a recurrent state and suppose x leads to y, i.e.,

x → y , then y is recurrent and ρ

= ρ

= 1.

Proof. Assume that x = y, otherwise there is nothing to prove. Since

(η

< ∞) = ρ

> 0 it must be that P

(η

= n) > 0 for some integer

n ≥ 1. Let n

be the smallest such positive integer, i.e., n

= min(n ≥

1: P

(η

= n) > 0). Then p

)

> 0 and p

(m)

= 0 for any m such that

1 ≤ m < n

. Therefore, we can ﬁnd states y

,...,y

−1

none of them

equal to either x or y, such that

= y

,...,X

−1

= y

−1

, X

= y) = p

···p

−1

> 0.

We want to prove that ρ

= 1. Suppose that ρ

< 1. Then a Markov

chain starting at y has a probability 1 −ρ

of never hitting x. This

means that the chain starting at x has the positive probability δ =

···p

−1y

)(1 − ρ

) of visiting y

,...,y

−1

, y successively in the

ﬁrst n

periods and never hitting x after time n

. Hence a Markov chain

starting from x never returns to x with probability at least δ>0, con-

tradicting the assumption that x is recurrent.

154 Markov Processes

Since ρ

= 1, there is a positive integer n

such that p

)

> 0. Now,

+n+n

)

= P

+n+n

= y)

≥ P

= x, X

+n+n

= y)

= p

)

(n)

)

It follows that G(y, y) ≥ p

)



∞

n=1

(n)

= p

)

G(x, x) =∞.

Hence y is a recurrent state. Since y is recurrent and y → x, we can

similarly prove that ρ

= 1.

In view of Theorem 7.1 and Proposition 7.1, for an irreducible Markov

chain either all states are transient or all states are recurrent. In the former

case the chain is said to be transient and in the latter case the chain is

called recurrent.

For studying the long-run behavior of a Markov chain, we note the

following:

Proposition 7.2 Every inessential state of a Markov chain is trans-

ient.

Proof. Let y be inessential. Then there exists x = y such that ρ

> 0,

but ρ

= 0. Suppose, if possible, y is recurrent. Then, by Proposi-

tion 7.1, x is recurrent and ρ

= 1. Consider the Markov chain starting

at y. Since ρ

= 1, η

:= inf{n ≥ 1: X

= x} < ∞, with probability 1.

Since ρ

= 0, the probability that y occurs after time η

is zero. But this

implies that, with probability 1, y occurs only ﬁnitely often, contradicting

the supposition that y is recurrent.

It follows that every recurrent state is essential. On the other hand,

essential states need not be recurrent. For example, the simple asymmetric

random walk on

Z (with 0 < p < 1) and the simple symmetric random

walk

, k ≥ 3, are irreducible (implying that all states are essential) and

transient.

Example 7.1 (Simple symmetric random walk on

) Let Z

, n ≥ 1,

be i.i.d. with P(Z

= e

) = 1/2k = P(Z

=−e

) for i = 1, 2,...,k,

where e

(∈ Z

) has 1 as its ith coordinate and 0’s elsewhere. For any

given x ∈

, the stochastic process X

:= x +Z

+···+Z

(n ≥ 1),

= x, is called the simple symmetric random walk on Z

, starting at x.

2.7 Transient and Recurrent Chains 155

In view of independent increments Z

(n ≥ 1), this process is a Markov

chain on S =

Theorem 7.2 (Polya) The simple symmetric random walk on Z

recurrent if k = 1, 2 and transient if k ≥ 3.

Proof. The case k = 1 is proved in Section 2.6. Consider the case k = 2.

Since every state y ∈

leads to every other state z (i.e., the chain is

irreducible), it is enough to prove that 0 = (0, 0) is a recurrent state, or

G(0, 0) =∞. Since the return times to each state x are even integers

n = 2, 4,...(i.e., the chain is periodic with period 2), one has

G(0, 0) =

∞



m=1

(2m)

∞



m=1

P(Z

+ Z

+···+Z

= (0, 0))

∞



m=1



r=0





2m − r



2m − 2r

m − r



m − r





∞



m=1











r=0





, (7.11)

since Z

+···+Z

= (0, 0) if and only if the number of Z



s, which

equal e

,sayr, is the same as the number which equal −e

, and the

number of Z



s which equal e

is the same as the number which equal

−e

, namely, m − r .Now



r=0







r=0





m − r







, (7.12)

since the second sum equals the number of ways m balls can be selected

from a box containing m distinct red balls and m distinct white balls.

Thus

G(0, 0) =

∞



m=1









. (7.13)

By Stirling’s formula,

r! = (2π)

1/2

r+1/2

−r

(1 + o(1)), (7.14)

156 Markov Processes

where o(1) → 0asr →∞. Hence





∪

∩

(2m)

2m+1/2

2m+1

2m+1/2

1/2





∪

∩

2m+1/2

, (7.15)

where c(m) ∪

∩

d(m) means there exist numbers 0 < A < B indepen-

dent of m, and a positive integer m

, such that A < c(m)/d(m) < B

for all m ≥ m

. Using (7.15) in (7.13), one obtains G(0, 0) =∞, since



∞

m=1

1/m =∞. This proves recurrence for the case k = 2. For k ≥ 3,

one gets, analogous to (7.11),

G(0, 0) =

∞



m=1



(2k)

−2m

2m!

···(r

, (7.16)

where the inner sum is over all k-tuples of nonnegative integers

, r

,...,r

, whose sum is equal to m.

Write the inner sum as

−2m







k,m

,...,r

), (7.17)

where p

k,m

,...,r

):= (k

−m

)m!/(r

!,...,r

!) is the probability of

the ith box receiving r

balls (1 ≤ i ≤ k) out of m balls distributed at

random over k boxes. Let a

k,m

denote the maximum of these probabilities

over all assignments r



i=1

= m. Then (7.17) is no more than

−2m





k,m

, (7.18)

since p

k,m

≤ p

k,m

. In the case m is an integer multiple of k, one can

show (see Exercise 7.1) that

k,m

= (k

−m

)m!/

. (7.19)

For the general case one can show that (Exercise 7.1)

k,rk+s

≤ a

k,rk

for all s = 1, 2,...,k − 1. (7.20)

Grouping m in blocks of k consecutive values rk ≤ m < (r + 1)k

(r = 1, 2,...), one then has

G(0, 0) ≤

∞



r=1

−2rk



2(r + 1)k

(r + 1)k



k,rk

k−1



m=1





−2m

. (7.21)

2.7 Transient and Recurrent Chains 157

Using Stirling’s formula (7.14), the inﬁnite sum in (7.21) is no more than

∞



r=1

−2rk

(2(r + 1)k)

2(r+1)k+

((r + 1)k)

2(r+1)k+1

−rk+1

(rk)

rk+

k(r+

)

= A2

2k+

3/2

∞



r=1

((r + 1)k)

1/2

(k−1)/2

≤ A



∞



r=1

k/2

< ∞ (k ≥ 3), (7.22)

where A and A



depend only on k. Thus, by Theorem 7.1, the simple

symmetric random walk is transient in dimensions k ≥ 3.

Exercise 7.1

(a) Show that r !(r + s)! ≥ (r + 1)!(r + s − 1)! for all s ≥ 1, with

strict inequality for s ≥ 2, and equality for s = 1. Use this to prove that,

for ﬁxed k and m, the maximum of p

k,m

,...,r

) occurs when r

’s are

as close to each other as possible, differing by no more than one. [Hint:

Take r to be the smallest among the r

’s and r + s the largest, and alter

them to r + 1 and r + 1 − s (unless s ≤ 1). Repeat the procedure with

the altered set of r

’s until they are equal (if m is a multiple of k) or differ

by at most one.]

(b) Show that

k,rk+s

= k

−(rk+s)

(rk + s)!

(r!)

k−s

((r + 1)!)

for 0 ≤ s < k. (7.23)

One may give a proof of the recurrence of a one-dimensional simple

symmetric random walk along the same lines as above, instead of the

derivation given in Section 2.6. For this, write, using the ﬁrst estimate in

(7.15),

G(0, 0) =

∞



m=1

(2m)

∞



m=1





2m!

(m!)

> A

∞



m=1

−1/2

=∞, (7.24)

for some positive number A.

158 Markov Processes

It may be pointed out that an asymmetric random walk on Z

(k ≥ 1)

deﬁned by X

= x, X

= x + Z

+···+Z

(n ≥ 1), where x ∈ Z

and

(n ≥ 1) are i.i.d. with values in Z

and E(Z

) = 0,istransient for all

k ≥ 1. This easily follows from the SLLN: with probability 1,

+···+Z

→ EZ

= 0asn →∞.Ifx were to be a recurrent state then

(with probability 1) there would exist a random sequence n

< n

< ···

such that X

= x for all m = 1, 2,...,implying X

→ 0as

m →∞, which is a contradiction.

For general recurrent Markov chains, the following consequence of the

strong Markov property (Theorem 6.2) is an important tool in analyzing

large-time behavior.

Recall (from (6.6)) that η

(r)

is the rth return time to state x.For

simplicity of notation we sometimes drop the subscript x, i.e., η

(0)

0 and η

(1)

≡ η

(1)

:= inf{n ≥ 1: X

= x}, η

(r+1)

≡ η

(r+1)

= inf{n >η

(r)

= x} (r ≥ 1).

Theorem 7.3 Let x be a recurrent state of a Markov chain. Then the ran-

dom cycles W

= (X

(r)

, X

(r)

,...,X

(r+1)

), r ≥ 1, are i.i.d., and are

independent of W

= (X

, X

,...,X

(1)

).IfX

≡ x, then the random

cycles are i.i.d. for r ≥ 0.

Proof. By Theorem 7.1 (ii), η

(r)

< ∞ for all r ≥ 1, outside a set of 0

probability. By the strong Markov property (Theorem 6.2), the condi-

tional distribution of the after-η

(r)

process X

(r)

= (X

(r)

, X

(r)

,...,),

given the past up to time η

(r)

is P

(r)

= P

. Since the latter is nonrandom,

it is independent of the past up to time η

(r)

. In particular, the cycle W

(r)

, X

(r)

,...,X

(r+1)

) is independent of all the preceding cycles.

Also, the conditional distribution of (X

(r)

,...,X

(r+1)

), given the past

up to time η

(r)

is the P

distribution of W

= (X

= x, X

,...,X

(1)

which is therefore also the unconditional distribution.

Finally, the following result may be derived in several different ways

(see Corollary 11.1).

Proposition 7.3 A Markov chain on a ﬁnite state space has at least one

invariant probability.

Proof. First we show that the class E of essential states is nonempty.

If all states are inessential and, therefore, transient (Proposition 7.2),

2.8 Recurrence and Steady State Distributions 159

then p

(n)

→ 0asn →∞for all i, j ∈ S (Theorem 7.1). Considering

the fact that



j∈S

(n)

= 1 ∀n, since S is ﬁnite, one can take term-by-

term limit of the sum to get 0 = 1, a contradiction. Now if E comprises

a single (equivalence) class of communicating states, then the Markov

chain restricted to E is irreducible and one may use either Corollary 5.1

or Theorem 5.2 to prove the existence of a unique invariant probability ¯π

on E. By letting ¯π assign mass zero to all inessential states, one obtains

an invariant probability on S.IfE comprises several equivalence classes

of communicating essential states E

, E

,...,E

, then, by the above

argument, there exists an invariant probability π

( j)

on E

(1 ≤ j ≤ m). By

assigning mass zero to S\E

, one extends π

( j)

to an invariant probability

on S.

2.8 Positive Recurrence and Steady State Distributions

of Markov Chains

By Theorem 5.2, every irreducible Markov chain on a ﬁnite state space

has a unique invariant probability π and that chain approaches this steady

state distribution over time, in the sense that 1/n



m=1

(m)

→ π

n →∞(for all i, j ∈ S). Such a result does not extend to the case

when S is denumerable (i.e., countable, but inﬁnite). As we have seen

in Section 2.7, many interesting irreducible Markov chains are transient

and, therefore, cannot have an invariant distribution.

Exercise 8.1 Prove that a transient Markov chain cannot have an invari-

ant distribution. [Hint: By Theorem 7.1 p

(n)

→ 0asn →∞.]

It is shown in this section that an irreducible Markov chain has a unique

invariant distribution if and only if it is positive recurrent in the following

sense:

Deﬁnition 8.1 A recurrent state x is positive recurrent if E

< ∞,

where η

= inf{n ≥ 1, X

= x} is the ﬁrst return time to x. A recurrent

state x is null recurrent if E

=∞.Anirreducible Markov chain

all whose states are positive recurrent is said to be a positive recurrent

Markov chain.

To prove our main result (Theorem 8.1) of this section we will need

the following, which is of independent interest.

160 Markov Processes

Proposition 8.1

(a) If a Markov chain has a positive recurrent state i, then it has an

invariant distribution π = (π

:j∈ S) where

= lim

n→∞



m=1

(m)

( j ∈ S), π

. (8.1)

(b) If i is positive recurrent and i → j , then j is positive recurrent.

Proof.

(a) Let i be a positive recurrent state, and consider the Markov chain

: n = 0, 1,...} with initial state i . By Theorem 7.3, η

(r+1)

− η

(r)

(r = 0, 1,...) are i.i.d., where η

(0)

= 0, η

(r+1)

≡ η

(r+1)

= inf{n >η

(r)

= i} (r ≥ 0). In particular η

(1)

= η

. By the SLLN one has, with

probability 1,

(N )



N −1

r=0

(η

(r+1)

− η

(r)

)

→ E

(1)

≡ E

as N →∞. (8.2)

Deﬁne N

= N

(i) = sup{r ≥ 0: η

(r)

≤ n}, namely, the number of re-

turns to i by time n(n ≥ 1). Then, with probability 1, N

→∞and

0 ≤

n − η

)

≤

+1)

− η

)

→ 0asn →∞. (8.3)

The last convergence follows from the fact that Z

/r → 0 (almost surely)

as r →∞, where we write Z

= η

(r+1)

− η

(r)

(see Exercise 8.2). Using

(8.3) in (8.2) we get

lim

n→∞

= E

, lim

n→∞

a.s. (8.4)

Next write T

(r)

= #{m ∈ [η

(r)

,η

(r+1)

): X

= j }, the number of visits

to j during the rth cycle. Then T

(r)

(r ≥ 0) are i.i.d. with a (common)

expectation E

(0)

≤ E

< ∞, so that by the SLLN (and the fact that

→∞as n →∞),

lim

N →∞



N −1

r=0

(r)

= E

(0)

, lim

n→∞



−1

r=0

(r)

= E

(0)

, (8.5)

almost surely. Now



−1

r=0

(r)

is the number of m ∈ [0,η

)

) such that

= j , and differs from



m=1

=j]

by no more than η

+1)

− η

)

2.8 Recurrence and Steady State Distributions 161

Hence, again using (8.3), (8.4), and by (8.5),

lim

n→∞



m=1

=j]

= lim

n→∞



−1

r=0

(r)

(0)

, (8.6)

with probability 1. Since the sequence under the limit on the left is

bounded by 1, one may take expectation to get

lim

n→∞



m=1

(m)

(0)

= π

,say(j ∈ S). (8.7)

Note that



j∈S

(0)

= η

(1)

≡ η

,so



j∈S



j∈S

(0)



j∈S

(0)

= 1, (8.8)

proving that π = (π

: j ∈ S) is a probability measure on S.Asinthe

proof of Theorem 5.2 [see (5.27), (5.30), and (5.31)], (8.7) implies the

invariance of π (also see Theorem 5.3). Since T

(0)

= 1 a.s., the second

relation in (8.1) also follows.

(b) First note that, under the given hypothesis, j is recurrent (Propo-

sition 7.1). In (8.6), replace n by η

(r)

– the time of rth visit to j (r ≥ 1).

Then one obtains

lim

r→∞

(r)

(0)

a.s. (8.9)

Note that E

(0)

= E

(r)

(r ≥ 1) must be positive. For otherwise

(r)

= 0 for all r (with probability 1), implying ρ

= 0.

But η

(r)

= η

(1)



m=2

(η

(m)

− η

(m−1)

), where η

(1)

≡ η

. Since

/r → 0 a.s., (as r →∞) and (η

(m)

− η

(m−1)

), m ≥ 2, is an i.i.d. se-

quence, η

(r)

/r → E

(η

(2)

− η

(1)

) a.s. (as r →∞). Since the limit (8.9)

is positive, we have E

= E

(η

(2)

− η

(1)

) < ∞. That is, j is positive

recurrent.

Exercise 8.2 Suppose a

(r = 1, 2,...) is a sequence such that c

(1/r)



m=1

converges to a ﬁnite limit c,asr →∞. Show that

/r → 0asr →∞. [Hint: the sequence c

is Cauchy and

− c

r−1

) − (

r−1

− 1)c

r−1

162 Markov Processes

Exercise 8.3 Find a Markov chain which is not irreducible but has a

unique invariant probability.

The main result of this section is the following:

Theorem 8.1 For an irreducible Markov chain the following statements

are equivalent.

(1) There exists a positive recurrent state.

(2) All states are positive recurrent.

(3) There exists an invariant distribution.

(4) There exists a unique invariant distribution.

(5) The quantities π

: = 1/E

( j ∈ S) deﬁne a unique invariant

distribution, and

lim

n→∞



m=1

(m)

= π

∀i, j. (8.10)

(6) π

:= 1/E

( j ∈ S) deﬁne a unique invariant distribution, and

lim

n→∞



j∈S

)



m=1

(m)

− π

)

= 0 ∀i. (8.11)

Proof. (1) ⇔ (2) ⇒ (3). This follows from Proposition 8.1.

(2) ⇒ (5). To see this note that, if (2) holds then (8.1) holds ∀i, j ,

implying π is the unique invariant distribution (see Theorem 5.3).

(5) ⇒ (6). This follows from Scheff´e’s Theorem (see Lemma C 11.3

in Complements and Details) and (8.10).

Clearly, (6) ⇒ (5) ⇒ (4) ⇒ (3).

It remains to prove that (3) ⇒ (1). For this suppose π is an invariant

distribution and j is a state such that π

> 0. Then j is recurrent; for

otherwise p

(n)

→ 0 ∀i (by Theorem 7.1(i)), leading to the contradiction

0 <π



(n)

→ 0asn →∞.

By irreducibility, all states are recurrent. To prove that j is positive

recurrent, consider the Markov chain {X

: n = 0, 1,...} with some ini-

tial state i and deﬁne N

( j) = sup{r ≥ 0: η

(r)

≤ n} (r ≥ 1),η

(0)

= 0.

Note that (η

(r+1)

− η

(r)

), r ≥ 1, are i.i.d. Suppose, if possible, j is not