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

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

1.3 Complexity 13

(ii) If x ∈ℵ



and y ∈ ℘(I )

lim sup

n→∞

|α

(x) − α

(y)| > 0.

Proof of [1].

Step 1. Let G be a real-valued continuous function on an interval I . For

any compact subinterval I

of G(I ) there is a compact subinterval

Q of I such that G(Q) = I

Proof of Step 1. One can ﬁgure out the subinterval Q directly as fol-

lows. Let I

= [G(x), G(y)] where x, y are in I. Assume that x < y.

Let r be the last point of [x, y] such that G(r) = G(x); let s be the

ﬁrst point after r such that G(s) = G(y). Then Q = [r, s] is mapped

onto I

under G. The case x > y is similar.

Step 2. Let I be an interval and α : I → I be continuous. Suppose

that (I

)

∞

n=0

is a sequence of compact subintervals of I, and for

all n,

n+1

⊂ α(I

). (3.4)

Then there is a sequence of compact subintervals (Q

) of I such

that for all n,

n+1

⊂ Q

= I

(3.5)

and

) = I

. (3.6)

Hence, there is

x ∈



such that α

(x) ∈ I

for all n. (3.7)

Proof of Step 2. The construction of the sequence Q

proceeds “in-

ductively” as follows: Deﬁne Q

= I

. Recall that α

is deﬁned as

the identity mapping, so α

) = I

and I

⊂ α(I

). If Q

n−1

is de-

ﬁned as a compact subinterval such that α

n−1

) = I

n−1

, then

⊂ α(I

n−1

) = α

n−1

). Use Step 1, with G = α

on Q

n−1

,inor-

der to get a compact subinterval Q

of Q

n−1

such that α

) = I

This completes the induction argument (establishing (3.5) and

(3.6)). Compactness of Q

leads to (3.7).

14 Dynamical Systems

Now we prove [1]. Assume that d ≤ a < b < c (the other case

d ≥ a > b > c is treated similarly).

Write K = [a, b] and L = [b, c].

Let k be any positive integer.

For k > 1, deﬁne a sequence of intervals (I

) as follows:

= L for n = 0, 1, 2,...,k − 2; I

k−1

= K ; and I

n+k

= I

for

n = 0, 1, 2,....

For k = 1, let I

= L for all n.

Let Q

be the intervals in Step 2. Note that Q

⊂ Q

= I

and

) = I

= I

. Hence, Proposition 2.1 applied to α

givesusaﬁxed

point x

of α

in Q

.Now,x

cannot have a period less than k; otherwise,

we need to have α

k−1

) = b, contrary to α

k+1

) ∈ L.

Proof of [2]. See Complements and Details.

We shall now state Sarkovskii’s theorem on periodic points. Consider

the following Sarkovskii ordering of the positive integers:

 5  7 ··· 2.3  2.5 ··· 2

3  2

5  ··· (SO)

 2

.3  2

.5 ··· 2

 2

 2  1

In other words, ﬁrst list all the odd integers beginning with 3; next list 2

times the odds, 2

times the odds, etc. Finally, list all the powers of 2 in

decreasing order.

Theorem 3.2 Let S =

R and α be a continuous function from S into S.

Suppose that α has a periodic point of period k. If k

 k



in the Sarkovskii

ordering (SO), then α has a periodic point of period k



Proof. See Devaney (1986).

It follows that if α has only ﬁnitely many periodic points, then they all

necessarily have periods that are powers of two.

1.3.2 A Remark on Robustness of Li–Yorke Complexity

Let S = [J, K ], and suppose that a continuous function α satisﬁes the

Li–Yorke condition (3.1) with strict inequality throughout; i.e., suppose

that there are points a, b, c, d such that

d = α(c) < a < b = α(a) < c = α(b) (3.8)

1.3 Complexity 15

d = α(c) > a > b = α(a) > c = α(b). (3.9)

Consider the space C(S) of all continuous (hence, bounded) real-

valued functions on S = [J, K ]. Let α=max

x∈S

α(x). The conclu-

sions of Theorem 3.1 hold with respect to the dynamical system (S,α).

But the Li–Yorke complexity is now “robust” in a precise sense.

Proposition 3.1 Let S = [J, K ], and let α satisfy (3.8). In addition,

assume that

J < m(S,α) < M(S,α) < K , (3.10)

where m(S,α) and M(S,α) are respectively the minimum and maximum

of α on [J, K ]. Then there is an open set N of C(S) containing α such

that β ∈ N implies that [1] and [2] of Theorem 3.1 hold with β in place

of α.

Proof. First, we show the following:

Fix x ∈ [J, K ]. Given k ≥ 1, ε>0, there exists δ(k,ε) > 0 such that

