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

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

2.13 Complements and Details 233

Lipschitzian functions on S by

L(a, b) ={f : ω

(S)  a, | f (x) − f (y)|

 bd(x, y) for all x, y ∈ S}.

(C11.32)

Now deﬁne the bounded Lipschitzian distance d

, Q

) = sup

f ∈L(1,1)

)

fdQ

−

fdQ

)

, Q

∈ P(S)).

(C11.33)

Corollary C11.1 If S is a separable metric space, then d

metrizes the

weak topology on P(S).

Proof. By Proposition C11.1, L(1, 1) is a Q-uniformity class for every

probability measure Q on S. Hence if {Q

} is a sequence of probability

measures converging weakly to Q, then

lim

, Q) = 0. (C11.34)

Conversely, suppose (C11.34) holds. We shall show that {Q

} converges

weakly to Q. It follows from (C11.33) that

lim

)

fdQ

−

fdQ

)

=0 for every bounded Lipschitzian function f.

(C11.35)

For, if | f (x) − f (y)|

 bd(x, y) for all x, y ∈ S,

fdQ

−

fdQ= c





−





where c = max{ω

(S), b} and f



= f /c ∈ L(1, 1). Let F be any

nonempty closed subset of S.Wenowprove

lim

(F)  Q(F). (C11.36)

For ε>0 deﬁne the real-valued function f

on S by

(x) = ψ(ε

−1

d(x, F)) (x ∈ S), (C11.37)

where ψ is deﬁned on [0, ∞)by

ψ(t) =



1 − t if 0

 t  1,

0ift > 1.

(C11.38)

234 Markov Processes

Note that f

is, for every positive ε, a bounded Lipschitzian function

satisfying

(S)  1, | f

(x) − f

(y)| 

)

d(x, F) −

d(y, F)

)



d(x, y)(x, y ∈ S),

so that, by (C11.35)

lim

dQ (ε>0). (C11.39)

Since 1

 f

for every positive ε,

lim

(F)  lim

dQ (ε>0). (C11.40)

Also, lim

ε↓0

(x) = I

(x) for all x in S. Hence

lim

ε↓0

dQ = Q(F). (C11.41)

By Theorem C11.1, {Q

} converges weakly to Q. Finally, it is easy to

check that d

is a distance function on P(S).

Remark C11.2 Note that in the second part of the proof of the above

corollary, we have shown that a sequence Q

(n ≥ 1) of probability mea-

sures on a metric space (S, d) converges weakly to a probability measure

Q if

fdQ

→

fdQ∀ f ∈ L(1, 1). (That is, uniform convergence

over the class L(1, 1) was not used for this fact.)

The next result is of considerable importance in probability. To state

it we need a notion called “tightness.”

Deﬁnition C11.3 A subset  of P(S) is said to be tight if, for every

ε>0, there exists a compact subset K

of S such that

P(K

) ≥ 1 − ε ∀P ∈ . (C11.42)

Theorem C11.5 (Prokhorov’s theorem)

(a) Let (S, d) be a separable metric space. If  ⊂ P(S) is tight, then

its weak closure

 is compact (metric) in the weak topology.

2.13 Complements and Details 235

(b) If (S, d) is Polish, then the converse is true: for a set  to be con-

ditionally compact (i.e.,

 compact) in the weak topology, it is necessary

that  is tight.

Proof.

(a) Let

S =∪

∞

j=1

1/j

, where K

1/j

is a compact set determined from

(C11.42) with ε = 1/j. Then P(

S) = 1 ∀ P ∈ . Also

S is σ -compact

and so is its image

=∪

∞

j=1

h(K

1/j

) under the map h (appearing in

the proofs of Lemma C11.1 and Theorem C11.3), since the image of a

compact set under a continuous map is compact. In particular,

is a

Borel subset of [0, 1]

and, therefore, of

. Let  be tight and let 

be the image of  in

under h, i.e., 

