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

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

3.6 Applications 273

F, G, namely, [G.1] and [P.1]–[P.4] are satisﬁed here and, by Theo-

rem 6.1, the distribution of X

(x) converges exponentially fast in the

Kolmogorov distance to a unique invariant probability, for every initial

x ∈ (0, 1).

3.6.4 Comparative Dynamics

Let

F be a continuous map on [c, d] (into [c, d]). For each ε ∈ (0, 1)

consider the Markov process X

, X

= α

n−1

···α

(n  1), where

{α

: n  1} is an i.i.d. sequence of maps on [c, d] independent of X

such that

Prob(α

F) = 1 − ε. (6.5)

We say a probability measure µ is

F-invariant if

h(x)µ(dx) =

F(x))µ(dx) ∀ continuous h on [c, d]. (6.6)

Note that (6.6) implies

h(x)µ(dx) =

(x))µ(dx) for all n ≥ 1

and all continuous h on [c, d]. In particular, if z

is a unique ﬁxed point

F and it is attractive, in the sense that

(x) → z

∀x ∈ [c, d], then

iterating (6.6), one gets

h(x)µ(dx) =

(x))µ(dx) → h(z

)as

n →∞. This implies µ = δ

. Conversely, for µ to be a unique

F-

invariant probability, there must exist a unique ﬁxed point z

, and no

other ﬁxed or periodic points; and in this case µ = δ

Theorem 6.2 Suppose that for each ε ∈ (0, 1), π

is an invariant proba-

bility of X

. Then every weak limit point π of π

as ε ↓ 0 is

F-invariant. If

µ = δ

is the unique

F-invariant probability, then π

converges weakly

to µ as ε ↓ 0.

Proof. Since the set of probability measures on [c, d] is a compact

metric space under the weak topology (see Lemma 11.1 in Chapter 2),

consider a limit point π of π

as ε ↓ 0. Then there exists a sequence

↓ 0as j ↑∞such that π

→ π weakly. By invariance of π

, for

every real-valued continuous function h on [c, d], one has

[c,d]

h(x)π

(dx) =

[c,d]



[c,d]

h(y)p

(x, dy)



(dx), (6.7)

274 Random Dynamical Systems

where p

(x, dy) is the transition probability of the Markov process

(n ≥ 0) above with ε = ε

. Note that p

(x, {

F(x)}) ≥ 1 −ε

. Hence

the right-hand side in (6.7) equals

[c,d]

[(1 − ε

)h(

F(x)) +δ

(x)]π

(dx), (6.8)

where δ

(x) = ε

E[h(α

x) | α

=

F], |δ

(x)|≤ε

(max

|h(y)|).

Therefore,

[c,d]

h(x)π

(dx) = (1 −ε

)

[c,d]

F(x))π

(dx)

[c,d]

(x)π

(dx)

→

[c,d]

F(x))π(dx)asε

→ 0, (6.9)

since π

→ π weakly. On the other hand, again by this weak conver-

gence, the left-hand side of (6.9) converges to

[c,d]

h(x)π(dx). There-

fore,

[c,d]

h(x)π(dx) =

[c,d]

F(x))π(dx). (6.10)

In other words, π is

F-invariant. If there is a unique

F-invariant prob-

ability µ, one has π = µ. Since this limit is the same whatever be the

sequence ε

↓ 0, the proof is complete.

Remark 6.2 Suppose

F and

G are monotone and continuous,

Prob(α

F) = 1 − ε and Prob(α

G) = ε, and that the process X

in (6.5) satisﬁes the splitting condition (H). Then the invariant probabil-

ity π

of X

is unique. Suppose ε is small. Then, whatever be the initial

state X

, the distribution of X

is approximated well (in the Kolmogorov

distance) by π

,ifn is large. On the other hand, π

is close to δ

(in the

weak topology) if z

is the unique attractive ﬁxed point of

F in the sense

of Theorem 6.2. Thus X

would be close to z

in probability if ε is small

