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

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

1.11 Supplementary Exercises 113

of economic growth in which optimal programs can be explicitly calcu-

lated for alternative optimality criteria. Radner (1967) dealt with a more

general framework. The reduced form model was used by Gale (1967) in

his landmark paper on optimal development in a multisector economy,

and subsequently proved convenient for mathematical analysis as well

as construction of examples.

Section 1.9.7. Indeed, Sundaram (1989, pp. 164–165) has a stronger

monotonicity result. However, if the stock effect is introduced in the

utility function, the evolution of stocks may display complex behavior

(see the example of Dutta and Sundaram (1993). See also the paper by

Dana and Montrucchio (1987)).

Section 1.9.8. Our exposition of the overlapping generations model

(Samuelson 1958) is based on Diamond (1965) and Galor and Ryder

(1989); see also Wendner (2003). Gale (1973) considered a pure ex-

change model. The possibility of chaotic behavior in this context was

conﬁrmed by Benhabib and Day (1982).

Section 1.9.9. Some of the basic papers on the stability of the price

adjustment processes are by Arrow and Hurwicz (1958), Arrow, Block,

and Hurwicz (1959), Arrow (1958), Scarf (1960), Saari (1985), and Bala

and Majumdar (1992).

1.11 Supplementary Exercises

(1) Let A be a strictly positive (n × n) matrix, and consider the fol-

lowing “backward” system:

= Ax

t+1

≥ 0(t = 0, 1,...). (11.1)

Of course x

= 0isatrivial solution. Show that

(i) there is a balanced growth solution to (11.1): x

= (1/η)

x, where

x > 0 and η>0 (and this solution is unique up to a multiplication by a

positive scalar).

(ii) the balanced growth solution is the sole possible nontrivial

solution.

114 Dynamical Systems

(2) Again, let A >> 0, and λ ≡ λ(A) be its dominant root. Consider

= Ax

t+1

+ c

≥ 0, c

≥ 0(t = 0, 1,...) (11.2)

where (c

) is a given sequence of vectors, c

≥ 0 for all t ≥ 0.

(i) Show that the convergence of either one of the following two series

for a given sequence (c

)(c

≥ 0, for t ≥ 0)

∞



m=0

(α)

∞



m=0

, λ ≡ λ( A)(β)

entails the convergence of the other. Moreover, (11.2) has a solution if

and only if (α) is convergent. If this condition is met, the series

∞



m=0

m+v

is also convergent for any integer v = 0, 1,...,and the solution of (11.2)

is given by

= u

∞



m=0

m+t

where u

is any solution of (11.1).

(For further discussions and applications of backward equations, see

Nikaido (1968) and Azariadis (1993).)

(3) Consider the difference equation

= px

t+1

+ qx

t−1

, t = 1, 2,... (11.3)

where 0 < p < 1 and q = 1 − p.

Show that the general solution has the form



A + B(q/ p)

if p = q

A + Bt if p = q

Specifying x

for any two distinct values of t sufﬁces to determine A and

B completely.

1.11 Supplementary Exercises 115

(4) In the study of (local) stability of a ﬁxed point of a nonlinear

dynamical system, we are led to the question of identifying conditions

under which

lim

t→∞

= 0, (11.4)

where A is a square matrix (n × n). If all the roots λ

of the characteristic

equation

det(A − λI ) = 0 (11.5)

satisfy |λ

| < 1, then (11.4) holds. For a quadratic equation

f (λ) = λ

+ a

λ + a

= 0, (11.6)

(where a

= 0, a

= 0), both roots λ

, λ

of (11.6) satisfy |λ

| < 1 if and

only if

1 + a

+ a

> 0, 1 −a

+ a

> 0, 1 −a

> 0

(see Brauer and Castillo-Chavez (2001, Chapter 2.7) and Samuelson

(1941)).

(5) Period-doubling bifurcation to chaos in an overlapping generations

model

(5.1) The Framework. Consider an economy described by (a, b; u

,δ,v), where (a, b) ∈ R

and b > 0; u

and u

are nondecreasing

functions from

to R, which are increasing on [0, a + b]; δ ∈ (0, 1);

and v ∈

A program is a sequence {c

, d

}

∞

such that

, d

) ∈ R

and c

+ d

= a + b for t ≥ 0

A competitive equilibrium is a sequence {c

, d

, p

, q}

∞

such that

(i) (c

, d

, p

, q) ∈ R

for t ≥ 0.

(ii) For each t ≥ 0, (c

, d

t+1

)isinB

t+1

={c, d ∈ R

: p

c + p

t+1

d ≤

a + p

t+1

b}, and u

) + δu

t+1

) ≥ u

(d) for all (c, d) ∈

t+1

. Further, d

is in B

={d ∈ R

: p

d ≤ p

b − qv} and u

) ≥

(d) for all d ∈ B

