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

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

2.6 Stopping Times and the Strong Markov Property 143

26 47



(2)









(2)







It follows by a simple calculation that the invariant distributions for

(2)

)

on C

and C

are, respectively,

(0)



(0)

,π

(0)





, π

(1)



(1)

,π

(1)





Therefore, the unique invariant distribution for the Markov chain on

={2, 4, 6, 7} is given by

π =



, 0,

, 0







, 0,











= (π

,π

)



2.6 Stopping Times and the Strong Markov Property

of Markov Chains

The Markov property deﬁned in Section 2.2 has two important

and stronger versions for Markov chains. The Markov property

implies that the conditional distribution of (X

, X

n+1

,...,X

n+m

given {X

, X

,...,X

}, depends only on X

. Here we have taken

, X

n+1

,...,X

n+m

) in place of (X

n+1

,...,X

n+m

) in the original Def-

inition 3.1.

P(X

= j

, X

n+1

= j

,...,X

n+m

= j

| X

, X

,...,X

)

= P(X

= j

, X

n+1

= j

,...,X

n+m

= j

| X

)

= P

= j

, X

= j

,...,X

= j

), (6.1)

all three terms being zero if j

= i

, and equal to P

= j

,...,X

)if j

= i

To state the ﬁrst stronger version of the Markov property, we need a

deﬁnition.

Deﬁnition 6.1 For each n ≥ 0, the process X

={X

n+m

: m = 0, 1,...}

is called the after-n process.

144 Markov Processes

The next result says that the conditional distributions of X

,given

, X

,...,X

}, depend only on X

and is in fact P

, i.e., the distri-

bution of a Markov chain with transition probability matrix p and initial

state X

Theorem 6.1 The conditional distribution of X

, given {X

, X

,...,

},isP

, i.e., for every (measurable) set F in the inﬁnite product

space S

∞

, one has

P(X

∈ F | X

= i

, X

,...,X

= i

) = P

((X

, X

,...,) ∈ F).

(6.2)

Proof. When F is ﬁnite-dimensional, i.e., of the form F ={ω =

( j

, j

,...) ∈ S

∞

:(j

, j

,..., j

) ∈ G}={(X

, X

,...,X

) ∈ G}

for some G ⊂ S

m+1

, (6.2) is just the Markov property in the form (6.1).

Since this is true for all m, and since the Kolmogorov sigmaﬁeld on the

product space S

∞

is generated by the class of all ﬁnite-dimensional sets,

(6.2) holds (see Complements and Details).

To state the second and the most important strengthening of the Markov

property, we need to deﬁne a class of random times τ such that the Markov

property holds, given the past up to these random times.

Deﬁnition 6.2 A random variable τ with values in Z

∪ {∞} =

{0, 1, 2,...,} ∪ {∞} is a stopping time if the event {τ = m} is deter-

mined by {X

, X

,...,X

} for every m ∈ Z

If τ is a stopping time and m



< m, then the event {τ = m



} is deter-

mined by {X

, X

,...,X



}and, therefore, by {X

, X

,...,X

}. Hence

an equivalent deﬁnition of a stopping time τ is {τ ≤ m} is determined

by {X

, X

, .., X

} for every m ∈ Z

Informally, whether or not the Markov chain stops at a stopping time

τ depends only on {X

, X

,...,X

}, provided τ<∞.

Example 6.1 Let A be an arbitrary nonempty proper subset of the

(countable) state space S. The hitting time η

of a chain {X

: n =

0, 1,...} is deﬁned by

= inf{n ≥ 1: X

∈ A}, (6.3)

the inﬁnum being inﬁnity (∞) if the set within {}above is empty, i.e.,

if the process never hits A after time 0. This random time takes values in

2.6 Stopping Times and the Strong Markov Property 145

{1, 2,...} ∪ {∞}, and

{η

= 1}={X

∈ A}

{η

= m}=



m−1



n=1

/∈ A }



∩{X

∈ A} (m ≥ 2), (6.4)

proving that it is a stopping time. On the other hand, the last time γ

say, that the process hits A, is, in general, not a stopping time, since the

event {γ

= m} equals {X

∈ A}



∞

n=m+1

/∈ A }.

If, in deﬁnition (6.3) one allows n = 0 then the stopping time is called

the ﬁrst passage time to A, denoted by T

= inf



n ≥ 0: X

∈ A



. (6.5)

Thus if X

∈ A, T

= 0. As in the case η

, it is easy to check that T

a stopping time.

For singleton sets A ={i} one writes η

and T

instead of η

{i}

and T

{i}

Deﬁnition 6.3 The rth return time to i of a Markov chain is deﬁned by

