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

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

2.9 Markov Processes on Measurable State Spaces 183

Theorem 9.1 may be derived as an immediate corollary of Proposi-

tion 9.1. To see this, write

(N )

(x, A) = λ(A) +q

(N )

(x, A), (9.26)

where q

(N )

(x, A) = p

(N )

(x, A) − λ(A) ≥ 0, q

(N )

(x, S) = 1 − λ(S).

Hence



= sup

x∈S,A∈S

)

(N )

(x, A) − p

(N )

(y, A)

)

= sup

x∈S,A∈S

)

(N )

(x, A) − q

(N )

(y, A)

)

≤ sup

x∈S,A∈S

(N )

(x, A) = 1 − λ(S) < 1,

verifying the hypothesis of Proposition 9.1.

Example 9.1 For a simple application of Theorem 9.1, consider a

Markov process on a Borel subset S of

with a transition probabil-

ity density p(x, y) such that

g(y):= inf

x∈S

p(x, y) > 0 on a subset of S of positive Lebesgue measure.

(9.27)

Then one may take λ(A) =

g(y)dy, A ∈ S. The condition (9.27)

holds, e.g., if S is a compact rectangle and (x, y) → p(x, y) is con-

tinuous and positive on S × S. Then g(y) ≥ δ := min{p(x, y): x, y ∈

S} > 0.

The next result, which extends the convergence criterion of Theorem

8.1 to general state spaces, is a centerpiece of the general theory of

irreducible Markov processes. Its proof is spelled out in Complements

and Details.

Theorem 9.2 Suppose there exists a set A

∈ S with the following two

properties:

(1) A

is recurrent, i.e.,

P(η

< ∞|X

= x) = 1 ∀x ∈ S, (9.28)

and

(2) A

is locally minorized, i.e., there exist (i) a probability measure ν

on (S, S) with ν(A

) = 1, (ii) a number λ>0, and (iii) a positive integer

184 Markov Processes

N , such that

(N )

(x, A) ≥ λν(A ) ∀x ∈ A

, A ∈ S. (9.29)

If, in addition,

(3) sup{E(η

= x):x ∈ A

} < ∞,

then there exists a unique invariant probability π, and, for every x ∈ S,

sup

A∈S

)



m=1

(m)

(x, A) − π (A)

)

→ 0, as n →∞. (9.30)

Deﬁnition 9.2 A Markov process {X

: n = 0, 1,...} with transition

probability p is said to be irreducible with respect to a nonzero sigma-

ﬁnite measure ν,orν-irreducible, if for each x ∈ S and B ∈ S with

ν(B) > 0, one has

(n)

(x, B) > 0 for some n ≥ 1. (9.31)

If, in addition, it is ϕ-recurrent, i.e., for each x ∈ S and each A ∈ S such

that ϕ( A) > 0, one has P(η

< ∞|X

= x) = 1 where η

= η

(1)

inf{n ≥ 1: X

∈ A}, then the Markov process is said to be Harris re-

current. If a Harris recurrent process satisﬁes sup{E(η

| X

= x): x ∈

} < ∞ for some ϕ-recurrent set A

, then the process is said to be

positive Harris recurrent.

Remark 9.4 It is known that if S is a Borel subset of a Polish space,

with S its Borel sigmaﬁeld, then conditions (1) and (2) of Theorem 9.2

together are equivalent to the process being irreducible (with respect to

ν) and ν-recurrent. Thus Theorem 9.2 says that, on such a state space, a

positive Harris recurrent process converges to a unique steady state π

as time increases, in the sense (9.30).

Remark 9.5 In the case N = 1, the Markov process in Theorem 9.2 is

said to be strongly aperiodic. By an argument somewhat similar to that

used for the countable state space case (Theorem 8.2), one can show that

in this case one has

sup

A∈S

(n)

(x, A) − π (A)|→0asn →∞, (9.32)