(iii) c

+ d

= a + b for t ≥ 0.

Here, in each period t ≥ 0, an agent is born who lives for two periods

(t, t + 1). The agent has an endowment (a, b) over its life time. There

is one ‘old’ agent in period 0 with an endowment b (who disappears at

116 Dynamical Systems

the end of period 0). In a competitive equilibrium, each agent born in

period t ≥ 0 chooses (c

, d

t+1

) from its budget set determined by prices

, p

t+1

so as to maximize the discounted sum of utilities u

(d)

from consumption (c, d) over its lifetime. The old agent leaves part of

his income to the ‘clearing house.’ The choices of the agent must meet

the feasibility condition (iii) period after period.

For an interpretation of this competitive equilibrium in terms of the

institution of a clearing house and IOUs, see Gale (1973). Our example

can be paraphrased from Gale as follows.

“We suppose that people never trade directly with each other but work

through a clearing house.” The old agent in period 0 consumes d

less

than its endowment b, and leaves an ‘income’ (vq) with the clearing

house. The new generation wishes to consume this excess, and must buy

it from the clearing house. It is not able to pay for it until its old age.

Accordingly it leaves with the clearing house an IOU for the ‘income.’

In its old age it pays its debt with interest and gets the IOU back, which

it can destroy. But, in the meantime, a new “generation” of young agents

has come to the clearing house with a new IOU and so on.

(5.2) Properties of competitive equilibrium. Verify that if {c

, d

, q}

∞

is a competitive equilibrium,

(i) p

> 0 for t ≥ 0;

(ii) p

+ p

t+1

= p

a + p

t+1

b for t ≥ 0, p

= p

b − qv.

(5.3) Dynamics of monetary equilibrium. A monetary equilibrium

, d

, p

, q}

∞

is a competitive equilibrium that satisﬁes q > 0. It is

interior if c

> 0 and d

> 0.

Given a monetary equilibrium, we can conclude that for each t ≥ 0,

, d

t+1

) must solve the problem

maximize u

(d)

subject to p

c + p

t+1

d = p

a + p

t+1

(c, d) ≥ 0







. (P)

Also, d

must solve the problem

maximize δu

(d)

subject to p

d = p

b − qv

d ≥ 0







. (Q)

1.11 Supplementary Exercises 117

We now look at the dynamics that must be satisﬁed by an interior

monetary equilibrium. For this purpose, we assume in what follows

that u

and u

are concave and continuously differentiable on

, and



(d) > 0 for d ∈ [0, a + b).

We note that for an interior monetary equilibrium, d

< a + b and

< a + b all t ≥ 0. Thus, there exists a sequence {λ

}

∞

such that



) = λ

δu



t+1

) = λ

t+1

and δu



) = λ







for t ≥ 0

and λ

> 0 for t ≥ 0. This yields

t+1



) = δ p



t+1

) for t ≥ 0. (11.7)

Also, using the constraint equation in (P),

t+1

(b − d

t+1

) = p

− a) for t ≥ 0. (11.8)

Finally, check the feasibility constraint

− a = b − d

for t ≥ 0. (11.9)

[Hint: Using the constraint in (Q), we know that b > d

(since q > 0,

v>0), so that by repeatedly using (11.9) and (11.8), b > d

for t ≥ 0.]

To summarize, if {c

, d

, p

, q}

∞

is an interior monetary equilibrium,

then

(i) (c

, d

, p

) >> 0 and b > d

for t ≥ 0;

(ii) c

+ d

= a + b for t ≥ 0;

(iii) p

− a) = p

t+1

(b − d

t+1

) for t ≥ 0;

(iv) [u



)/δu



t+1

)] = [ p

/ p

t+1

] for t ≥ 0.

Conversely, verify the following: suppose there is a sequence

, d

, p

}

∞

satisfying

(i) (c

, d

, p

) >> 0 for t ≥ 0 and b > d

;

(ii) c

+ d

= a + b for t ≥ 0;

(iii) p

− a) = p

t+1

(b − d

t+1

) for t ≥ 0;

(iv) [u



)/δu



t+1

)] = [ p

/ p

t+1

] for t ≥ 0;

then {c

, d

, p

, q}

∞

is an interior monetary equilibrium, where q =

[b − d

]/v.

Thus for any sequence {c

, d

, p

}

∞

, conditions (i)–(iv) characterize

interior monetary equilibria.

118 Dynamical Systems

Consider, now, any sequence {c

, d

, p

}

∞

satisfying conditions (i)–

(iv) above. Deﬁning x

= b − d

for t ≥ 0, and using (ii) and (iii), we

then have

t+1

= [ p

/ p

t+1

for t ≥ 0. (11.10)

Using (iv) in (11.10), we ﬁnally get

t+1



)

δu



t+1

)

for t ≥ 0. (11.11)