={P

−1

: P ∈ }⊂P(

In view of the homeomorphism h:

S →

, it is enough to prove that 

is conditionally compact as a subset of P(

Since

is a Borel subset of

, one may take P(

) as a sub-

set of P(

), extending P in P(

) by setting P(

) = 0. Thus



⊆ P(

) ⊆ P(

). By Lemma C11.1, P(

) is compact metric

(in the weak topology). Hence every sequence {P

: n = 1, 2,...} in



has a subsequence {P

: k = 1, 2,...} converging weakly to some

Q ∈ P(

). We need to show Q ∈ P(

), that is Q(

) = 1. By Theo-

rem C11.1, Q(h(K

1/j

)) ≥ lim sup

k→∞

(h(K

1/j

)) ≥ 1 − 1/j (by hy-

pothesis, P(h(K

1/j

)) ≥ 1 − 1/j ∀ P ∈ 

). Letting j →∞, one gets

) = 1.

(b) Assume (S, d) is separable and complete, and  is relatively

compact in the weak topology. We ﬁrst show that given any sequence

of open sets G

↑ S, there exists, for every ε>0, n = n(ε) such that

P(G

n(ε)

) ≥ 1 − ε ∀P ∈ . If this is not true, then there exists ε>0 and

a sequence P

∈ (n = 1, 2,...) such that P

) < 1 − ε ∀n. Then,

by assumption, there exists a subsequence 1 ≤ n(1) < n(2) < ··· such

that P

n(k)

converges weakly to some Q ∈ P(S)ask →∞. But this would

imply, by Theorem C11.3, Q(G

) ≤ lim inf

k→∞

n(k)

) ≤ lim inf

k→∞

n(k)

) < 1 − ε, ∀n = 1, 2,... (Note that, for sufﬁciently large k,

n ≤ n(k) so that G

⊂ G

n(k)

). This leads to the contradiction Q(S) =

lim

n→∞

Q(G

) ≤ 1 − ε.

To prove  is tight, ﬁx ε>0. Due to separability of S, there exists

for each k = 1, 2,... a sequence of open balls B

n,k

of radius less than

1/k (n = 1, 2,...) such that ∪

∞

n=1

n,k

= S. Denote G

n,k

=∪

m=1

m,k

Then G

n,k

↑ S as n ↑∞, and, by the italicized statement in the preceding

236 Markov Processes

paragraph, one may ﬁnd n = n(k) such that P(G

n(k),k

) ≥ 1 − ε/2

∀P ∈

. Let A =∩

∞

k=1

n(k),k

. Then

A is totally bounded since, for each k,

there exists a ﬁnite cover of

A by n(k) balls

n,k

(1 ≤ n ≤ n(k)) each

of diameter less than 1/k. Hence, by completeness of S,

A is compact

(see Diendonn´e 1960, p. 56). On the other hand, P(

A) ≥ P( A) ≥ 1 −



∞

k=1

ε/2

= 1 − ε ∀P ∈ .

The following corollary (left as an exercise) is an easy consequence

of Theorem C11.5(b).

Corollary C11.2 Let (S, d) be a Polish space. Then (i) every ﬁnite

set  ⊂ P(S) is tight and (ii) if  comprises a Cauchy sequence in

(P(S), d

) then it is tight.

Perhaps the most popular metric on (P(S)istheProkhorov metric d

deﬁned by

(P, Q):= inf{ε>0: P(B)≤Q(B

) + ε, Q(B) ≤ P(B

) + ε∀B ∈S}.

(C11.43)

Proposition C11.2 Let (S, d) be a metric space. Then the following

will hold: (a) d

is a metric on P(S), (b) if d

, P) → 0, then P

converges weakly to P, and (c) if (S, d) is a separable metric space, then

if P

converges weakly to P, d

, P) → 0, i.e., d

metrizes the weak

topology on P(S).

Proof.

(a) To check that (i) d

(P, Q) = 0 ⇒ P = Q, consider the in-

equalities (within curly brackets in (C11.43)) for B = F closed.

Letting ε ↓ 0, one gets P(F) ≤ Q(F) and Q(F) ≤ P(F) ∀ closed

F. (ii) Clearly, d

(P, Q) = d

(Q, P). (iii) To check the trian-

gle inequality d

, P

) + d

, P

) ≥ d

, P

), let d

, P

) <

and d

, P

) <ε

. Then P

(B) ≤ P

) + ε

≤ P

((B

)

) +

+ ε

≤ P

+ε

) + ε

+ ε

∀B ∈ S and, similarly, P

(B) ≤

+ε

) + ε

+ ε

∀B ∈ S. Hence d

, P

) ≤ ε

+ ε

. This pro-

vides d

, P

) ≤ d

, P

) + d

, P

(b) Suppose d

, P) → 0. Let ε

→ 0 be such that d

, P) <

. Then, by the deﬁnition (C11.43), P

(F) ≤ P(F

) + ε

∀ closed F.

Hence lim sup P

(F) ≤ P(F) ∀ closed F, proving that P

converges

weakly to P.

2.13 Complements and Details 237