“

β − α <δ(k,ε)” implies |β

(x) − α

(x)| <εfor all j = 1,...,k.

The proof is by induction on k. It is clearly true for k = 1, with

δ(1,ε) ≡ ε. Assume that the claim is true for k = m, but not for

k = m + 1. Then there exist some ε>0 and a sequence of functions

{β

} satisfying β

− α→0 such that |β

m+1

(x) − α

m+1

(x)|≥ε. Let

(x) = y

and α

(x) = y. Then, by the induction hypothesis, y

→ y.

From Rudin (1976, Chapter 7) we conclude that β

) → α(y), which

yields a contraction.

Next, choose a real number ρ satisfying 0 <ρ<min[1/2(a − d),

1/2(b − a), 1/2(c − b)] and a positive number r such that β − α < r

implies |β

(a) − α

(a)| <ρfor j = 1, 2, 3, and also 0 < r < min{K −

M(S,α), m(S,α) − J }.

Deﬁne the open set N as

N ={β ∈ C(S):β − α < r }.

It follows that any β ∈ N maps S into S, since the maximum of β on

[J, K ] is less than M(S,α) +r < K . Similarly, the minimum of β on

[J, K ] is likewise greater than J . It remains to show that the condition

(3.8) also holds for any β in N . Recall that α(a) = b,α(b) = c, α(c) = d.

16 Dynamical Systems

Since

β(a) − α(a)

≡

β(a) − b

<ρ,wehave

(i) β(a) > b − ρ>a + ρ>a.

Likewise, since β(a) < b + ρ and |β

(a) − c| <ρ,we get

(ii) β

(a) > c − ρ>b + ρ>β(a).

Finally, since |β

(a) − d| <ρ,we get

(iii) β

(a) < d + ρ<a − ρ<a.

1.3.3 Complexity: Alternative Approaches

Attempts to capture the complexity of dynamical systems have led to

alternative deﬁnitions of chaos that capture particular properties. Here,

we brieﬂy introduce two interesting properties: topological transitivity

and sensitive dependence on initial condition.

A dynamical system (S,α)istopologically transitive if for any pair of

nonempty open sets U and V , there exists k ≥ 1 such that α

(U) ∩ V =

φ. Of interest are the following two results.

Proposition 3.2 If there is some x such that γ (x), the orbit from x, is

dense in S, then (S,α) is topologically transitive.

Proof. Left as an exercise.

Proposition 3.3 Let S be a (nonempty) compact metric space. Assume

that (S,α) is topologically transitive. Then there is some x ∈ S such that

the orbit γ (x) from x is dense in S.

Proof. Since S is compact, it has a countable base of open sets; i.e.,

there is a family {V

} of open sets in S with the property that if M is any

open subset of S, there is some V

⊂ M.

Corresponding to each V

, deﬁne the set O

as follows:

={x ∈ S : α

(x) ∈ V

, for some j ≥ 0}.

is open, by continuity of α. By topological transitivity it is also dense

in S. By the Baire category theorem (see Appendix), the intersection

O =∩

is nonempty (in fact, dense in S). Take any x ∈ O, and con-

sider the orbit γ (x) from x.Takeanyy in S and any open M containing

y. Then M contains some V

. Since x belongs to the corresponding O

there is some element of γ (x)inV

. Hence, γ (x) is dense in S.

1.4 Linear Difference Equations 17

It is important to reﬂect upon the behavior of a topologically transitive

dynamical system and contrast it to one in which the law of motion

satisﬁes the strict contraction property. We now turn to another concept

that has profound implications for the long-run prediction of a dynamical

system. A dynamical system (S,α) has sensitive dependence on initial

condition if there is ∂>0 such that for any x ∈ S and any neighborhood

N of x there exist y ∈ N and an integer j ≥ 0 with the property |α

(x) −

(y)| >∂.

Devaney (1986) asserted that if a dynamical system “possesses sen-

sitive dependence on initial condition, then for all practical purposes,

the dynamics defy numerical computation. Small errors in computation

which are introduced by round-off may become magniﬁed upon itera-

tion. The results of numerical computation of an orbit, no matter how

accurate, may bear no resemblance whatsoever with the real orbit.”

Example 3.2 The map α(x) = 4x(1 − x)on[0, 1] is topologically tran-

sitive and has sensitive dependence on initial condition (see Devaney

1986).

1.4 Linear Difference Equations

Excellent coverage of this topic is available from many sources: we pro-

vide only a sketch. Consider

t+1

= ax

+ b. (4.1)

When a = 1, x

= x

+ bt. When a =−1, x

=−x

+ b for t =

1, 3,...,and x

= x

for t = 2, 4,....