(5.4) An example of period doubling. We consider now a speciﬁc

example (based on the one discussed in Benhabib and Day (1982)) in

which

(a, b) = (0, 1)

(1/4) <δ<1



c − (1/2)c

for 0 ≤ c ≤ 1

1/2 for c > 1

(d) = d for d ≥ 0.

Note that (a, b), u

, and u

satisfy all the assumptions imposed above.

Now (11.11) translates to

t+1

= (1/δ)[1 − c

for t ≥ 0.

And since x

= b − d

= 1 − d

= a + b − d

= c

, we ﬁnally obtain the

basic difference equation

t+1

= (1/δ)x

[1 − x

] for t ≥ 0

with x

∈ (0, 1).

Applying this well-known theory, we can observe how the nature

of the dynamics in the overlapping generations model changes as the

discount factor δ decreases from values close to 1 to values close to 0.25.

Markov Processes

A drunk man will ﬁnd his way home, but a drunk bird may get lost forever.

Shizuo Kakutani

Ranu looked at Kajal and thought suddenly, “His father used to look exactly like

this when he was up to some mischief.” Kajal’s father had made a small mistake

in thinking that his state of childhood at Nischindipur was lost forever. After an

absence of twenty four years the innocent child had returned to Nischindipur.

The unvanquished mystery of life, travelling through the ages, how gloriously it

had revealed itself again.

Bibhuti Bandyopadhyay

2.1 Introduction

In theory and applications Markov processes constitute one of the most

important classes of stochastic processes. A sequence of random vari-

ables {X

: n = 0, 1, 2,...} with values in a state space S (with a sig-

maﬁeld S) is said to be a (discrete parameter) Markov process if, for

each n ≥ 0, the conditional distribution of X

n+1

,given{X

, X

,...,X

}

depends only on X

. If this conditional distribution does not depend

on n (i.e., if it is the same for all n), then the Markov process is

said to be time-homogeneous. All Markov processes will be considered

time-homogeneous unless speciﬁed otherwise. The above conditional

probability p(x, B):= Prob (X

n+1

∈ B | X

= x) ≡ Prob (X

n+1

∈ B |

, X

,...,X

})on{X

= x}, x ∈ S, B ∈ S, is called the transi-

tion probability of the Markov process. Conversely, given a function

(x, B) → p(x, B)onS × S such that (i) x → p(x, B) is measurable on

S into

R for every B ∈ S and (ii) B → p(x, B) is a probability measure

119

120 Markov Processes

on (S, S) for every x ∈ S, one may construct a Markov process with

transition probability p(.,.) for any given initial state X

= x

(or initial

distribution µ of X

The present chapter is devoted to the general theory of Markov pro-

cesses. A broad understanding of this vast and fascinating ﬁeld is facili-

tated by an analysis of these processes on countable state spaces (Markov

chains). Irreducible chains, where every state can be reached from ev-

ery other state with positive probability, are either transient or recurrent

(Theorem 7.1). In a transient chain, every state eventually disappears

from the view, i.e., after a while, the chain will not return to it. A recur-

rent chain, on the other hand, will reappear again and again at any given

state. Among the most celebrated chains are simple random walks on the

integer lattice

, and a famous result of Polya (Theorem 7.2) says that

these walks are recurrent in dimensions k = 1, 2 and are transient in all

higher dimensions k ≥ 3.

Recurrent chains may be further classiﬁed as null recurrent or positive

recurrent (Section 2.8). In a null recurrent chain, it takes a long time for

any given state to reappear – the mean return time to any state being

inﬁnite. If the mean return time to some state is ﬁnite, then so is the case

for every state, and in this case the chain is called positive recurrent. In

the latter case the Markov process has a unique invariant distribution,or

steady state, to which it approaches as time goes on, no matter where it

starts (Theorem 8.1). Simple random walks in dimensions k = 1, 2 are

null recurrent. A rich class of examples is provided by the birth-and-death

chains in which the process moves a unit step to the left or to the right at

each period of time (Examples 8.1–8.3), but the probabilities of moving

in one direction or another may depend on the current state. Depending on

these probabilities, the chain may be transient, null recurrent, or positive

recurrent (Propositions 8.3 and 8.4). Two signiﬁcant applications are to

physics (Ehrenfest model of heat exchange) and economics (a thermostat

model of managerial behavior, due to Radner).

Moving on to general state spaces in Section 2.9, two proofs are given

of an important result on the exponential convergence to a unique steady

state under the so-called Doeblin minorization condition (Theorem 9.1).

Simple examples that satisfy this condition are irreducible and aperiodic

Markov chains on ﬁnite state spaces, and Markov processes with continu-

ous and positive transition probability densities on a compact rectangle in

(k ≥ 1). A third proof of Theorem 9.1 is given in Chapter 3, using no-

tions of random dynamical systems. Theorem 9.2 provides an extension

2.1 Introduction 121

to general state spaces of the criterion of Theorem 8.1 for the existence

of a unique steady state and its stability in distribution.

Section 2.10 extends two important classical limit theorems to func-

tions of positive recurrent Markov chains – the SLLN, the strong law of

large numbers (Theorem 10.1), and the CLT, the central limit theorem

(Theorem 10.2). They are important for the statistical estimation of in-

variant (or steady state) probabilities, and of steady state means or other

quantities of interest. Appropriate extensions of the CLT to general state

spaces are provided later in Chapter 5. Finally, Sections 2.11 and 2.12

deﬁne notions of convergence in distribution in metric spaces and that

of asymptotic stationarity and provide criteria for them, which are used

in later chapters.

A special signiﬁcance of discrete time Markov processes in our

scheme is due to a rather remarkable fact: such processes may be re-

alized or represented as random dynamical systems. To understand the

latter notion, consider a set  ={f

,..., f

} of measurable functions

on S into S, with f

assigned a positive probability q

(1 ≤ i ≤ k),

+···+q

= 1. Given an initial state x

∈ S, one picks a function

at random from : f

being picked with probability q

,1≤ i ≤ k.

Let α

denote this randomly chosen function. Then the state at time

n = 1isX

= α

≡ α

). At time n = 2, one again chooses a