(0)

= 0,η

(r)

:= inf



n >η

(r−1)

: X

= i



(r ≥ 1). (6.6)

Exercise 6.1 Check that η

(r)

(r ≥ 1) are stopping times.

For a stopping time τ denote by X

the after-τ process {X

τ +n

: n =

0, 1,...} on the set {τ<∞} (if τ =∞, X

is not deﬁned). Also write

)

= X

τ +n

for the state of the after - τ process at time n. The strong

Markov property deﬁned below is an extension of (6.2) to stopping times.

Deﬁnition 6.4 A Markov chain {X

: n = 0, 1,...} is to have the strong

Markov property if, for every stopping time τ , the conditional distribution

of the after - τ process X

, given the past up to time τ,isP

on the set

{τ<∞}:

P(X

∈ F,τ = m | X

, X

,...,X

) = P

(F)1

{τ =m}

, (6.7)

for every F belonging to the Kolmogorov sigmaﬁeld F = S

∗∞

on S

∞

and every m ∈ Z

Theorem 6.2 Every Markov chain has the strong Markov property.

146 Markov Processes

Proof. If τ is a stopping time, then for all F ∈F and every m ≥ 0,

P(X

∈ F,τ = m | X

= i

, X

= i

,...,X

= i

)

= P(X

∈ F,τ = m | X

= i

, X

= i

,...,X

= i

)

= P(X

∈ F | X

= i

, X

= i

,...,X

= i

{τ =m}

Since the event {τ = m} is determined by {X

, X

,...,X

}, the last

equality trivially holds if {X

= i

, X

= i

,...,X

= i

}implies {τ =

m}, both sides being zero. If {X

= i

, X

= i

,...,X

= i

} implies

{τ = m}, then both sides of the last equality are P(X

∈ F | X

,...,X

= i

) = P

((X

, X

,...,) ∈ F) ≡ P

(F). Hence (6.7)

holds.

Example 6.2 (First passage times for the simple random walk) Let

: n = 1, 2,...} be i.i.d. Bernoulli with P(Z

=+1) = p, P(Z

−1) = q where q = 1 − p (0 < p < 1). A simple random walk starting

at x is the process on S =

Z deﬁned by X

= x, X

= x + Z

+···+

(n ≥ 1), with x ∈ Z. Since {X

: n ≥ 0} is a process with independent

increments it has the Markov property. Indeed its transition probabilities

are given by p

i,i+1

= p, p

i,i−1

= q, p

= 0if|i − j| > 1ori = j .We

ﬁrst compute the probability ϕ(x) that the random walk starting at x

reaches d before c, where c < d are given integers, and c ≤ x ≤ d, i.e.,

ϕ(x) = P(T

< T

| X

= x). Now if c < x < d, then

P({X

: n ≥ 0} reaches d before c and Z

=+1 | X

= x)

= P({X



:= x + 1 + Z

+···+Z

n+1

(n ≥ 1), X



= x + 1}

reaches d before c and Z

=+1) = pϕ(x + 1),

since, {X



: n ≥ 0} is a simple random walk starting at x + 1, and it is

independent of Z

. Similarly

P({X

: n ≥ 0} reaches d before c and Z

=−1 | X

= x)

= qϕ(x − 1).

Adding the two relations we get

ϕ(x) = pϕ(x + 1) + qϕ(x − 1),

ϕ(x + 1) −ϕ(x) =

(ϕ(x) − ϕ(x − 1)), c < x < d. (6.8)

2.6 Stopping Times and the Strong Markov Property 147

In the case p =

= q, the increments of ϕ are constant, so that ϕ is

linear. Since ϕ(c) = 0, ϕ(d) = 1, one has in this case

ϕ(x) =

x − c

d − c

, c ≤ x ≤ d. (6.9)

If p =

, then an iteration of (6.8) yields

ϕ(x + 1) −ϕ(x) =





x−c

(ϕ(c + 1) − ϕ(c)) =





x−c

ϕ(c + 1).

(6.10)

Summing both sides over x = c, c + 1,...,y − 1, one gets

ϕ(y) = ϕ(c + 1)

y−1



x=c





x−c

= ϕ(c + 1)



1 − (q/ p)

y−c

1 − (q/ p)



. (6.11)

To compute ϕ(c + 1), let y = d in (6.11) and use ϕ(d) = 1, to get

ϕ(c + 1) =

1 − (q/ p)

d−c

Substituting this in (6.11) we have

ϕ(y) =

1 − (q/ p)

y−c

1 − (q/ p)

d−c

, c ≤ y ≤ d. (6.12)

To compute the probability ψ(x) = P(T

< T

| X

= x), one similarity