Now assume a = 1. The map α(x) = ax + b when a = 1, has a unique

ﬁxed point x

∗

1−a

. Given any initial x

= x, the solution to (4.1) can

be veriﬁed as

= (x − x

∗

+ x

∗

. (4.2)

The long-run behavior of trajectories from alternative initial x can

be analyzed from (4.2). In this context, the important fact is that

the sequence a

converges to 0 if

< 1 and becomes unbounded if

> 1.

Example 4.1 Consider an economy where the output y

(≥0) in any pe-

riod is divided between consumption c

(≥0) and investment x

(≥0). The

18 Dynamical Systems

return function is given by

t+1

= rx

, r > 1, t ≥ 0. (4.3)

Given an initial stock y > 0, a program x = (x

) (from y) is a nonneg-

ative sequence satisfying x

≤ y, x

t+1

≤ rx

(for t ≥ 1). It generates a

corresponding consumption program c = (c

) deﬁned by c

= y − x

;

t+1

= y

t+1

− x

t+1

= rx

− x

t+1

for t ≥ 0.

(a) Show that a consumption program c = (c

) must satisfy

∞



t=0

≤ y.

(b) Call a program x from y [generating c] efﬁcient if there does not

exist another program x



[generating (c



)] from y such that c



≥ c

for all

t ≥ 0 with strict inequality for some t. Show that a program x is efﬁcient

if and only if

∞



t=0

= y.

amount c > 0 in every period. Informally, we say that a program x from

y that satisﬁes c

≥ c for all t ≥ 0 survives at (or above) c. Note that the

law of motion of the economy that plans a consumption c ≥ 0inevery

period t ≥ 1, with an investment x

initially, can be written as

t+1

= rx

− c. (4.4)

This equation has a solution

= r

− ξ ) +ξ,

where

ξ = c/(r − 1). (4.5)

Hence,

(1) x

reaches 0 in ﬁnite time if x

<ξ;

(2) x

= ξ for all t if x

= ξ ;

(3) x

diverges to (plus) inﬁnity if x

>ξ.

To summarize the implications for survival and sustainable develop-

ment we state the following:

1.4 Linear Difference Equations 19

Proposition 4.1 Survival at (or above) c > 0 is possible if and only if

the initial stock y ≥ ξ + c, or equivalently,

y ≥



r − 1



Of course if r ≤ 1, there is no program that can guarantee that c

≥ c

for any c > 0.

In this chapter, our exposition deals with processes that are generated

by an autonomous or time invariant law of motion [in (2.1), the function

α : S → S does not depend on time]. We shall digress brieﬂy and study

a simple example which explicitly recognizes that the law of motion may

itself depend on time.

Example 4.2 Let x

(t ≥ 0) be the stock of a natural resource at the

beginning of period t, and assume that the evolution of x

is described

by the following (nonautonomous) difference equation

t+1

= ax

+ b

t+1

, (4.6)

where 0 < a < 1 and (b

t+1

)

t≥0

is a sequence of nonnegative num-

bers. During period t,(1− a)x

is consumed or used up and b

t+1

is the “new discovery” of the resource reported at the beginning of

period t + 1.

Given an initial x

> 0, one can write

= a

t−1



i=0

t−i

. (4.7)

Now, if the sequence (b

t+1

)

t≥0

is bounded above, i.e., if there is B > 0

such that 0 ≤ b

t+1

≤ B for all t ≥ 0, then the sequence



t−1

i=0

t−i

converges, so that the sequence (x

) converges to a ﬁnite limit as

well.

For other examples of such nonautonomous systems, see Azariadis

(1993, Chapters 1–5). What happens if we want to introduce uncertainty

in the new discovery of the resource? Perhaps the natural ﬁrst step is to

consider (b

t+1

)

t≥0

as a sequence of independent, identically distributed

random variables (assuming values in

). This leads us to the process

(2.1) studied in Chapter 4.

20 Dynamical Systems

1.5 Increasing Laws of Motion

Consider ﬁrst the dynamical system (S,α) where S ≡ R (the set of reals)

and α : S → S is continuous and nondecreasing (i.e., if x, x



∈ S and

x ≥ x



, then α(x) ≥ α(x



)). Consider the trajectory τ (x

) from any initial

. Since

t+1

= α(x

) for t ≥ 0, (5.1)

there are three possibilities:

Case I: x

> x

Case II: x

= x

Case III: x

< x

In Case I, x

= α(x

) ≥ α(x

) = x

. It follows that {x

} is a non-

decreasing sequence.

In Case II, it is clear that x

= x

for all t ≥ 0.

In Case III, x

= α(x

) ≤ α(x

) = x

. It follows that {x

} is a non-

