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

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

3.7 Contractions 283

δ := d(x

, y

). The continuous function (x, y) → d(γx,γy)/d(x, y)on

the compact set K

={(x, y): d(x, y) ≥ δ}(⊂ S × S) attains a maxi-

mum c < 1. Let x

, y

be two preimages of x

, y

, respectively, un-

der γ, i.e., γx

= x

,γy

= y

. Since γ , is a contraction, d(x

, y

) ≥

d(γx

,γy

) = d(x

, y

) = δ. Therefore, (x

, y

) ∈ K

and d(x

, y

) ≤

cd(x

, y

), or d(x

, y

) ≥ δ/c. In general, let x

, y

be two preimages

under γ of x

j−1

, y

j−1

, respectively. Then, by induction, d(x

, y

) ≥

d(x

j−1

, y

j−1

)/c ≥···≥d(x

, y

)/c

→∞as j →∞, which contra-

dicts the fact that S is bounded.

By the same kind of reasoning, one shows that

diam (γ

S) ↓ 0asj ↑∞. (7.23)

For, if (7.23) is not true, there exists δ>0 such that diam (γ

S) >δ>

0 for all j. Thus there exist x

, y

∈ γ

S such that d(x

, y

) ≥ δ,

which implies, using preimages, that there exist x

, y

∈ S satisfying

d(x

, y

) ≥ δ/c

→∞as j →∞, a contradiction.

Now ﬁx j and let γ

,γ

,...,γ

, n > j, be such that j consec-

utive members, say γ

i+1

,...,γ

i+j

, are within a distance ε from

γ, i.e., γ

i+k

− γ 

∞

<ε, k = 1,..., j , where 1 ≤ i + 1 < i + j 

n. We shall show

diam (γ

n−1

···γ

S) ≤ diam (γ

S) + 2 jε. (7.24)

For this note that the contraction γ

n−1

···γ

i+j+1

does not increase

the diameter of the set γ

i+j

···γ

i+1

···γ

S. Also, γ

i+j

···

i+1

(γ

···γ

S) ⊂ γ

i+j

···γ

i+1

Hence the left-hand side of (7.24) is no more than

diam (γ

i+j

···γ

i+1

S).

Now, whatever be x, y, one has, by the triangle inequality,

d(γ

i+j

···γ

i+2

i+1

x,γ

i+j

···γ

i+2

i+1

≤ 2ε + d(γ

i+j

···γ

i+2

γ x,γ

i+j

···γ

i+2

γ y).

Applying the same argument with γ x, γ y in place of x, y, and replacing

i+2

by γ , and so on, one arrives at (7.24).

We are now ready to verify (a)



. Choose δ>0 arbitrarily. Let j be

such that diam (γ

S) <δ/2. Let ε = δ/4 j, so that the right-hand side of

(7.24) is less than δ. Deﬁne the events

={α

j(m−1)+k

− γ 

∞

<ε∀k = 1, 2,..., j},(m = 1, 2,...).

(7.25)

284 Random Dynamical Systems

Note that P( A

) = b

, where b := P(



− γ



∞

<ε). Since γ is in the

support of Q, b > 0. The events A

(m = 1, 2,...) form an independent

sequence, and



∞

m=1

P(A

) =∞. Hence, by the second Borel–Cantelli

lemma, P(A

occurs for some m) ≥ P( A

occurs for inﬁnitely many

m) = 1. But on A

, diam (α

mj−1

···α

mj−j +1

S) <δ so that, with

probability 1, diam (α

···α

S) <δ for all sufﬁciently large n. Since

δ>0 is arbitrary, (a)



holds.

Remark 7.4 The proof given above is merely an ampliﬁcation of the

derivation given in the original article by Dubins and Freedman (1966).

It may be noted that this result does not follow from Theorem 7.1, since

one may easily construct strict contractions with the Lipschitz constant 1.

On the other hand, Theorems 7.1 and 7.2 apply to sets , which contain

(noncontracting) maps with one Lipschitz constant larger than 1 in the

support of Q, but still satisfy the criteria (a) and (b) for stability in

distribution.

3.8 Complements and Details

Sections 3.1, 3.2.

Proposition C1.1. Let S be a Borel subset of a Polish space and S

its Borel sigmaﬁeld. Let p(x, B)(x ∈ S, B ∈ S) be a transition prob-

ability on (S, S). Then there exists a set  of functions on S into S

and a probability measure Q on a sigmaﬁeld



on  such that (i)

the map (γ,x) → γ (x) on  × S into S is measurable with respect to

the sigmaﬁelds



⊗S (on  × S) and S (on S), and (ii) (2.3) holds:

p(x, C) = Q({γ ∈ : γ (x) ∈ C}) ∀x ∈ S, C ∈ S.

Proof. By a well-known theorem of Kuratowski (see Royden 1968,

p. 326), there exists a one-to-one Borel measurable map h on S onto

a Borel subset D of the unit interval [0, 1] such that h

−1

is Borel

measurable on D onto S. Hence one may, without loss of generality,

consider D in place of S and D = D ∩ B([0, 1]) in place of S. Since

one may deﬁne the equivalent (or corresponding) transition probabil-

ity

p(u, B):= p(h

−1

(u), h

−1

(B))∀u ∈ D, B ∈ D, it sufﬁces to prove

the desired representation for

p(u, B) on the state space (D, D). For

this purpose, let the distribution function of

p(u, dy)beF



):=