and n is large.

Remark 6.3 Theorem 6.2 holds on arbitrary compact metric spaces in

place of [c, d]. There is a broad class of dynamical systems F on com-

pact metric spaces S, each with a distinguished F-invariant probability

3.7 Contractions 275

π whose support is large and to which the invariant probability π

the perturbed (random) dynamical system converges as the perturbation,

measured by ε, goes to 0. Such measures π are sometimes called Kol-

mogorov measures,orSinai–Ruelle–Bowen (SRB) measures. See, for

example, Kifer (1988) for precise statements and details. For similar

results for the case of quadratic maps F

(x) = θ x(1 − x)(x ∈ [0, 1]),

see Katok and Kifer (1986).

3.7 Contractions

3.7.1 Iteration of Random Lipschitz Maps

In this section (S, d) is a complete separable metric space. A map f from

S into S is Lipschitz if for some ﬁnite L > 0,

d( f (x), f (y)) ≤ Ld(x, y)

for all x, y ∈ S. Let  be a family of Lipschitz maps from S into S.

Let {α

: n ≥ 1} be an i.i.d. sequence of random Lipschitz maps from

. Denote by L

(k ≥ j), the random Lipschitz coefﬁcient of α

···α

i.e.,

(·):= sup {d(α

···α

x,α

···α

y)/d(x, y): x = y}. (7.1)

As before (see Remark 4.1), X

(x) = α

···α

x, and let Y

(x) =

···α

x denote the backward iteration (n ≥ 1; x ∈ S). Note that, for

every n ≥ 1, X

(x) and Y

(x) have the same distribution for each x, and

we denote this by

(x)

= Y

(x).

Before deriving the general result of this section, namely, Theorem 7.2,

we ﬁrst state and prove the following simpler special case, which sufﬁces

for a number of applications.

Theorem 7.1 Let (S, d) be compact metric, and assume

−∞ ≤ E log L

< 0, for some r ≥ 1. (7.2)

Then the Markov process X

has a unique invariant probability and is

stable in distribution.

276 Random Dynamical Systems

Proof. First assume (7.2) with r = 1. A convenient distance metrizing

the weak topology of P(S) is the bounded Lipschitzian distance d

(see Complements and Details, Chapter 2, (C11.33)),

(µ, ν) = sup



)

fdµ −

fdν

)

: f ∈ L



L :={f : S →

f (x) − f (y)

≤ 1∀x, y,

f (x) − f (y)

≤ d(x, y) ∀x, y}. (7.3)

By Prokhorov’s theorem (see Complements and Details, Chapter 2, The-

orem C11.5), the space (P(S), d

) is a compact metric space. Since

∗

is a continuous map on this latter space, due to Feller continuity

of p(x, dy), it has a ﬁxed point π – an invariant probability. To prove

uniqueness of π and stability, write L

= L

(see (7.1)) and note that for

all x, y ∈ S, one has

d(X

(x), X

(y)) ≡ d(α

···α

x,α

···α

≤ L

d(α

n−1

···α

x,α

n−1

···α

···

≤ L

n−1

···L

d(x, y) ≤ L

n−1

···L

M, (7.4)

where M = sup{d(x, y): x, y ∈ S}. By the strong law of large numbers,

the logarithm of the last term in (7.4) goes to −∞ a.s. since, in view of

(7.4) (with r = 1),



j=1

log L

→ E log L

< 0. Hence

sup

x,y∈S

d(X

(x), X

(y)) → 0a.s. as n →∞. (7.5)

Let X

be independent of (α

)

n≥1

and have distribution π. Then (7.5)

yields

sup

x∈S

d(X

(x), X

)) → 0a.s. asn→∞. (7.6)

Since X

(x) has distribution p

(n)

(x, dy) and X

) has distribution π,

one then has (see (7.3))

(n)

(x, ·),π) = sup{

Ef(X

(x)) − Ef(X

))

: f ∈ L}