(P, Q) ≤ (d

(P, Q))

1/2

∀P, Q ∈ P(S). (C11.44)

Fix ε>0. For a Borel set B, the function f (x):= max{0, 1 −

−1

d(x, B)} is Lipschitz: | f (x) − f (y)|≤ε

−1

d(x, y),  f 

∞

≤ 1.

Hence ε f ∈ L(1, 1). For P, Q ∈ P(S), Q(B) ≤

fdQ (since f ≥

0, and f = 1onB) ≤

fdP+ ε

−1

(P, Q) (since d

(P, Q) ≥

ε fd(P − Q)|) ≤ P(B

) + ε

−1

(P, Q) (since f = 0 outside B

One may interchange P, Q in the above relations. Thus, if d

(P, Q) ≤

, d

(P, Q) ≤ ε. Since ε>0 is arbitrary, (C11.44) follows.

Now if P

converges weakly to P, one has d

, P) → 0(by

Corollary C11.1) and, in view of (C11.44) d

, P) → 0.

Theorem C11.6 Let (S, d) be a complete separable metric space. Then

(P(S), d

) is a complete separable metric space.

Proof. Suppose {P

: n ≥ 1}is a d

-Cauchy sequence. Then, by Corol-

lary C11.2, it is tight. Now Theorem C11.5 (Prokhorov’s theorem) im-

plies there exists a subsequence 1 ≤ n(1) < n(2) <...such that P

n(k)

converges weakly to some P ∈ P(S). Therefore, d

n(k)

, P) → 0as

k →∞, which in turn implies d

, P) → 0.

Remark C11.3 Theorem C11.3 holds with d

in place of d

. For this

one needs to show that a d

-Cauchy sequence is tight (see Dudley 1989,

p. 317).

The ﬁnal result in this section concerns the Kolmogorov distance.

Deﬁnition C11.4 Let P, Q be probability measures on (the Borel sig-

maﬁeld of )

, with distribution functions F, G, respectively. The Kol-

mogorov distance d

between P and Q is deﬁned by

(P, Q) = sup

x∈R

|F(x) − G(x)|. (C11.45)

Proposition C11.3

(a) Convergence in the Kolmogorov distance implies weak conver-

gence on P(

(b) (P(

), d

) is a complete metric space.

238 Markov Processes

Proof. Part (a) follows from Theorem C11.2. To prove part (b), let

(n ≥ 1) be a Cauchy sequence in the metric d

, with correspond-

ing distribution functions F

(n ≥ 1). Then F

converges uniformly

to a function G,say,on

, which is right-continuous. We need to

show that G is the distribution function of a probability measure.

Now, {P

: n ≥ 1} is tight. For given ε>0, one can ﬁnd n

such that

(x) − F

(x)|<ε/4k ∀x,ifn ≥ n

. One may ﬁnd b

, b

,...,b

large

and a

, a

,...,a

small such that F

, b

,...,b

) > 1 − ε/4k, and

, b

,...,b

i−1

, a

, b

i+1

,...,b

) <ε/4k ∀i = 1, 2,...,k. Then,

writing a = (a

,...,a

), b = (b

,...,b

), [a, b] = (a

, b

) ×···×

, b

) one has ∀n ≥ n

([a, b]) ≥ F

(b) −



i=1

,...,b

i−1

, a

, b

i+1

,...,b

)

≥ F

(b)−

−



i=1

,...,b

i−1

, a

, b

i+1

,...,b

≥ 1 −

−

− k

= 1 −

−

≥ 1 − ε.

Hence {P

: n ≥ 1}is tight. By Prokhorov’s theorem (Theorem C11.5),

there exists a sequence n

(k ≥ 1) such that P

converges weakly to

some probability measure P with distribution function F, say. Then

(x) → F(x) at all points of continuity x of F. Then F(x) = G(x)

for all such x. Since both F and G are right continuous, and since for

every x ∈ R

there exists a sequence x

of continuity points of F such

that x

↓ x, it follows that F(x) = G(x) ∀x. Thus G is the distribution

function of P, and d

, P) → 0.

Bibliographical Notes. On precise “rate of convergence to” the in-

variant distribution see Diaconis (1988) and the articles by Diaconis and

Strook (1991), and Fill (1991). An extension to continuous time Markov

process is in Bhattacharya (1999). For a useful survey of some results

on invariant distributions of Markov processes and their applications to

economics, see Futia (1982). To go beyond Example 8.1, see Radner and

Rothschild (1975), Radner (1986), Rothschild (1974), and Simon (1959,

1986). For results on characterization and stability of invariant distribu-