p(u, D ∩ [0, y



]), 0 ≤ y



≤ 1, u ∈ D. Deﬁne its inverse F

−1

(v):=

inf{y



∈ [0, 1]; F



) >v}. Let m denote the Lebesgue measure on

3.8 Complements and Details 285

[0, 1]. Then we check that

m({v ∈ [0, 1]: F

−1

(v) ≤ y}) ≥ m({v ∈ [0, 1]: F

(y) >v})

= F

(y), (u ∈ D, y ∈ [0, 1]) (C1.1)

and

m({v ∈ [0, 1]: F

−1

(v) ≤ y}) ≤ m({v ∈ [0, 1]: F

(y) ≥ v})

= F

(y), (u ∈ D, y ∈ [0, 1]). (C1.2)

To check the inequality in (C1.1) note that if F

(y) >v then (by the

deﬁnition of the inverse), F

−1

(v) ≤ y (since y belongs to the set over

which the inﬁmum is taken to deﬁne F

−1

(v)). The equality in (C1.1)

simply gives the Lebesgue measure of the interval [0, F

(y)). Conversely,

to derive (C1.2), note ﬁrst that if v = 1, then there exists in [0, 1] a

sequence y

↓ F

−1

(v), y

> F

−1

(v) ∀n. Then F

) >v ∀n and by

the right-continuity of F

, F

−1

(v)) ≥ v. Hence y ≥ F

−1

(v) implies

(y) ≥ v, proving the inequality in (C1.2), since m({1}) = 0.

Together (C1.1) and (C1.2) imply

m({v ∈ [0, 1]: F

−1

(v) ≤ y}) = F

(y)(u ∈ D, y ∈ [0, 1]). (C1.3)

Deﬁne  ={γ

: v ∈ [0, 1]}, where γ

(u) = F

−1

(v), u ∈ D. One may

then identify  with the label set [0, 1], and let



be the Borel sigmaﬁeld

of [0, 1], Q = m. With this identiﬁcation, one obtains

p(u, [0, y] ∩

D) = Q({γ : γ (u) ∈ [0, y] ∩ D}), y ∈ [0, 1], u ∈ D.

For complete details on measurability (i.e., property(i)) see Blumen-

thal and Corson (1972).

An interesting and ingenious application of i.i.d. iteration of ran-

dom maps in image encoding was obtained by Diaconis and Shasha-

hani (1986), Barnsley and Elton (1988), and Barnsley (1993). An image

is represented by a probability measure ν, which assigns mass 1/b to

each of the b black points. This measure ν is then approximated by the

invariant probability of a random dynamical system generated by two-

dimensional afﬁne maps chosen at random from a ﬁnite set using an

appropriate matching algorithm.

Section 3.5. (Nondecreasing Maps on



) For generalizations of Theo-