solves (6.8) (with ψ in place of ϕ), but with boundary conditions ψ(c) =

1,ψ(d) = 0, to get

ψ(y) =

d − y

d − c

(c ≤ y ≤ d), if p =

ψ(y) =

1 − ( p/q)

d−y

1 − ( p/q)

d−c

(c ≥ y ≤ d), if p =

. (6.13)

Exercise 6.2 Alternatively, one may derive (6.13) from (6.9), (6.12) by

“symmetry,” noting that {−X

: n = 0, 1,...} is a simple random walk

starting at −x, and with the increment process {−Z

: n ≥ 1}.

Note that ϕ(y) +ψ(y) = 1 for c ≤ y ≤ d. This implies that the simple

random walk will reach the boundary {c, d} with probability 1, whatever

148 Markov Processes

be c < x < d. Letting c ↓−∞in (6.9) and (6.12), one arrives at

:= P(η

< ∞|X

= y) = P(T

< ∞|X

= y)



1ifp ≥

(p/q)

d−y

if p <

;(y < d)

. (6.14)

Similarly, by letting d ↑∞in (6.12), one gets

:= P(η

< ∞|X

= y) = P(T

< ∞|X

= y)



1ifp ≤

(q/ p)

y−c

if p >

;(y > c)

. (6.15)

Note that T

= η

if X

≡ x = y (see (6.3) and (6.5)). It now follows

from (6.14) and (6.15), with d = y + 1 and c = y − 1, respectively, and

intersecting {η

< ∞} with Z

=+1 and Z

=−1, that

:= P(η

< ∞|X

= y) = pρ

y+1,y

+ qρ

y−1,y











1ifp =

2q if p >

2p if p <

or in all cases

= 2 min{p, q}. (6.16)

Next, use the strong Markov property with the stopping time η

(r)

(see

(6.6)) to get



(r+1)

< ∞|X

= x



= E





(r)

< ∞ and



(r)



= y for some n ≥ 1 | given the past up to η

(r)



= E



(r)

(

= y for some n ≥ 1

)



(r)

< ∞





= E



(

= y for some n ≥ 1

)



(r)

< ∞



= ρ





(r)

< ∞



= ρ



(r)

< ∞|X

= x



(6.17)

Iterating (6.17) one arrives at



(r+1)

< ∞|X

= x



= ρ

P(η

< ∞|X

= x)

= ρ

(x, y ∈ S). (6.18)

2.6 Stopping Times and the Strong Markov Property 149

Letting r ↑∞and using (6.16) we get

P(X

= yi.o. | X

= x) =



1ifp =

0ifp =

, (6.19)

where “i.o.” stands for inﬁnitely often. One expresses (6.19) as follows

the simple random walk on

Z is recurrent (i.e., ρ

= 1 for all x) if it

is symmetric and transient (i.e., ρ

< 1 for all x) otherwise. Note that

transience, in case p =

, also follows from the SLLN (see Appendix):

+···+Z

→ EZ

= 0, as n →∞, (6.20)

with probability 1.

Example 6.3 One may modify the simple random walk of the preceding

example slightly by letting the step sizes Z

have the distribution P(Z

−1) = q, P(Z

= 0) = r, P(Z

=+1) = p, with p + q + r = 1, p >

0, q > 0. Then the transition probabilities are

i,i−1

= q, p

i,i

= r , p

i,i+1

= p(i ∈ Z). (6.21)

Then ϕ(x):= P(T

< T

| X

= x), c ≤ x ≤ d, satisﬁes

ϕ(x) = pϕ(x + 1) + qϕ(x − 1) +rϕ(x), c < x < d,

(p + q)ϕ(x) = pϕ(x + 1) + qϕ(x − 1).

From this we get the same relation as (6.8) and, in the symmetric case

p = q, (6.9) holds. As a consequence all the relations (6.10)–(6.19) hold,

provided one writes p = q instead of p =

, and p = q instead of p =

Thus one has

ϕ(x) =

x − c

d − x

, c ≤ x ≤ d,ifp = q;

ϕ(x) =

1 − (q/ p)

x−c

1 − (q/ p)

d−c

, c ≤ x ≤ d,ifp = q. (6.22)

Then ψ (x):= P(T

< T

| X

= x), c ≤ x ≤ d,isgivenbyψ(x) =

1 − ϕ(x), as in (6.13). Based on these expressions for ϕ(x) and ψ(x),

150 Markov Processes

one derives (see (6.14) and (6.15))



1ifp ≥ q

(p/q)

d−y

if p < q

(y < d);



1ifp ≤ q

(q/ p)

y−c

if p > q

(y > c). (6.23)