strengthening (9.30) (see Complements and Details).

2.10 Strong Law of Large Numbers and Central Limit Theorem 185

Example 9.2 (Positive recurrent markov chain) Every irreducible pos-

itive recurrent Markov chain satisﬁes the hypothesis of Theorem 9.2,

with A

={x}, x an arbitrary state, N a sufﬁciently large multiple of the

period of x, ν = δ

(i.e., ν({x}) = 1, ν(S\{x}) = 0, and λ = p

(N )

2.10 Strong Law of Large Numbers

and Central Limit Theorem

In this section we derive the SLLN and the CLT for sums



m=0

f (X

)

for a broad class of functions f on the state space S of a positive recurrent

Markov chain X

(n ≥ 0). The main tools for this are the classical SLLN

and CLT for i.i.d. summands, together with the fact (see Theorem 7.3)

that the random cycles W

= (X

η(r)

, X

η(r)

,...,X

η(r+1)

), r ≥ 1,

are i.i.d. Here η

(0)

≡ 0,η

(r)

:= η

(r)

= inf{n >η

(r−1)

: X

= i} (r ≥ 1)

with some (any) speciﬁed state i. For convenience we will consider the

nonoverlapping cycles



:= (X

η(r)

, X

η(r)

,...,X

η(r+1)

−1

)(r ≥ 1). (10.1)

Since these are obtained simply by omitting the last term X

η(r+1)

≡ i

from the i.i.d. cycles W

, the cycles W



(r ≥ 1) are also i.i.d.

Theorem 10.1 (SLLN for Markov chains) Let X

(n ≥ 0) be an irre-

ducible positive recurrent Markov chain on S with the unique invari-

ant probability π . Then, if f is a real-valued function on S such that

| f |dπ<∞, one has

lim

n→∞

n + 1



m=0

f (X

) =

fdπ a.s., (10.2)

whatever the initial distribution (of X

Proof. Fix i and let η

(r)

= η

(r)

as above. Recalling the notation T

(0)

#{m: η

(1)

≤ m ≤ η

(2)

− 1, X

= j } (see (8.1) and (8.7)), one has

(2)

−1



m=η

(1)

| f (X

)|=E



j∈S

(0)

| f ( j )| (10.3)



j∈S

| f ( j )|=(1/π

)

| f |dπ<∞.

186 Markov Processes

Therefore, considering the i.i.d. sequence



(r)

≤m≤η

(r+1)

−1

f (X

)(r ≥ 1), (10.4)

one has, by the classical SLLN (see Appendix), with probability 1

lim

N →∞

(N)



m=η

(1)

f (X

) = lim

N →∞



r=1

= EY

= (1/π

)

fdπ. (10.5)

Letting N = N

− 1, where N

= sup{r ≥ 0: η

(r)

≤ n}, one has

lim

n→∞

− 1

)



m=η

(1)

f (X

) = (1/π

)

fdπ a.s. (10.6)

Write

n + 1



m=0

f (X

) =

n + 1

η(1)

−1



m=0

f (X

)

− 1

n + 1

•

− 1

)

−1



m=η

(1)

f (X

)

n + 1



m=η

)

f (X

)

= I

+ I

, say. (10.7)

Now I

→ 0 a.s., as n →∞. I

is bounded by

n+1



+1)

−1

m=η

)

| f (X

)|≤

(1/N

, where Z



(r)

≤m≤η

(r+1)

−1

| f (X

)|. By (10.3), Z

/r → 0

a.s., as r →∞(see Exercise 8.2). Hence Z

→ 0 a.s., as n →∞.

Also, I

converges a.s. to

fdπ ,asn →∞by (10.6), and the fact

(n + 1)/(N

− 1) → E

(= 1/π

) a.s. (use (10.6) with f ≡ 1). Thus

the left hand side of (10.7) converges a.s. to

fdπ .

Remark 10.1 Note that (10.2) allows one to estimate π from observa-

tions, i.e.,

≈

n + 1

#{m:0≤ m ≤ n, X

= j }∀j ∈ S, a.s., (10.8)