rem 5.1 to multidimension, we will use a different route, which is useful

in other contexts, for example, in proving a central limit theorem. In the

286 Random Dynamical Systems

rest of this section, we present a brief exposition of the method given in

Bhattacharya and Lee (1988), along with some amendments and exten-

sions, for an appropriate generalization of Theorem 5.1 to



(>1).

Theorem C5.1 is not a complete generalization of Corollary 5.2.

For the latter applies to i.i.d (continuous) monotone maps, while The-

orem C5.1 assumes the maps α

to be i.i.d. (measurable) monotone

nondecreasing. The proof given below easily adapts to i.i.d. (measur-

able) monotone nonincreasing maps as well, but not quite to the case in

which α

may be nondecreasing with positive probability and, at the same

time, nonincreasing with positive probability. See Bhattacharya and Lee

(1988), also Bhattacharya and Lee 1997 (correction)) and Bhattacharya

and Majumdar (1999b, 2004).

Let S be a Borel subset of



and α

an i.i.d. sequence of measurable

nondecreasing random maps on S into itself. Recall that for two vectors

x = (x

,...,x



) and y = (y

,...,y



)inR



, we write x ≥ y of x

≥ y

for all i. A map γ = (γ

)isnondecreasing if each coordinate map γ

nondecreasing, i.e., x ≥ y implies γ

(x) ≥ γ

(y). The signiﬁcant distinc-

tion and the main source of difﬁculty in analysis here is that, unlike the

one-dimensional case, the relation ≥is only a partial order. It is somewhat

surprising then that one still has an appropriate and broad generalization

of Theorem 5.1. To this effect let A be the class of all sets A of the form

A ={y ∈ S : φ(y) ≤ x}

φ continuous and nondecreasing on S into



, x ∈ R



(C5.1)

A generalization on P(S) of the Kolmogorov distance (5.3) is

(µ, ν):= sup

A∈A

|µ(A) −ν(A)|,(µ, ν ∈ P(S)). (C5.2)

Consider the following splitting condition:

) There exist χ

> 0(i = 1, 2), F

measurable subsets of



(i = 1, 2), x

∈ S, and a positive integer N such that

(1) F

⊂{γ ∈ 

: ˜γx ≤ x

∀x ∈ S}, Q

) = χ

(2) F

{γ ∈ 

: ˜γx ≥ x

∀x ∈ S}, Q

) = χ

. (C5.3)

As before for γ = (γ

,γ

,...,γ

) ∈ 

, ˜γ = γ

N −1

···γ

3.8 Complements and Details 287

We will show that, under (H

), Theorem 5.1 extends to a large class

of Borel sets S ⊂



. The problems that one faces here are

(a) T

∗

may not be a strict contraction on P(S) for the metric d

(b) (P(S), d

) may not be a complete metric space, and

implies weak conver-

gence.

Problems (b) and (c) are related, and are resolved by the following:

Lemma C5.1 Suppose S is a closed subset of



. Then (P(S), d

) is a

complete metric space, and convergence in d

implies weak convergence.

Proof. Let P

(n ≥ 1) be a Cauchy sequence in (P(S), d

). Let

the extension of P

to R



, i.e.,

(B) = P

(B ∩ S), where B is a Borel

subset. By taking φ in (C5.1) to be the identity map, it is seen that the

d.f.s F

are Cauchy in the uniform distance for functions on



The limit F on



is the d.f. of a probability measure

P on R



, and

converges weakly to

P on R



. On the other hand, P

(A) converges to

some P

∞

(A) uniformly ∀A ∈ A. It follows that P

∞

(A) =

P(A) for all

A = (−∞, x] ∩ S(∀x ∈



). To show that

P(S) = 1, recall that since

S is closed and P

(S) = 1 ∀n, by Alexandroff’s theorem (Chapter 2,

Complements and Details, Theorem C11.1), one has

P(S) ≥

lim

n→∞

(S) = lim

n→∞

(S) = 1.

Let P be the restriction of

P to S. Then P ∈ P(S), and we will show

that P

converges weakly to P on S. To see this let O be an arbitrary

open subset of S. Then O = U ∩ S, where U is an open subset of