From (6.23) one gets

= pρ

y+1,y

+ qρ

y−1,y

+r,



1ifp = q,

2 min{p, q}+r if p = q

. (6.24)

Thus the chain is transient in the asymmetric case (p = q) and recurrent

in the symmetric case (p = q).

We now turn to the computation of m(x):= E(T

{c,d}

| X

= x) for

c ≤ x ≤ d, where T

{c,d}

= inf{n ≥ 0: X

= c or d}. By conditioning on

=+1, −1, or 0, one obtains

m(x) = 1 + pm (x + 1) +qm(x − 1) +rm(x), c < x < d,

m(c) = 0, m(d) = 0, (6.25)

whose solution is given by (see (C8.8) in Complements and Details)

m(x) =







(x −c)(d−x)

p+q

, if p = q,

d−c

p−q

1−(q/ p)

x−c

1−(q/ p)

d−c

−

x−c

p−q

,ifp = q.

(6.26)

Note that by letting d ↑∞in (6.26), one has E

≡ E

x−c

q−p

< ∞

for x > c,if p < q, and E

≡ E

d−x

p−q

< ∞for x < d,if p > q.

=∞in all other cases.

2.7 Transient and Recurrent Chains

We now introduce some concepts that are critical in understanding the

asymptotic behavior of a Markov chain {X

: n = 0, 1,...}with a (count-

able) state space S, and a transition probability matrix p. Write, as before,

= P

(η

< ∞). (7.1)

Deﬁnition 7.1 A state y ∈ S is recurrent if ρ

= 1. A state y ∈ S is

transient if ρ

< 1.

2.7 Transient and Recurrent Chains 151

If P

(η

= 1) = 1 then p

= 1 and y is an absorbing state and y is

necessarily recurrent.

Let us denote by 1

(z) the indicator function of the set {y} deﬁned by

(z) =



1ifz = y

0ifz = y



. (7.2)

Denote by N (y) the number of times after time 0 that the chain is in state

y. We see that

N (y) =

∞



n=1

). (7.3)

The event {N (y) ≥ 1} is the same as the event {η

< ∞}. Thus,

(N (y) ≥ 1) = P

(η

< ∞) = ρ

. (7.4)

One has

(N (y) ≥ 2) = ρ

. (7.5)

For this note that

{N (y) ≥ 2}={η

< ∞ and X

returns to y}.

Hence, using the strong Markov property (see Theorem 6.2)

(N (y) ≥ 2) = P

(η

< ∞ and X

= y for some n ≥ 1)

= E

[η

<∞]

= y for some n ≥ 1)

= E



[η

<∞]

= y for some n ≥ 1)



= E



[η

<∞]



= ρ

(η

< ∞) = ρ

Similarly we conclude that

(N (y) ≥ m) = ρ

m−1

for m ≥ 1. (7.6)

Since

(N (y) = m) = P

(N (y) ≥ m) − P

(N (y) ≥ m + 1), (7.7)

it follows that

(N (y) = m) = ρ

m−1

(1 − ρ

) for m ≥ 1. (7.8)

Also,

(N (y) = 0) = 1 − P

(N (y) ≥ 1) = 1 − ρ

. (7.9)

152 Markov Processes

Let us denote by E

(·) the expectation of random variables deﬁned in

terms of a Markov chain starting at x. Then

(N (y)) = E



∞



n=1

)



∞



n=1



)



∞



n=1

(n)

. (7.10)

Write G(x, y) = E

(N (y)) =



∞

n=1

(n)

. Then G(x, y) is the expected

number of visits to

y for a Markov chain starting at x, after time 0.

Theorem 7.1

(i) Let y be a transient state. Then, P

(N (y) < ∞) = 1 and G(x, y) =

1−ρ

< ∞∀x ∈ S.

(ii) Let y be a recurrent state. Then, P

(N (y) =∞) = 1 and

G(y, y) =∞. Also P

(N (y) =∞) = P

(η

< ∞) = ρ

∀x ∈ S. If

= 0, then G(x, y) = 0. If ρ

> 0 then G(x, y) =∞.

Proof.

(i) Let y be a transient state. Since 0 <ρ

< 1, we see by (7.6) that

(N (y) =∞) = lim

m→∞

(N (y) ≥ m) = lim

m→∞

m−1

= 0.

Now by (7.8),

G(x, y) = E

(N (y))

∞



m=1

(N (y) = m)

∞



m=1

m−1

(1 − ρ

) = ρ

(1 − ρ

)

∞



m=1

mρ

m−1

Now, differentiating both sides of the identity

(1 − t)

−1

≡

∞



m=0

(|t| < 1),