increasing sequence.

In Case I, if {x

} is bounded above,

lim

t→∞

= x

∗

exists. From (5.1) by taking limits and using the continuity of α,wehave

∗

= α(x

∗

Similarly, in Case III, if {x

} is bounded below,

lim

t→∞

= x

∗

exists, and, again by the continuity of α, we have, by taking limits in

(5.1),

∗

= α(x

∗

We shall now identify some well-known conditions under which the

long-run behavior of all the trajectories can be precisely characterized.

Example 5.1 Let S =

and α : S → S be a continuous, nondecreas-

ing function that satisﬁes the following condition (PI):

there is a unique x

∗

> 0 such that

α(x) > x for all 0 < x < x

∗

α(x) < x for all x > x

∗

. (PI)

1.5 Increasing Laws of Motion 21

In this case, if the initial x

∈ (0, x

∗

), then

= α(x

) > x

and we are in Case I. But note that

< x

∗

implies that x

= α(x

) ≤ α(x

∗

) = x

∗

. Repeating the argument, we get

∗

≥ x

t+1

≥ x

> x

> 0. (5.2)

Thus, the sequence {x

} is nondecreasing, bounded above by x

∗

Hence, lim

t→∞

x exists and, using the continuity of α, we conclude

that

x = α(

x) > 0.

Now, the uniqueness of x

∗

implies that

x = x

∗

If x

= x

∗

, then x

= x

∗

for all t ≥ 0 and we are in Case II.

If x

> x

∗

, then x

= α(x

) < x

, and we are in Case III. Now,

≥ x

∗

and, repeating the argument,

∗

≤ x

t+1

≤ x

···≤x

≤ x

Thus, the sequence {x

} is nonincreasing and bounded below by x

∗

Hence, lim

t→∞

x exists. Again, by continuity of α,

x = α(

x), so

that the uniqueness of x

∗

implies that x

∗

To summarize:

Proposition 5.1 Let S =

and α : S → S be a continuous, nonde-

creasing function that satisﬁes (PI). Then for any x > 0 the trajectory

τ (x) from x converges to x

∗

.Ifx < x

∗

, τ (x) is a nondecreasing sequence.

If x > x

∗

, τ (x) is a nonincreasing sequence.

Here, the long-run behavior of the dynamical system is independent

of the initial condition on x > 0.

Remark 5.1 Suppose α is continuous and increasing, i.e., “x > x



” im-

plies “α(x) >α(x



).”

Again, there are three possibilities:

Case I: x

> x

Case II: x

= x

Case III: x < x

22 Dynamical Systems

Now in Case I, x

= α(x

) >α(x

) = x

. Hence {x

} is an increasing

sequence. In Case II, x

= x

for all t ≥ 0. Finally, in Case III {x

} is a

decreasing sequence. The appropriate rewording of Proposition 5.1 when

α is a continuous, increasing function is left as an exercise.

Proposition 5.2 (Uzawa–Inada condition) S =

, α is continuous,

nondecreasing, and satisﬁes the Uzawa–Inada condition (UI):

A(x) ≡ [α(x)/x] is decreasing in x > 0;

for some

x > 0, A(

x) > 1,

and for some

x >

x > 0, A(

x) < 1. (UI)

Then the condition (PI) holds.

Proof. Clearly, by the intermediate value theorem, there is some x

∗

∈

(

x) such that A(x

∗

) = 1, i.e., α(x

∗

) = x

∗

> 0. Since A(x) is decreas-

ing, A(x) > 1 for x < x

∗

and A(x) < 1 for x > x

∗

. In other words, for

all x ∈ (0, x

∗

), α(x) > x and for all x > x

∗

, α(x) < x, i.e., the property

(PI) holds.

In the literature on economic growth, the (UI) condition is implied

by appropriate differentiability assumptions. We state a list of typical

assumptions from this literature.

Proposition 5.3 Let S =

and α :S→ S be a function that is

(i) continuous on S,

(ii) twice continuously differentiable at x > 0 satisfying:

[E.1] lim

x↓0



(x) = 1 + θ

, θ

> 0,

[E.2] lim

x↑∞



(x) = 1 − θ

, θ

> 0,

[E.3] α



(x) > 0, α



(x) < 0 at x > 0.

Then the condition (UI) holds.

Proof. Take

x >

x ≥ 0; by the mean value theorem

[α(

x) − α(

x)] = (

x −

x)α



(z) where

x < z <

Since α



(z) > 0,α(

x) >α(

x).

Thus α is increasing. Also, α



(x) < 0atx > 0 means that α is strictly

concave. Take

x >

x > 0. Then

x ≡ t

x + (1 − t)0, 0 < t < 1.