≤ Ed(X

(x), X

))}→0asn →∞. (7.7)

This completes the proof for the case r = 1.

3.7 Contractions 277

Let now r > 1 (in (7.2)). The above argument applied to p

(r)

(x, dy),

regarded as a one-step transition probability, shows that for every

x ∈ S,ask →∞, p

(kr )

(x, ·) converges in d

-distance (and, therefore,

weakly) to a probability π that is invariant for p

(r)

(·, ·). This implies

that T

∗kr

µ → π (weakly) for every µ ∈ P(S). In particular, for each

j = 1, 2,...,r − 1,

(kr +j )

(x, ·) ≡ T

∗kr

( j)

(x, ·) → π as k →∞. That is, for every

x ∈ S,

(n)

(x, ·) converges weakly to π as n →∞. (7.8)

In turn, (7.8) implies T

∗n

µ → π weakly for every µ ∈ P(S). Therefore,

π is the unique invariant probability for p(·, ·) and stability holds.

Remark 7.1 The last argument above shows, in general, that if for some

r > 1, the skeleton Markov process {X

: k = 0, 1,...} has a unique

invariant probability π and is stable, then the entire Markov pro-

cess {X

: n = 0, 1,...} has the unique invariant probability π and is

stable.

Exercise 7.1 A direct application of Theorem 7.1 leads to a strengthen-

ing of the stability results in Green and Majumdar (Theorems 5.1–5.2,

1975) who introduced (i.i.d.) random shocks in the Walras-Samuelson

tatonnement.

We now turn to the main result of this section, which extends Theorem

7.1 and which will ﬁnd an important application in Chapter 4.

Theorem 7.2 Let S be a complete separable metric space with metric d.

Assume that (7.2) holds for some r ≥ 1 and there exists a point x

∈ S

such that

E log

d(α

···α

, x

) < ∞. (7.9)

Then the Markov process X

(x):= α

···α

x (n ≥ 1) has a unique in-

variant probability and is stable in distribution.

Proof. First consider the case r = 1 for simplicity. For this case, we

will show that the desired conclusion follows from the following two

assertions:

278 Random Dynamical Systems

(a) sup{d(Y

(x), Y

(y)): d(x, y) ≤ M}→0 in probability as n →

∞, for every M > 0.

(b) The sequence of distributions of d(X

), x

), n ≥ 1, is rela-

tively weakly compact.

Assuming (a), (b), note that for every real-valued Lipschitz f ∈ L (see

(7.3)), one has for all M > 0,

sup

ρ(x,y)≤M

Ef(X

(x)) − Ef(X

(y))

≤ sup

ρ(x,y)≤M

E[ρ(X

(x), X

(y)) ∧ 1] → 0 (7.10)

as n →∞, by (a) and Lebesgue’s dominated convergence theorem. Also,

Ef(X

n+m

)) − Ef(X

))

Ef(Y

n+m

)) − Ef(Y

))

≡|Ef(α

···α

n+1

···α

n+m

) − Ef(α

···α

≤ E[d(α

···α

n+1

···α

n+m

,α

···α

) ∧ 1]. (7.11)

Foragivenn and arbitrary M > 0, divide the sample space into the

disjoint sets:

(i) B

={d(α

n+1

···α

n+m

, x

) ≥ M}

and

(ii) B

={d(α

n+1

···α

n+m

, x

) < M}.

The last expectation in (7.11) is no more than P(B

)onB

On B

, denoting for the moment X = α

n+1

···α

n+m

, one has

d(α

···α

n+1

···α

n+m

,α

···α

) ≡ d(α

···α

X,α

···α

)

≡ d(Y

(X), Y

)) ≤ sup{d(Y

(x), Y

(y)): d(x, y) ≤ M}=Z ,say.

The last inequality holds since, on B

, d(X, x

) ≤ M. Now, for every δ>

0, E(Z ∧ 1) = E(Z ∧ 1 ·1

{Z>δ}

) + E(Z ∧ 1 ·1

{Z≤δ}

) ≤ P(Z >δ) + δ.

