Bhattacharya R., Majumdar M. Random Dynamical Systems: Theory and Applications
Подождите немного. Документ загружается.
5.6 Complements and Details 373
Finally,
lim
n→∞
)
)
)
)
E exp{iξ S
n
}−exp
−
ξ
2
2
)
)
)
)
lim
n→∞
)
)
E exp{iξ S
n
}−E exp{iξ S
n
}
)
)
+
lim
n→∞
)
)
)
)
E exp{iξ S
n
}−exp
−
ξ
2
2
)
)
)
)
= 0 +
lim
n→∞
)
)
)
)
E exp{iξ S
n
}−exp
−
ξ
2
2
)
)
)
)
exp
−
ξ
2
2
−|ξ |
3
ε
−1
|ξ|
3
ε. (C4.14)
The extreme right side of (C4.14) goes to zero as ε ↓ 0, while the extreme
left does not depend on ε.
Condition (ii) of the martingale CLT is called the conditional Linde-
berg condition.
The martingale CLT as presented here is due to Brown (1977). Its
proof follows Bhattacharya and Waymire (1990).
The following CLT is due to Gordin and Lifsic (1978). Its proof is
based on a version of the margingale CLT due to Billingsley (1961)
and Ibragimov (1963). The term “ergodic” in its statement is defined in
a general context under Remark C4.1. For our purposes, it is enough
to know that a Markov process {X
n
: n ≥ 0} with a unique invariant
probability π is ergodic (if X
0
has distribution π). The process {X
n
:
n ≥ 0} is then said to be ergodic even when X
0
has an arbitrary initial
distribution.
As a very special case, the following is obtained: If p(x; dy) admits
a unique invariant probability π, and {X
n
: n 0} is a Markov process
with transition probability p(x, dy) and initial distribution π , then {X
n
:
n
0} is ergodic.
Theorem C4.1 (CLT for discrete-parameter Markov processes)
Assume p(x, dy) admits an invariant probability π and, under the initial
distribution π , {X
n
} is ergodic. Assume also that
˜
h = h −
!
hdπ is in
the range of I − T . Then, under initial π ,
1
√
n
n−1
m=0
h(X
m
) −
"
hdπ
→ N (0,σ
2
) as n →∞, (C4.15)
where σ
2
= σ
2
h
is given by (4.1) with g defined by (I − T )g =
˜
h.
374 Invariant Distributions: Estimation and Computation
Remark C4.1 (Birkhoff’s ergodic theorem) Let T
1
be a measurable map
on a state space (
˜
S,
˜
S) into itself, which preserves a probability measure µ
on (
˜
S,
˜
S). Birkhoff’s ergodic theorem says: For every µ-integrable g,
1
n
n−1
m=0
g(T
m
1
x) converges a.s.(w.r.t. µ) and in L
1
(µ) to a function
¯
g(x),
say, where
¯
g is invariant:
¯
g(T
1
x) =
¯
g(x) ∀x ∈
˜
S,
!
¯
gdµ =
!
gdµ. If
the dynamical system (T
1
,
˜
S,µ) is ergodic,
¯
g =
!
gdµ. Here (T
1
,
˜
S,µ)
is said to be ergodic if all invariant functions are constant a.s. with respect
to µ. Suppose one takes
˜
S = S
∞
, S = S
⊗∞
, and X
n
(n ≥ 0) a stochas-
tic process with state space (S, S), defined on the canonical probability
space (S
∞
, S
⊗∞
, Q) such that X
n
(ω) is the projection onto the nth coor-
dinate of ω ∈ S
∞
(n ≥ 0). The process X = (X
0
, X
1
,....) is stationary,
if
˜
T X ≡ (X
1
, X
2
,...) has the same distribution Q as X. Then, by
Birkhoff ’s ergodic theorem, if E|h(X)| < ∞,
1
n
n−1
m=0
h(
˜
T
m
X) con-
verges a.s. and in L
1
(Q) to an invariant random variable
¯
h(X), say.
If {X
n
: n ≥ 0} is ergodic then
¯
h(X) = Eh(X) ≡
!
hdQ a.s. As a spe-
cial case, with h(X):= f (X
0
) for some measurable f : S → R such that
E| f (X
0
)| < ∞, one has
1
n
n−1
m=0
f (X
m
) converges a.s. and in L
1
(Q)to
an invariant
¯
h(X), which equals Ef(X
0
)if{X
n
: n ≥ 0} is ergodic. Note
that the validity of the last italicized statement depends only on the dis-
tribution of X. Hence it holds for a stationary process {X
n
: n ≥ 0} on an
arbitrary probability space (, F, P).
For proofs of Birkhoff’s ergodic theorem, we refer to Billingsley (1965,
pp. 20–29), or Bhattacharya and Waymire (1990, pp. 224–227).
Theorem C4.2 below is due to Bhattacharya and Lee (1988). Theorem
4.2 is a special case of this.
Theorem C4.2 Let {X
n
: n ≥ 0} be a Markov process defined by X
n+1
=
α
n+1
X
n
(n ≥ 0), where {α
n
: n ≥ 1} is a sequence of i.i.d. monotone
nondecreasing maps on a closed subset S of
R
, and X
0
is independent
of {α
n
: n ≥ 1}. Suppose the splitting hypothesis (H) of Section 3.5 holds,
as in the case of collary 5.3. Then, no matter what the distribution of
X
0
is, the CLT (C4.15) holds for every h that may be expressed as
the difference f
1
− f
2
between two nondecreasing measurable functions
f
i
: S → S such that f
i
∈ L
2
(π)(i = 1, 2).
Bhattacharya (1982) contains additional information on the CLT for
Markov processes in continuous time, much of which can be adapted to
discrete time.
5.7 Supplementary Exercises 375
Central limit theorems are truly “central” for statistical inference in
time series. Of the great body of literature on the statistical inference
for time series, we mention Anderson (1971), Box and Jenkins (1976),
Brillinger (1981), Brockwell and Davis (1991), Grenander and Rosen-
blatt (1957), Granger and Terasvirta (1993), Hannan (1970), Pristley
(1981), and Rosenblatt (2000). A comprehensive account of the asymp-
totic statistical theory for estimation and testing for parametric and semi-
parametric linear as well as nonlinear models may be found in Tamiguchi
and Kakizawa (2000). Hwang (2002) contains some asymptotic results,
including bootstrapping of the nonparametric estimation of the driving
function f in nonlinear autoregressive models (5.1) of Chapter 4, under
the hypothesis of Theorem C5.1 in Complements and Details, Chapter 4.
For bootstrapping in the first-order model NLAR(1), see Frankel, Kreiss,
and Mammen (2002). The results of Hwang on NLAR(k), k ≥ 1, were
obtained independently of those on the first-order model NLAR(1) by
Franke et al. (2002).
The Billingsley–Ibragimov CLT (Billingsley 1961, Ibragimov 1963,
applied to Markov processes in Gordin and Lifsic (1978), Bhattacharya
(1982), is especially useful when the process is not necessarily irre-
ducible.
5.7 Supplementary Exercises
(1) (Definitions and simple properties of martingales). A sequence of
random variables {X
n
}(n = 0, 1,...) is said to be {
n
}-adapted with
respect to an increasing sequence of sigmafields
n
⊂
n+1
···(n =
0, 1,...)ifX
n
is
n
-measurable (for every n). An {
n
}-adapted sequence
{X
n
} with finite expectations is said to be {
n
}-martingale if E(X
n+1
|
n
) = X
n
a.s. (n ≥ 0). If, in particular,
n
= σ {X
j
:0≤ j ≤ n}∀n, then
{X
n
} is simply said to be a martingale. Suppose that {X
n
} is an {
n
}-
adapted martingale. Prove the following statements:
(a) E(X
n
|
n
) = X
m
a.s. for every m ≤ n. [Hint: Take successive
conditional expectations, recalling that E(X | G) = E[E(X |) | G] for
all sigmafields G ⊂.]
(b) {X
n
} is a martingale (with respect to the sigmafields
G
n
= σ {X
j
:0≤ j ≤ n}. [Hint: E(X
n+1
| G
n
) = E[E(X
n+1
|
n
)|G
n
] =
E(X
n
| G
n
) = X
n
a.s., noting that if {X
n
} is {
n
}-adapted then G
n
⊂
n
∀n.]
376 Invariant Distributions: Estimation and Computation
(c) The martingale differences Z
n
≡ X
n
− X
n−1
(n ≥ 1) satisfy (i)
E(Z
n+1
|
n
) = 0 = E(Z
n+1
| G
n
)(n ≥ 0), (ii) if EX
2
n
< ∞ for all n,
then EZ
n
Z
m
= 0 ∀n = m.
(d) EX
n
= EX
0
for all n (constancy of expectations).
(e) EX
2
n
= EX
2
0
+
n
m=1
EZ
2
m
,ifEX
2
n
< ∞ for all n, and Z
m
≡
X
m
− X
m−1
(m ≥ 1).
(2) (Examples of martingales).
(a) Suppose {Z
n
: n ≥ 0} is a sequence of independent ran-
dom variables with finite means EZ
n
= µ
n
(n ≥ 0). Prove that (i)
S
n
=
n
0
(Z
j
− µ
j
), n ≥ 0, is an {
n
}-martingale, where
n
= σ {Z
j
:
0 ≤ j ≤ n}, (ii) if EZ
2
n
< ∞ for all n, then X
n
≡ S
2
n
−
n
0
σ
2
j
(n ≥ 0) is
an {
n
}-martingale, where σ
2
j
≡ var(Z
j
). [Hint: E(X
n+1
|
n
)=E((S
n
+
Z
n+1
µ
n+1
)
2
−
n+1
0
σ
2
j
|
n
)=S
2
n
−
n
0
σ
2
j
+E((Z
n+1
− µ
n+1
)
2
|
n
)−
2S
n
E(Z
n+1
− µ
n+1
|
n
) − σ
2
n+1
= X
n
.]
(b) Suppose Y
j
( j ≥ 1) are independent random variables with a com-
mon finite nonzero mean µ. Show that X
n
= µ
−n
=
n
j=1
Y
j
(n ≥ 1) is an
{
n
}-martingale, where
n
= σ {Y
j
:1≤ j ≤ n} (n ≥ 1).
(c) Suppose X is a random variable on a probability space (, , P)
with a finite expectation. If
n
(n ≥ 1) is an increasing sequence of sig-
mafields,
n
⊂for all n, show that X
n
≡ E(X |
n
), n ≥ 1, is an {
n
}-
martingale.
(3) (Stopping times). Let {X
n
}be an {
n
}-adapted sequence of random
variables (n ≥ 0). A stopping time,oran{
n
}-stopping time, τ is a ran-
dom variable taking values in {0, 1, 2,...} ∪ {∞}such that {τ ≤ n}∈
n
for every n = 0, 1, 2,....Prove the following:
(a) τ is a stopping time if and only if {τ = n}∈
n
for all n.
(b) If τ is a stopping time, then so is τ ∧ m ≡ min{τ,m} for every
nonnegative integer m.
(c) τ ≡ m,aconstant time, is a stopping time, whatever be the non-
negative integer m.
(d) The first passage time τ
B
= inf{n ≥ 0: X
n
∈ B} is a stopping
time for every Borel set B. Here “inf” of an empty set is taken to
be ∞.
(4) (Optional stopping of martingales). Suppose {X
n
} is a {
n
}-
adapted martingale (n ≥ 0) and τ is a stopping time.
(a) Prove that EX
τ
= EX
0
if τ is bounded. [Hint: Suppose
τ ≤ m. Define X
−1
= 0. Then EX
τ
=
m
n=0
EX
n
· 1
{τ =n}
=
m
n=0
5.7 Supplementary Exercises 377
EX
n
[1
{τ ≤n}
− 1
{τ ≤n−1}
.] Now use the fact that E[(X
n
− X
n−1
)
1
{τ ≤n−1}
]=E[1
{τ ≤n−1}
E(X
n
−X
n−1
|
n−1
)]=0∀n ≥ 1, to get EX
τ
=
m
n=0
EX
n
1
{τ ≤n}
−
m
n=0
E(X
n−1
+ X
n
− X
n−1
)1
{τ ≤n−1}
=
m
n=0
EX
n
1
{τ ≤n}
−
m
n=0
EX
n−1
1
{τ ≤n−1}
= EX
m
1
{τ ≤m}
= EX
m
= EX
0
.]
(b) If τ is finite a.s. and E|X
τ ∧m
− X
τ
|→0asm →∞,
then prove that EX
τ
= EX
0
. [Hint: Take τ ∧ m as the stopping
time in (a) to get EX
τ ∧m
= EX
0
, and then take the limit as
m →∞.]
(5) (First passage times for the simple symmetric random walk). Let
S
0
= 0, S
n
= Z
1
+ Z
2
+···+Z
n
(n ≥ 1), where Z
j
( j ≥ 1) are i.i.d.,
and P(Z
j
=+1) = P(Z
j
=−1) = 1/2. Let a, b be two positive inte-
gers and consider the first passage time τ = τ
{−a,b}
(to −a or b). Let
n
= σ {Z
j
:1≤ j ≤ n},
0
={φ, }. Let A
1
be the event “{S
n
}reaches
−a before it reaches b,”and A
2
be the event “{S
n
} reaches b before it
reaches −a.”
(a) Prove that P(A
1
) = b/(a + b), P(A
2
) = a/(a + b ). [Hint: {S
n
:
n ≥ 0} is a {
n
} martingale, and ES
0
= 0 = ES
τ
= bP(A
2
) −
aP( A
1
) = bP(A
2
) − a(1 − P(A
2
)) = (a + b)P(A
2
) − a. Here we use
Exercise 4(b).]
(b) Prove that Eτ = ab. [Hint: Consider the {
n
}-martingale X
0
= 0,
X
n
= S
2
n
− nEZ
2
1
≡ S
2
n
− n(n ≥ 1). By Exercise 4(b), ES
2
τ
− Eτ = 0,
or Eτ = (−a)
2
P(A
1
) + b
2
P(A
2
) = a
2
b/(a + b) + b
2
a/(a + b) = ab.
To apply Exercise 4(b), one needs to show that E|X
τm
− X
τ
|≡
|E(S
τ ∧m
− S
τ
) − (τ ∧ m − τ )|→0. Since S
2
τ ∧m
, S
2
τ
are bounded by
max{a
2
, b
2
}, and τ ∧ m → τ a.s. as m →∞, it is enough to prove
that Eτ<∞. For then τ ∧ m ↑ τ a.s., and by the monotone conver-
gence theorem, E|τ ∧ m − τ |→0asm →∞. To prove that Eτ<∞,
write Eτ =
∞
m=0
P(τ ≥ m). Now the probability that the random walk
reaches {−a, b } in n
0
= max{a, b}steps or less is at least
1
2
n
0
≡ δ,say,
n
0
matter where the random walk starts in (−a, b) since the distance
between the starting point and {−a, b } is never more than n
0
. Hence
P(τ ≥ m) ≤ (1 − δ)
k
if m ≥ n
0
k. That is, P(τ ≥ m) ≤ (1 − δ)
[m/n
0
]
∀m,
where [r] is the integer part of r. This shows that the series for Eτ con-
verges (exponentially fast).]
(6) (Wald’s identity). Let Y
j
( j ≥ 1) be a sequence of i.i.d. random vari-
ables with finite mean µ = EY
j
, Y
0
≡ 0. Let τ be a {
n
}-stopping time,
where
n
= σ {Y
j
:0≤ j ≤ n}. Write S
n
=
n
0
Y
j
. Suppose Eτ<∞
and E|S
τ
− S
τ ∧m
|→0asm →∞. Then ES
τ
= µEτ . [Hint: Consider
378 Invariant Distributions: Estimation and Computation
the {
n
}-martingale X
n
= S
n
− nµ, and apply Exercise 4(b) to get
EX
τ
= EX
0
= 0, i.e., ES
τ
− Eτµ = 0.]
(7) (First passage times for the asymmetric simple random walk).
Let {Z
j
: j ≥ 1} be i.i.d., P(Z
j
=+1) = p, P(Z
j
=−1) = q = 1 − p,
and assume p > 1/2. Let τ = τ
{−a,b}
. Prove that, for the random walk
S
n
=
n
1
Z
j
− n( p − q), n ≥ 1, S
0
= 0,
Eτ =
a + b
p − q
1 −
,
q
p
-
a
1 −
,
q
p
-
a+b
−
a
p + q
.
[Hint: By Exercise (6), ES
τ
= ( p − q)Eτ . But ES
τ
= (−a)P(A
1
) +
bP(A
2
), where A
1
, A
2
are as in Exercise (5). Now use P(A
1
)(= 1 −
P(A
2
)) as given in Example 6.3, Chapter 2 (i.e., (6.22), with x = 0,
c =−a, d = b).]
6
Discounted Dynamic Programming
Under Uncertainty
The basic need for a special theory to explain behavior under conditions of
uncertainty arises from two considerations: (1) subjective feelings of imperfect
knowledge when certain types of choices, typically commitments over time, are
made; (2) the existence of certain observed phenomena, of which insurance is
the most conspicuous example, which cannot be explained on the assumption
that individuals act with subjective certainty.
Kenneth J. Arrow
6.1 Introduction
In this chapter we briefly review some results on discounted dynamic
programming under uncertainty, and indicate how Markov processes
and random dynamical systems are generated by optimal policies. In
Section 6.2, following a precise description of the dynamic program-
ming framework, we turn to the special case where the set S of states is
countable, and the set A of actions is finite. Here the link between optimal
policies and the celebrated functional equation can be established with
no measure theoretic complications. In Section 6.3 we study the maxi-
mum theorem, which is of independent interest in optimization theory
and is a key to the understanding of the basic result in the next section.
In Section 6.4 we explore the more general model where S is a Borel
subset of a Polish space, and A is a compact action space, and spell out
the conditions under which there is a stationary optimal policy.
The dynamic programming technique reviewed here has been par-
ticularly powerful in attacking a variety of problems in intertemporal
economics. In Section 6.5 we discuss in detail the aggregative model
of optimal economic growth under uncertainty. Here, given the spe-
cific structure of the model, the process of optimal stocks (or optimal
379
380 Discounted Dynamic Programming Under Uncertainty
inputs) can be viewed as a random dynamical system. We draw upon
our earlier results to analyze the long-run behavior of the optimal input
process.
6.2 The Model
A dynamic programming problem is specified by the following objects:
" S, A, q, u,δ#, where S is a nonempty Borel subset of a Polish (i.e.,
complete, separable metric) space, interpreted as the set of states of some
system; A is a nonempty Borel subset of a Polish space, interpreted as
the set of actions available to the decision maker; q is the law of motion
of the system – it associates (Borel measurably) with each pair (s, a)a
probability measure q(.|s, a)onS, the Borel sigmafield of S: when the
system is in state s and an action a is chosen, it moves to the state s
in the next period according to the distribution q(.|s, a); u is a bounded
Borel measurable function on S × A, interpreted as the utility, income,
or immediate return – when the system is in state s, and the chosen action
is a, the decision maker receives an income u(s, a); δ is a discount factor,
0 <δ<1. A policy (or plan) ζ = (ζ
t
) specifies for each t 1 which
action to choose in the tth period as a Borel measurable function of the
history h = (s
1
, a
1
,...,a
t−1
; s
t
) of the system up to period t, or more
generally, ζ specifies for each h a probability distribution ζ
t
(.|h)onthe
Borel subsets of A.
A Borel function f from S into A defines a policy. When in state s,
choose an action f (s)(independently of when and how the system has
arrived at state s). We denote the corresponding policy by ( f
(∞)
). Such
policies are called stationary, and f is somewhat informally referred to
as an optimal policy function.
A policy ζ associates with each initial state s a corresponding
tth period expected return u
t
(ζ)(s) and an expected discounted total
return
I (ζ)(s) =
∞
t=1
δ
t−1
u
t
(ζ)(s), (2.1)
where δ is the discount factor, 0 <δ<1.
A policy ζ
∗
will be called optimal if I (ζ
∗
)(s) I (ζ)(s) for all policies
ζ and s ∈ S. The problem, then, is to find an optimal policy.
6.2 The Model 381
6.2.1 Optimality and the Functional Equation
of Dynamic Programming
We begin with the case where the state space S is countable and the
action space A is finite and introduce the celebrated functional equa-
tion that characterizes optimality. Recall from Chapter 2 that the states
in a countable S are labeled i, j, k etc. Also, we write q
ij
(a) to denote
the probability with which the state moves from i to j if (after observ-
ing i) the action a is chosen. Thus, for any fixed i ∈ S, and a ∈ A,
q
ij
(a) is the probability distribution of the state in the next period (i.e.,
q
ij
(a) ≥ 0,
j
q
ij
(a) = 1). The immediate return function is bounded,
i.e., there is some constant B > 0 such that |u(i, a)|≤B for all i ∈ S,
and a ∈ A.
Define
V (i) = sup
ζ
I (ζ)(i).
V : S →
R is the value function of the dynamic programming
problem.
Clearly, a policy ζ
∗
is optimal if
I (ζ
∗
)(i) = V (i) for all i ∈ S.
Our first result characterizes the value function V by the functional
equation (2.2), which will be casually referred to as the “optimality equa-
tion” or the “functional equation” of dynamic programming.
Theorem 2.1 For all i ∈ S,
V (i) = max
a∈A
u(i, a) + δ
j
q
ij
(a)V ( j)
. (2.2)
Proof. Let ζ be any policy, and suppose it chooses some action a ∈ A
in the initial period (period 1). Then,
I (ζ)(i) = u(i, a) + δ
j
q
ij
(a)w
ζ
( j),
382 Discounted Dynamic Programming Under Uncertainty
where w
ζ
( j) represents the total expected return from period 2 onward,
given that ζ is used and the state in period 2 is j. But w
ζ
( j) ≤ V ( j).
Hence,
I (ζ)(i) ≤ u(i, a) +δ
j
q
ij
(a)V ( j)
≤ max
a∈A
u(i, a) + δ
j
q
ij
(a)V ( j)
.
Since ζ is arbitrary, we have
V (i) ≡ sup
ζ
I (ζ)(i) ≤ max
a∈A
u(i, a) + δ
j
q
ij
(a)V ( j)
.
Conversely, using the finiteness of A, let a
0
be such that
u(i, a
0
) + δ
j
q
ij
(a
0
)V ( j)
≡ max
a∈A
u(i, a) + δ
j
q
ij
(a)V ( j)
.
Let ζ be the policy that chooses a
0
when the initial state is i, and if
the next state is j, then views the process as originating in j, and uses a
policy ζ
j
such that I (ζ
j
)( j) ≥ V ( j) − ε. Hence,
I (ζ)(i) = u(i, a
0
) + δ
j
q
ij
(a
0
)I (ζ
j
)( j)
≥ u(i, a
0
) + δ
j
q
ij
(a
0
)V ( j) − δε.
Since V (i) ≥ I (ζ)(i), we have
V (i) ≥ u(i, a
0
) + δ
j
q
ij
(a
0
)V ( j) − δε.
Hence,
V (i) ≥ max
a∈A
u(i, a) + δ
j
q
ij
(a)V ( j)
− δε.
Since ε is arbitrary,
V (i) ≥ max
a∈A
u(i, a) + δ
j
q
ij
(a)V ( j)
.