function, say α

from  according to the assigned probabilities and

independently of the ﬁrst choice α

. The state at time n = 2 is then

= α

). In this manner one constructs a random dy-

namical system X

n+1

= α

n+1

) = α

n+1

···α

(n ≥ 1), X

= x

where {α

: n ≥ 1} is a sequence of independent maps on S into S with

the common distribution Q ={q

, q

,...,q

} on . It is simple to

check that {X

: n = 0, 1,...} is a Markov process having the transition

probability

p(x, B) = Prob(α

x ∈ B) = Q({γ ∈  : γ x ∈ B}), (x ∈ S, B ∈ S).

(1.1)

One may take X

to be random, independent of {α

: n ≥ 1} and having

a given (initial) distribution µ. It is an important fact that, conversely,

every Markov process on a state space S may be represented in a similar

manner, provided S is a standard state space, i.e., a Borel subset of a

Polish space (see Chapter 3, Complements and Details for a more formal

elaboration of this point). Recall that a topological space M is Polish if

it is homeomorphic to a complete separable metric space.

122 Markov Processes

Exercise 1.1 Show that (0, 1)

,[0, 1]

,[0, 1)

,(0, ∞)

,[0, ∞)

with

their usual Euclidean distances are Polish, k ≥ 1. [Hint: (0, 1)

and (0, ∞)

are homeomorphic to R

;[0, 1)

is homeomorphic to

[0, ∞)

Although the present chapter focuses primarily on the asymptotic, or

long-run, behavior of a Markov process based on its transition probabil-

ity, in many applications the Markov process is speciﬁed as a random

dynamical system. One may of course compute the transition probabil-

ity in such cases using Equation (1.1). However, the asymptotic analysis

is facilitated by the evolution of the process as directly depicted by the

random dynamical system. A systematic account of this approach begins

in Chapter 3, which also presents several important results that are not

derivable from the standard theory presented in this chapter.

2.2 Construction of Stochastic Processes

A stochastic process represents the random evolution with time of the

state of an object, e.g., the price of a stock, population or unemployment

rate of a country, length of a queue, number of people infected with

a contagious disease, a person’s cholesterol levels, the position of a

gas molecule. In discrete time a stochastic process may be denoted as

: n = 0, 1, 2,...,}, where X

is the state of the object at time n de-

ﬁned on a probability space (, F, P). Sometimes the index n starts at

1, instead of 0. The state space can be quite arbitrary, e.g.,

(for the

price of a stock),

(for the length of a queue), R

(for the position of

a molecule). In the case the state space S is a metric space with some

metric d, the sigmaﬁeld S is taken to be the Borel sigmaﬁeld. Note that

for every n, the distribution µ

0,1,...,n

, say, of (X

, X

,...,X

) can be

obtained from the distribution µ

0,1,...,n+1

of (X

, X

,...,X

, X

n+1

)by

integrating out the last coordinate (e.g., from the joint density or joint

probability function of the latter). We will refer to this as the consistency

condition for the ﬁnite-dimensional distributions µ

0,1,...,n

(n = 0, 1,...).

An important question is: Given a sequence of ﬁnite-dimensional

distributions µ

0,1,...,n

(n = 0, 1,...) satisfying the consistency condition,

does there exist a stochastic process {X

: n = 0, 1, 2,...}on some proba-

bility space with these as its ﬁnite-dimensional distributions? The answer

to this is “yes” if S is a Polish space and S its Borel sigmaﬁeld, according