Hence,

Ef(X

n+m

)) − Ef(X

))

≤ P(d(α

n+1

···α

n+m

, x

) ≥ M)

+P(sup{d(Y

(x), Y

(y)) : d(x, y) ≤ M} >δ) +δ. (7.12)

Fix ε>0, and let δ = ε/3. Choose M = M

such that

P(d(α

···α

, x

) ≥ M

) <ε/3 for all m = 1, 2,.... (7.13)

3.7 Contractions 279

This is possible by (b). Now (a) implies that the middle term on the

right in (7.12) goes to zero as n →∞. Hence (7.12), (7.13), and

(a) imply that there exists n

such that for all m = 1, 2,..., and

f ∈ L,

Ef(X

n+m

)) − Ef(X

))

<ε for all n ≥ n

. (7.14)

In other words, recalling deﬁnition (7.3) of the bounded Lipschitzian

distance d

(µ, ν),

sup

m≥1

(n+m)

, dy), p

(n)

, dy)) → 0asn →∞. (7.15)

This implies that p

(n)

, dy) is Cauchy in (P(S), d

) and, therefore,

converges weakly to a probability measure π(dy)asn →∞, by the com-

pleteness of (P(S), d

) (Theorem C11.6 in Complements and Details,

Chapter 2). Since, p(x, dy) has the Feller property, it follows that π is

an invariant probability. In view of (7.10) and (a), p

(n)

(x, dy) converges

weakly to π, for every x ∈ S. This implies that π is the unique invariant

probability.

It remains to prove (a) and (b).

To prove (a), recall L

= sup{d(α

x,α

y)/d(x, y): x = y}, and as in

(7.4),

d(Y

(x), Y

(y)) = d(α

···α

x,α

···α

≤ L

d(α

···α

,α

···α

≤···≤ L

···L

ρ(x, y)

≤ L

···L

M for all (x, y) such that d(x, y) ≤ M.

Take logarithms to get

sup

{(x ,y):d(x,y)≤M}

log d(Y

(x), Y

(y)) ≤ log L

+···

+log L

+ log M →−∞a.s. as n →∞, (7.16)

by the strong law of large numbers and (7.2). This proves (a). To prove

(b), it is enough to prove that d(α

...α

, x

) converges almost

280 Random Dynamical Systems

surely and, therefore, in distribution, to some a.s. ﬁnite limit (use

the fact that d(Y

), x

) = d(α

···α

, x

) and d(X

), x

) =

d(α

···α

, x

) have the same distribution). For this use the triangle

inequality to write

d(α

···α

n+m

, x

) − d(α

···α

, x

)

≤ d(α

···α

n+m

,α

···α

)

≤



j=1

d(α

···α

n+j

,α

···α

n+j −1

)

≤



j=1

···L

n+j −1

d(α

n+j

, x

). (7.17)

Let c :=−E log L

(> 0). First assume c is ﬁnite and ﬁx ε,0<ε<c.

It follows from (7.2) and the strong law of large numbers that there exists

(ω) such that, outside a P-null set N

log (L

···L



)







k=1

log L

< −(c − ε/2),

···L



)



< e

−(c−ε/2)

, L

···L



< e

−n



(c−ε/2)

∀n



≥ n

(·). (7.18)

In view of (7.9), with r = 1,

∞



k=1



log

d(α

, x

)

ε/2

> k



∞



k=1



log

d(α

, x

)

ε/2

> k



≤

E log

d(α

, x

)

ε/2

< ∞, (7.19)

since



∞

k=1

P(V > k) ≤ EV for every nonnegative random variable V

(see Exercise 10.1, Chapter 2).

Therefore, by the Borel–Cantelli lemma, there exists n

(ω) such that,

outside a P-null set N

d(α

, x

) ≤ e

kε/2

for all k ≥ n

(·). (7.20)

3.7 Contractions 281