and

lim

(O) = lim

(U) ≥

P(U) = P(O),

showing, again by Alexandroff’s theorem, that P

converges weakly to

P.NowP

◦ φ

−1

converges weakly to P ◦ φ

−1

for every continuous

nondecreasing φ on S. This implies (P

◦ φ

−1

)

∧

converges weakly to

(P ◦ φ

−1

)

∧

(use Alexandroff’s theorem with open set U ⊂ R



). But ap-

plying the same argument to the d.f.s of (P

◦ φ

−1

)

∧

as used above for

the d.f.s. of

(letting x in (C5.1) range over all of R



) and, since P

is Cauchy in (P(S), d

), the d.f.s of (P

◦ φ

−1

)

∧

converge to that of

(P ◦ φ

−1

)

∧

uniformly on R



. Thus P( A) = P

∞

(A) ∀A ∈ A, and

sup

A∈A

(A) − P(A)|→0.

288 Random Dynamical Systems

Problem (a) mentioned above is taken care of by deﬁning a new metric

on P(S). Let G

denote the set of all real-valued nondecreasing measur-

able maps f on S such that 0 ≤ f ≤ a (a > 0). Consider the metric

(µ, ν):= sup

f ∈G

)

fdµ −

fdν

)

(µ, ν ∈ P(S)). (C5.4)

Clearly,

(µ, ν) = ad

(µ, ν). (C5.5)

Also, the topology under d

is stronger than that under d

(µ, ν) ≥ d

(µ, ν). (C5.6)

To see this, note that the indicator 1

of the complement of every set

A ∈ A belongs to G

We are now ready to prove our main theorem of this section.

Theorem C5.1 Let S be a closed subset of



, and α

(n ≥ 1) an i.i.d.

sequence of nondecreasing random maps on S. If (H

) holds, then

∗n

µ, T

∗n

ν) ≤ (1 −χ

)

[n/N]

(µ, ν)(µ, ν) ∈ P(S), (C5.7)

where χ

:= min{χ

,χ

Also, there exists a unique invariant probability π on S for the Markov

process X

:= α

n−1

···α

, and

∗n

µ, π ) ≤ (1 − χ

)

[n/N]

, (µ ∈ P(S)). (C5.8)

Proof. Let 

:={γ ∈ 

: ˜γ(S) ⊂ (−∞, x

] ∩ S},



:={γ ∈ 

: ˜γ(S) ⊂ [x

, ∞) ∩ S},

where ˜γ = γ

···γ

for γ = (γ

,γ

, ···,γ

) ∈ 

. Let f ∈ G

Write

∗N

µ) −

∗N

ν)





f (˜γ x)Q

(dγ )



µ(dx)−





f (˜γ x)Q

(dγ )



ν(dx)



i=1



(x)µ(dx) −

(x)ν(dx)



, (C5.9)

3.8 Complements and Details 289

where

(x):=

\(F

∩F

)

f ( ˜γx)Q

(dγ ),

(x):=

\(F

∩F

)

f ( ˜γx)Q

(dγ ),

(x):=



\(F

∪F

)

f ( ˜γx)Q

(dγ ),

(x):=

∩F

)

f ( ˜γx)Q

(dγ ). (C5.10)

Note that, on F

∩ F

, ˜γ(x) = x

, so that the integrals of h

in (C5.9)

cancel each other. Also,

(x)µ(dx) −

(x)ν(dx) =



(x)ν(dx) −



(x)µ(dx),



(x):=

\(F

∩F

)

(1 − f ( ˜γx))Q

(dγ ).

Now h

(x) and h

(x) are nondecreasing, as is a

− h



(x), where

0 ≤ h

(x) ≤ f (x

)(Q

) − Q

∩ F

)) = a

0 ≤ h



(x) ≤ (1 − f (x

))(Q

) − Q

∩ F

)) = a

0 ≤ h

(x) ≤ 1 − Q

) − Q

) + Q

∩ F

) = a

Hence, h

∈ G

, a

− h



∈ G

, h

∈ G

, and, since

)

dµ −

dν

)

≤ d