2.10 Strong Law of Large Numbers and Central Limit Theorem 187

where ≈ indicates that the difference between the two sides goes to zero.

A special case of the next theorem (Theorem 10.2) provides one with a

fairly precise estimate of the error in the estimation (10.8).

Example 10.1 Consider the Ehrenfest model (Example 8.3). In view of

(8.38), one has the limit (10.2) given by



j=0

f ( j)(

−2d

In order to prove the CLT we ﬁrst need the following extension of the

classical CLT (see Appendix) to the sum of a random number of i.i.d.

summands.

Proposition 10.1 Let X

( j ≥ 1) be i.i.d. with E X

= 0,EX

= σ

(0 <σ

< ∞). Let ν

(n ≥ 1) be a sequence of nonnegative random

variables satisfying

→ α in probability, as n →∞, (10.9)

for some constant α>0. Then



j=1

√

converges in distribution

to N(0,σ

) as n →∞.

A proof of this proposition is given under Complements and Details.

We will write L

−→

to denote convergence in distribution.

Theorem 10.2 (CLT for Markov chains) In addition to the hypothesis

of Theorem 10.1, assume EY

< ∞, where Y

(r ≥ 1) is given by (10.4).

Then, whatever be the distribution of X

√

n + 1



m=0

( f (X

) −

fdπ ) L

−→

N (0,δ

), as n →∞, (10.10)

where δ

= π

var(



(2)

−1

m=η

(1)

( f (X

) −

fdπ ).

Proof. Write

f = f −

fdπ ,



(r+1)

−1

m=η

(r)

f (X

), S



r=1

Let N

= inf{r ≤ n: η

(r)

≤ n}, where η

(r)

= η

(r)

as above. Then N

/n →

> 0 a.s., as n →∞(as in the proof of Theorem 10.1, or see (8.1) and

188 Markov Processes

(8.4)). Therefore, by Proposition 10.1,

√

≡

√



r=1

−→

N (0,σ

), as n →∞, (10.11)

where σ

= E

≡ varY

. Now write, as in (10.7),

√

n + 1



m=0

f (X

) =

√

n + 1

(1)

−1



m=0

f (X

) +

− 1

n + 1

√

− 1

−1

√

n + 1



m=η

)

f (X

)

= J

+ J

, say. (10.12)

Now J

→ 0 a.s., as n →∞. J

converges in distribution to

N (0,δ

) by Proposition 10.1, noting that

− 1)/(n + 1)

converges a.s. to

√

. Finally, |J

|≤(n + 1)

−1/2

[



(1)

−1

m=0

f (X

)|+

max{



η(N

+1)

−1

m=η(N

)

f (X

)|:1≤ r ≤ n − 1}]. To prove that this converges

to 0 in probability, it is enough to show that for an i.i.d. sequence U

(r ≥ 1) with ﬁnite second moment, n

−1/2

max{|U

|:1≤ r ≤ n}→0in

probability. To prove this, write M

:= max{|U

|:1≤ r ≤ n}. For any

given ε>0, writing i.o. for inﬁnitely often or “inﬁnitely many n,” one

has (Exercise 10.1),

P(n

−1/2

>εi.o.)= P(M

≥ n

1/2

ε i.o.) = P(|U

|≥n

1/2

ε i.o.)

≤

∞



n=N

P(|U

|≥n

1/2

ε)=

∞



n=N

P(U

/ε

≥n)→0asN →∞.

For,

∞



n=1

P(U

/ε

≥ n) ≤ E(U

/ε

) < ∞.

Exercise 10.1 (a) Show that {M

≥ n

1/2

ε i.o.}={|U

|≥n

1/2

ε i.o.}.

(b) If V is nonnegative, then show that EV ≥



∞