Using (7.18) and (7.20) in (7.17), one gets

sup

m≥1

d(α

···α

n+1

···α

n+m

, x

) − d(α

···α

, x

)

≤

∞



j=1

−(n+j −1)(c−ε/2)

(n+j )ε/2

= e

c−ε/2

−n(c−ε)

∞



j=1

−j(c−ε)

for all n ≥ n

(·):= max{n

(·), n

(·)}, (7.21)

outside the P-null set N = N

∪ N

. Thus the left-hand side of (7.21)

goes to 0 almost surely as n →∞, showing that d(α

···α

, x

)

(n ≥ 1) is Cauchy and, therefore, converges almost surely as n →∞.

The proof of (b) is now complete if −E log L

< ∞.If−E log L

=∞,

then (7.18) and (7.21) hold for any c > 0. This concludes the proof of

the theorem for r = 1 (in (7.2)). Now, the extension to the case r > 1

follows exactly as in the proof of Theorem 7.1 (see Remark 7.1).

Remark 7.2 The theorem holds if P(L

= 0) > 0. The proof (for the

case E log L

=−∞) includes this case. But the proof may be made

simpler in this case by noting that for all sufﬁciently large n,sayn ≥

n(ω), X

(x) = X

(y) ∀x, y. (Exercise: Use Borel–Cantelli lemma to

show this.)

Remark 7.3 The moment condition (7.9) under which Theorem 7.2 is

derived here is nearly optimal, as seen from its specialization to the afﬁne

linear case in the next section. Under the additional moment assumption

< ∞, the stability result is proved in Diaconis and Freedman (1999)

(for the case r = 1), and a speed of convergence is derived. The authors

also provide a number of important applications as well as an extensive

list of references to the earlier literature.

3.7.2 A Variant Due to Dubins and Freedman

Stepping back for a moment, we see that the general criterion for the

existence of a unique invariant probability for the Markov process X

described by (2.1) and for its stability in distribution is given by the

282 Random Dynamical Systems

following two conditions, which only require α

to be continuous and

not necessarily Lipschitz. We have proved

Proposition 7.1 On a complete separable metric space, let α

(n ≥ 1)

be i.i.d. continuous. The Markov process X

(x) ≡ α

···α

x is stable in

distribution if

(a) sup{d(α

n−1

···α

x,α

n−1

···α

y): d(x, y) ≤ M}→0 in

probability, as n →∞, for every M > 0,

and

(b) for some x

∈ S, the sequence of distributions of d(X

), x

) ≡

d(α

···α

, x

) is relatively weakly compact.

When S is compact, then (b) is automatic, since the sequence

d(X

), x

) is bounded by the diameter of S, whatever be x

and n.

Obviously here one may simplify the statement of (a) by taking just one

M, namely, the diameter of S:

(a)



: diam(α

n−1

···α

S) → 0 in probability as n →∞.

The criterion (a)



is now used to prove the following basic result of

Dubins and Freedman (1966).

Theorem 7.3 Let (S, d) be compact metric and  the set of all contrac-

tions on S. Let Q be a probability measure on the Borel sigmaﬁeld of

 (with respect to the “supremum” distance) such that the support of

Q contains a strict contraction. Then the Markov process X

deﬁned

by (2.1) and (2.2) has a unique invariant probability and is stable in

distribution.

Proof. Let γ be a strict contraction in the support of Q, i.e.,

d(γ x,γy) < d(x, y)∀x = y.

As before, the jth iterate of γ is denoted by γ

. Since γ

j+1

S =

(γ S) ⊂ γ

S, it follows that γ

S decreases as j increases. Indeed

S decreases to ∩

∞

j=1

S = a singleton {x

}. (7.22)

To see this, ﬁrst note that the limit is nonempty, by the ﬁnite inter-

section property of (S, d), and the fact that γ

S is the continuous

image of a compact set S and therefore, closed (compact). Assume,

if possible, that there are points x

, y

in the limit set, x

= y

. Let