(µ, ν) = a

(µ, ν)(i = 1, 3),

and

)



− h





dµ −



− h





dν

)

≤ d

(µ, ν) = a

(µ, ν)

it follows that

)

fd(T

∗N

µ) −

fd(T

∗N

ν)

)

dµ −

dν +

− h



) dµ −

− h



) dν

dµ −

dν

)

≤ (a

+ a

) d

(µ, ν), (C5.11)

290 Random Dynamical Systems

where

+ a

= f (x

)(Q

) − Q

∩ F

))

+(1 − f (x

)(Q

) − Q

∩ F

))

≤ max{Q

), Q

)}−Q

∩ F

and a

= 1 − Q

) − Q

) + Q

∩ F

). It follows that a

+ a

≤ 1 − χ

if χ

= Q

) ≥ Q

) = χ

, and a

+ a

≤ 1 − χ

if χ

≤ χ

. Thus a

+ a

≤ 1 − χ

. Hence we have

derived

∗N

µ, T

∗N

ν) ≤ (1 −χ

) d

(µ, ν), (µ, ν ∈ P(S)). (C5.12)

Also, ∀ f ∈ G

)

fd(T

∗

µ) −

fd(T

∗

ν)

)

g(x)µ(dx) −

g(x)ν(dx)

)

where g(x):=



f ( ˜γx)Q(dγ ), so that g ∈ G

. Thus

∗

µ, T

∗

ν) ≤ d

(µ, ν), (µ, ν ∈ P(S)). (C5.13)

Combining (C5.12) and (C5.13) one arrives at (C5.7). In particular,

this implies

∗n

µ, T

∗n

ν) ≤ (1 −χ

)

[n/N]

,(µ, ν ∈ P(S)). (C5.14)

Fix x ∈ S, and a positive integer r arbitrarily, and let µ = δ

,ν=

∗r

in (C5.14), where δ

is the point mass at x. Then T

∗n

µ =

(n)

(x, dy), T

∗n

ν = p

(n+r )

(x, dy), and (C5.14) yields

(n)

(x, dy), p

(n+r )

(x, dy)) ≤ (1 −χ

)

[n/N]

→ 0asn →∞.

(C5.15)

That is, p

(n)

(x, dy)(n ≥ 1) is a Cauchy sequence in (P(S), d

). By

completeness (see Lemma C5.1), there exists π ∈ P(S) such that

(n)

(x, dy),π(dy)) → 0asn →∞. Letting r →∞in (C5.15) one

gets

(n)

(x, dy),π(dy)) ≤ (1 − χ

)

[n/N]

. (C5.16)

Since this is true ∀x, one may average the left-hand side with respect to

µ(dx)toget

∗n

µ, π ) ≤ (1 − χ1

)

[n/N]

. (C5.17)

3.8 Complements and Details 291

It remains to show that π is the unique invariant probability for

p(x, dy). This follows from the Lemma C5.2.

Lemma C5.2 Let S be a Borel subset of R



, and α

(n ≥ 1) i.i.d. mono-

tone nondecreasing maps on the state space S. If p

(n)

(x, dy) converges

weakly to π as n →∞, ∀x ∈ S, then π is the unique invariant proba-

bility for p(x, dy).

Proof. Suppose ﬁrst that there exist a = (a

, a

,...,a

) and b =

, b

,...,b

)inS such that a ≤ x ≤ b ∀x ∈ S. Let Y

(x):=

···α

x. Then, as shown in Remark 5.1, Y

(a) ↑ Y as n ↑∞, and

(b) ↓ Y as n ↑∞. Therefore, p

(n)

(a, dy) converges weakly to the dis-

tribution of Y

, which must be π. Similarly, p

(n)

(b, dy) converges weakly

to the distribution of

Y , also π. Since Y ≤ Y , it now follows that Y = Y .

Let α be independent of {α

: n ≥ 1}, and have the same distribution Q.

Then, αY

(z) has the distribution p

(n+1)

(z, dy). Hence, ∀x ∈ R



(n+1)

(b, S ∩ [a, x]) = Prob(αY

(b) ≤ x) ≤ Prob(αY ≤ x)