tions of diffusion process, see Khas’minskii (1960), Bhattacharya (1978),

and Bhattacharya and Majumdar (1980).

2.14 Supplementary Exercises 239

2.14 Supplementary Exercises

(1) Consider the following transition probability matrix:

p =





0.25 0.25 0.5

0.50.25 0.25

0.20.30.5





(a) Show that the invariant distribution of the matrix p is given by

π =





0.2963

0.2716

0.4321





(b) Note that

100





0.2963 0.2716 0.4321





(2) Consider the following transition probability matrix:

p =





0.40.60

0.20.40.4

00.70.3





(a) Show that the invariant distribution of the matrix p is given by

π =





0.175

0.525

0.3





(b) Verify that





0.28 0.48 0.24

0.16 0.56 0.28

0.14 0.49 0.37





100





0.175 0.525 0.3





240 Markov Processes

(3) Consider the following transition probability matrix:

p =







000.60.4

000.20.8

0.25 0.75 0 0

0.50.50 0







(a) Show that the invariant distribution of the matrix p is given by

π =







0.2045

0.2955

0.1818

0.3182







(b) Verify that







0.35 0.65 0 0

0.45 0.55 0 0

000.30.7

000.40.6







is given by



π =







0.4091

0.5909







(d) Note that







000.3636 0.6364

0.4091 0.5909 0 0







100







0.4091 0.5909 0 0

000.3636 0.6364







(4) Let Q = [q

] be a matrix with rows and columns indexed by the

elements of a ﬁnite or countable set U . Suppose Q is substochastic in

2.14 Supplementary Exercises 241

the sense that

≥ 0 and for all i,



≤ 1.

Let Q

= [q

(n)

] be the nth power so that

(

n+1

)



(

)

(

)

= δ



1ifi = j,

0ifi = j.

(a) Show that the row sums

(

)



(

)

satisfy σ

(

n+1

)

≤ σ

(

)

. Hence,

= lim

n→∞

(

)

= lim

n→∞



(

)

(14.1)

exist, and, show that



. (14.2)

[Hint: (i) σ

(

n+1

)



(

)

. (ii) If lim

n→∞

= x

and

≤ M

where



< ∞, then lim

n→∞



(b) Thus, σ

solve the system



j∈U

, i ∈ U,

0 ≤ x

≤ 1, i ∈ U. (14.3)

For an arbitrary solution

(

)

(

14.3

)

, show that x

≤ σ

. Thus, the σ

give the maximal solution to

(

14.3

)

[Hint: x



≤



= σ

(

)

, and x

≤ σ

(

)

for all i implies

that x

≤



(

)

= σ

(n+1)

. Thus, x

≤ σ

(n)

for all n by induction.]

To summarize:

[R.1] For a substochastic matrix Q, the limits

(

14.1

)

are the maximal

solution of

(

14.3

)

242 Markov Processes

] for i and j in U give a substochastic matrix Q. Then, σ

(

)

[

∈ U, t ≤ n

]

Letting n →∞,

= P

[

∈ U, t = 1, 2,...

]

, i ∈ U (14.4)

Then, [R.1] can be restated as follows:

[R.2] For U ⊂ S, the probabilities

(

)

(

14.4

)

are the maximal

solution of the system



j∈U

, i ∈ U,

0 ≤ x

≤ 1, i ∈ U. (14.5)

Now consider the system

(

14.5

)

with U = S −

{

}

for a single state



j=i

, i = i

0 ≤ x

≤ 1, i = i

. (14.6)

There is always a trivial solution to

(

14.6

)

, namely x

= 0.

Now prove the following:

[R.3] An irreducible chain is transient if and only if

(

14.6

)

has a

nontrivial solution.

[Hint: The probabilities

1 − ρ

= P

[

= i

, n ≥ 1

]

i = i

(14.7)

are, by [R.2], the maximal solution of

(

14.6

)

and hence vanish identically

if and only if

(

14.6

)

has no nontrivial solution.

Verify that

= p



i=i

If the chain is transient, ρ

< 1, hence ρ

< 1 for some i = i

]

Since the Equations

(

14.6

)

are homogeneous, the central question is

whether they have a nonzero solution that is nonnegative and bounded.

If they do, 0 ≤ x

≤ 1 is ensured by normalization.

(d) Review Example 6.2. For a random walk with state space

Z, con-

sider the set U =

{

0, 1, 2,...

}

. Then, consider the system

(

14.5

)