n=1

P(V ≥ n).

[Hint:

EV ≥

∞



n=1

(n − 1)P(n − 1 ≤ V < n)

∞



n=1

(n − 1)[P(V ≥ n − 1) − P(V ≥ n)]

2.10 Strong Law of Large Numbers and Central Limit Theorem 189

= lim

N ↑∞



n=2

(n − 1)[P(V ≥ n − 1) − P(V ≥ n)]

= lim

N ↑∞

[



n=2

P(V ≥ n)



n=2

(n − 1)P(V ≥ n − 1) −



n=2

nP(V ≥ n)]

= lim

N ↑∞





n=2

P(V ≥ n) + P(V ≥ 1) − NP(V ≥ N )



= lim

N ↑∞





n=1

P(V ≥ n) − NP(V ≥ N )



∞



n=1

P(V ≥ n)

Note that NP(V ≥ N) ≤ EV1

{V ≥N }

→ 0asN →∞.

Example 10.2 Consider the two-state model of Example 3.1. Let η be

the ﬁrst return time to 0. Then the distribution of η

, starting at 0, is

given by

(η

= 1) = P(X

= 0 | X

= 0) = 1 − p,

(η

= 2) = P(X

= 1, X

= 0 | X

= 0) = pq,

(η

= k) = P(X

= 1, X

= 1,...,X

k−1

= 1, X

= 0 | X

= 0)

= p(1 − q)

k−2

q = pq (1 − q)

k−2

(k ≥ 2). (10.13)

Therefore (see Exercise 10.2),

= 1(1 − p) +

∞



k=2

kpq(1 −q)

k−2

= 1 − p + pq

∞



k=2

{1 + (k − 1)}(1 − q)

k−2

= 1 − p + pq





+ pq





= 1 +

p + q

, (10.14)

which accords with the facts that π

= 1/E

(see (8.14)) and π

q/(p + q) (see Example 3.1, or calculate directly from the invariance

Equation (3.10)).

190 Markov Processes

Now, let f = 1

{0}

. Then, by Theorem 10.1,

lim

n→∞

n + 1

= f (0)π

+ f (1)π

= 1π

+ 0π

= π

p + q

a.s., (10.15)

where N

is the number of visits to the state 0 in time n.

Next, we apply Theorem 10.2 to the same function f = 1

{0}

. Let η

(r)

be the r th return time to 0. Then E

f = 1π

+ 0π

= π

= q/( p + q),

f = 1

{0}

− q/( p + q), Y

≡ 1 (see (10.4)), and

≡

(2)

−1



m=η

(1)

f (X

) = 1 − (q/(p + q))



(2)

− η

(1)



. (10.16)

Since the distribution of η

(2)

− η

(1)

, starting from an arbitrary initial state,

is the same as the distribution of η

, starting from state 0,

var(

) =



p + q



var

(η

) =



p + q





− (E

)



(10.17)

Using (10.13), we get (see Exercise 10.2)

= 1

(1 − p ) +

∞



k=2

pq (1 − q)

k−2

= 1 − p + pq[k(k − 1) + (k − 1) + 1](1 − q)

k−2

= 1 − p + pq





= 1 +

2p + pq

+ 2 p + pq

. (10.18)

Therefore, by (10.14) and (10.17),

var

(η

) =

+ 2 p + pq − ( p + q)

p(2 − p − q)

var(

) =

p(2 − p − q)

(p + q)

. (10.19)

Since π

= q/( p + q), one has, by Theorem 10.2,

√

n + 1



−



n + 1



q/(p + q)



→ N



pq (2 − p − q)

(p + q)



(10.20)

2.11 Markov Processes on Metric Spaces 191

as n →∞. Note that, in the special case p = q = 1/2, f (X

) ≡ 1

=0}

(m ≥ 1) are independent symmetric Bernoulli (since the transition prob-

abilities are all equal to 1/2, and they do not depend on the state). There-