p(z, S ∩ [a, x])π(dz) = Prob(αY

≤ x)

≤ Prob(αY

(a) ≤ x)

= p

(n+1)

a, S ∩ [a, x]). (C5.18)

By hypothesis, the two extreme sides of (C5.18) both converge to π (S ∩

[a, x]) at all points x of continuity of the d.f. of π . Therefore,

p(z, S ∩ [a, x])π (dz) = π(S ∩ [a, x]) (C5.19)

at all such x. From the right-continuity of the d.f. of π(C5.19) holds for

all x.

This implies that π is invariant. For, the two sides of (C5.19) are the

d.f.’s of α

and X

, respectively, where X

has distribution π , and

invariance of π just means α

and X

have the same distribution. If



is another invariant probability, then ∀n

(n)

(z, S ∩ [a, x])π



(dz) = π



(S ∩ [a, x]) ∀x. (C5.20)

But the integrand on the left converges to π(S ∩ [a, x]) as n →∞by

(C5.18). Therefore, the left-hand side converges to π(S ∩ [a, x]), show-

ing that π



= π .

292 Random Dynamical Systems

Finally, suppose there do not exist a and/or b ∈ S, which bound S

from below and/or above. In this case, one can ﬁnd an increasing home-

omorphism of S onto a bounded set S

. It is then enough to consider S

Let a

:= inf{x

: x = (x

,...,x

) ∈ S

},1≤ i ≤ k, and b

:= sup{y

y = y

,...,y

) ∈ S

}. Let a = (a

, a

,...,a

), b = (b

, b

,...,b

For simplicity, assume N = 1. Let 

:={γ ∈ : γ x ≤ x

∀x ∈ S



:={γ ∈ : γ x ≥ x

∀x ∈ S

}. Extend γ ∈ 

\(

∩ 

) by set-

ting γ (a) = a, γ (b) = x

. Extend γ ∈ 

∩ 

to S

∪{a, b} by set-

ting γ (a) = x

= γ (b). Similarly extend γ ∈ 

\(

∩ 

) by setting

γ (a) = x

, γ (b) = b.Forγ/∈ 

∪ 

, let γ (a) = a,γ(b) = b.Onthe

space S

∪{a, b} the splitting condition (H

) holds, and the proof given

above shows that π is the unique invariant probability on S

∪{a, b}.

Since π(S

) = 1, the proof is now complete. If one of a, b belongs to S

while the other does not, simply omit the speciﬁcation at the point that

belongs to S

Remark C5.1 The assumption of continuity of i.i.d. monotone maps in

Corollary 5.2 is used only to verify the second hypothesis (5.12) of the

splitting hypothesis H

. In the absence of continuity of ˜γ (for γ ∈ 

˜γ

−1

A ={z ∈ S: ˜γ.φ(z) ≤ x}may not belong to A for A in A of the form

A ={y ∈ S: φ(y) ≤ x}, where φ is continuous and monotone. Hence we

are unable to infer (5.12) without the continuity of ˜γ for γ ∈ 

. In the

one-dimensional case, a direct proof of the result is given (see the proof

of Corollary 5.1), which we are unable to extend to higher dimensions.

Remark C5.2 The assumption (in Corollary 5.2 and Theorem C5.1) that

S be a closed subset of



may be relaxed somewhat. For example, if

there exists a homeomorphism h : S → S



where h is a strictly increasing

map and S



is a closed subset of R

, then by relabeling S by S



, Corollary

5.2 and Theorem C5.1 hold for the state space S. This holds, for example,

to sets such as S = (0, 1)



,[0, 1)



,(0, 1]



, or (0, ∞)



, which are mapped

(by appropriate continuous strictly increasing h) homeomorphically to



= R



,[0, ∞)



,(−∞, 0]



, R



, respectively. However, the following is

an example of an open subset S of

R on which (P(S), d

) is not complete.

Note that in one dimension, d

is the Kolmogorov distance k

(see (5.3)).

Example C5.1 (B.V. Rao). Let C ⊂ [0, 1] be the classical Cantor

“middle-third” set, and S =

R\C. Let X be a random variable having