fore,



m=1

f (X

) is a symmetric binomial B(n, 1/2). The limiting vari-

ance in this case is 1/2(1 − 1/2) = 1/4, the same as given by (10.20)

with p = q = 1/2.

Exercise 10.2 Suppose |a| < 1. Then the geometric series equals



∞

r=0

= (1 −a)

−1

. By term-by-term differentiation with re-

spect to a show that (i)



∞

r=1

r−1

≡



∞

k=2

(k − 1)a

k−2

= (1 −a)

−2

(ii)



∞

r=1

r(r − 1)a

r−2

≡



∞

r=2

r(r − 1)a

r−2

= 2(1 −a)

−3

2.11 Markov Processes on Metric Spaces:

Existence of Steady States

We continue our study of Markov processes on general state spaces, but

now with the relatively mild restriction that the spaces be metric. The

focus here is to provide a criterion for the existence of an invariant prob-

ability, not necessarily unique, under simple topological assumptions.

Throughout this section, unless otherwise stated, (S, d) is a metric

space and S the Borel sigmaﬁeld on S. We will denote by C

(S) the

class of all real-valued bounded continuous functions on S.

Deﬁnition 11.1 A transition probability p(x, dy)on(S, S) is said to

have the Feller property,orisweakly continuous, if for every continuous

bounded real-valued function f on S the function

x → Tf(x):=

f (y) p(x, dy), ( f ∈ C

(S)) (11.1)

is continuous.

Example 11.1 (Markov chains) Let S be countable and d(x, y) = 1if

y = x, d(x, x) = 0 for all x, y ∈ S. Then the Borel sigmaﬁeld on S is

the class S of all subsets of S, since every subset of S is open. Thus every

bounded function on S is continuous. Hence every transition probability

of a Markov chain has the Feller property.

Example 11.2 (Random dynamical systems) Let (S, d) be an arbitrary

metric space and  ={g

, g

,...,g

} a set of continuous functions on

192 Markov Processes

S into S. Let p

> 0(1≤ i ≤ k),



i=1

= 1. For each n ≥ 1, let α

denote a random selection from  with Prob(α

= g

) = p

(1 ≤ i ≤ k),

and assume that {α

: n ≥ 1} is an i.i.d. sequence. For each initial X

independent of {α

: n ≥ 1} (e.g., X

= x for some s ∈ S), deﬁne

= α

≡ α

), X

= α

≡ d

),...,

= α

n−1

···α

≡ α

n−1

)(n ≥ 1). (11.2)

Then {X

: n ≥ 0} is a Markov process on S, with the transition

probability

p(x, B) = Prob(α

x ∈ B) =



i=1

−1

(B)

(x). (11.3)

If f ∈ C

(S), then

Tf(x) = Ef(α

x) =



i=1

f (g

(x)) ≡



i=1

( f ◦ g

)(x), (11.4)

which is clearly continuous on S. Hence p(x, dy) has the Feller property.

A more general version of this is considered in the next chapter.

Deﬁnition 11.2 A sequence of probability measures P

(n ≥ 1) on a

metric space (S, d) is said to converge weakly to a probability measure

P on S if

lim

n→∞

fdP

fdP ∀ f ∈ C

(S). (11.5)

Example 11.3 (Classical CLT) The classical CLT says that the se-

quence of distributions P

of n

−1/2

+···+X

), where X

, n ≥ 1,

are i.i.d. with mean vector O and a ﬁnite covariance matrix V, converges

weakly to the normal distribution N (O, V) with mean vector O and co-

variance matrix V.

As a matter of notation, p

(0)

(x, dy) = δ

(dy), i.e., p

(0)

(x, {x}) = 1.

Correspondingly, T

is the identity map on B(S): T

f = f .

The basic result of this section may now be stated.

Theorem 11.1 Let p(x, dy) be a transition probability with the Feller

property on a metric space (S, d).