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

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

4.9 Complements and Details 343

= (−1)

z(1 − λ

−1

···(1 − λ

−1

m−1



j=0

m−1−j



∞



n=0



m−1



j=0

m−1−j

,(|z| < |λ

−1

(C3.2)

On the other hand,

(A − λI)

−1

=−z(I − zA)

−1

=−z

∞



k=0



|z| <

A



. (C3.3)

To see this, ﬁrst note that the series on the right-hand side is convergent in

norm for |z| < 1/A, and then check that term-by-term multiplication

of the series



by I − zAyields the identity I after all cancellations.

In particular, writing a

(k)

for the (i, j) element of A

, the series

−z

∞



k=0

(k)

(C3.4)

converges absolutely for |z| < 1/A. Since (C3.4) is the same as the

(i, j) element of the series (C3.2), at least for |z| < 1/A, their coefﬁ-

cients coincide and, therefore, the series in (C3.4) is absolutely conver-

gent for |z| < |λ

−1

(as (C3.2) is).

This implies that, for each ε>0,

)

(k)

)

< (

+ ε)

for all sufﬁciently large k. (C3.5)

For if (C3.5) is violated, one may choose |z| sufﬁciently close to (but

less than) 1/|λ

| such that |z



)



)

|→∞for a subsequence {k



}, con-

tradicting the requirement that the terms of the convergent series (C3.4)

must go to zero for |z| < 1/|λ

Now A

≤m max{|a

(k)

|:1 ≤ i, j ≤ m}(Exercise). Since m

1/k

→ 1

as k →∞, (C3.5) implies (3.10).

Section 4.4. The following generalization of Theorem 4.1 has been de-

rived independently by Bhattacharya and Majumdar (2002, 2004) and

Athreya (2003).

Theorem C4.1 Assume that the distribution Q of C

in (4.2) has a

nonzero absolutely continuous component (with respect to the Lebesgue

344 Random Dynamical Systems: Special Structures

measure on (0,4)), whose density is bounded away from zero on some

nondegenerate interval in (1,4). Assume

E log C

> 0 and E|log(4 − C

)| < ∞. (C4.1)

Then (a) the Markov process X

(n ≥ 0) deﬁned by (4.3) has a unique

invariant probability π on S = (0, 1), and



n=1

(n)

(x, dy) → π(dy) in total variation distance, as N →∞

(C4.2)

and (b) if, in addition, the density component is bounded away from zero

on an interval that includes an attractive periodic point of prime period

m, then

(mk)

(x, dy) → π(dy) in total variation distance, as k →∞.

(C4.3)

Remark 4.2 Theorem 4.1, which is due to Dai (2000), corresponds to

the case m = 1 of part (b) of Theorem C4.1. In general, (C4.1) is a

sufﬁcient condition for the tightness of p

(n)

(x, dy)(n ≥ 1), and therefore,

for the existence of an invariant probability on S = (0, 1) (see Athreya

and Dai 2002). However, it does not ensure the uniqueness of the invariant

probability on (0, 1). Indeed, it has been shown by Athreya and Dai (2002)

that there are distributions Q (of C

) with a two-point support {θ

,θ

}

for which p

(n)

(x, dy) admits more than 1 invariant probability on S.

This is the case for 1 <θ

<θ

< 4, such that 1/θ

+ 1/θ

= 1, and

∈ (3, z], where z is the solution of x

(4 − x) = 16.

A study of the random iteration of two quadratic maps (i.e., Q hav-

ing a two-point support) was initiated in Bhattacharya and Rao (1993).

Examples 4.1–4.3 are taken from this article. Example 4.4 is due to Bhat-

tacharya and Majumdar (1999a). With regard to Examples 4.1 and 4.2, it

has been shown by Carlsson (2002) that the existence of a unique invari-

ant probability (and stability in distribution) holds for the case Q with

support {θ

,θ

} for all 1 <θ

<θ

≤ 3. The extension of these results

to general distributions, as given in Theorem 4.2, is due to Bhattacharya

and Waymire (2002).

4.9 Complements and Details 345

Proof of Theorem 4.2. The result is an immediate consequence of the

following Lemma:

Lemma C4.1 Let θ

<θ

and m ≥ 1 be given.

(a) If, for all θ

∈{θ

,θ

}, 1 ≤ i ≤ m, the range of F

···F

on an

interval I

= [u

] is contained in I

= [u

], then the same is true

for all θ

∈ [θ

,θ

]. In particular, if F

···F

leaves an interval [c, d]

invariant for all θ

∈{θ

,θ

}, 1 ≤ i ≤ m, then the same is true for all

∈ [θ

,θ

], 1 ≤ i ≤ m.

(b) Suppose, for all θ

∈{θ

,θ

}, 1 ≤ i ≤ m, F

···F

leaves in-

variant an interval [c, d]. Assume also that the strict splitting property

above holds, with N = km, a multiple of m, for a distribution Q = Q

whose support is {θ

,θ

}. Then (i) F

···F

leaves [c, d] invariant for

all θ

∈ [θ

,θ

] and (ii) the strict splitting property holds for an arbi-

trary Q =

Q whose support has θ

as the smallest point and θ

as its

largest.

Proof.

(a) The proof is by induction on m. The assertion is true for

m = 1, since in this case u

≤ min{F

(y): y ∈ [u

]}≤F

(x) ≤

max{F

(y): y ∈ [u

]}≤v

, for all x ∈ [u

]. Assume the asser-

tion is true for some integer m ≥ 1. Let a = min{F

···F

m+1

(x): θ

∈

{θ

,θ

},2≤ i ≤ m + 1, x ∈ [u

]}, and b = max{F

···F

m+1

(x):

∈{θ

,θ

},2≤ i ≤ m + 1, x ∈ [u

]}. By the induction hypoth-

esis, for arbitrary θ

,...,θ

m+1

∈ [θ

,θ

], the range F

···F

m+1

on [u

] is contained in [a, b]. On the other hand, u

≤

min{F

(y): y ∈ [a, b]}, v

≥ max{F

(y): y ∈ [a, b]}. Hence, for ar-

bitrary θ

,...,θ

m+1

∈ [θ

,θ

], the range of F

···F

m+1

on [u

]is

contained in [u

], thus completing the induction argument.

(b) (ii) Suppose a strict splitting property holds with δ>0, x

, N .

Deﬁne the continuous functions L, l on [θ

,θ

]







L(θ

,...,θ

):= max

c≤x≤d

···F

(x),

l(θ

,...,θ

):= min

c≤x≤d

···F

(x).

(C4.4)

By hypothesis, the open subset U of [θ

,θ

]

, deﬁned by

U :={(θ

,...,θ

) ∈ [θ

,θ

]

: L(θ

,...,θ

) < x

}, includes a point

(θ

,...,θ

) ∈{θ

,θ

}

. Therefore, U contains a rectangle R = R

346 Random Dynamical Systems: Special Structures

×···×R

where R

is of the form R

= [θ

,θ

+ h

)orR

= (θ

−

,θ

] for some h

> 0(1≤ i ≤ N ), depending on whether θ

= θ

or θ

= θ

. By the hypothesis on

Q,δ

) > 0. Hence the

ﬁrst inequality within parentheses in (4.12) (with “< x

”) holds with

probability at least δ

. Similarly, the second inequality in (4.12) holds

(with “> x

”) with some probability δ

> 0, since V :={(θ

,...,θ

) ∈

[θ

,θ

]

: l(θ

,...,θ

) > x

} is an open subset of [θ

,θ

]

, which in-

cludes a point (θ

,...,θ

) ∈{θ

,θ

}

. Now take the minimum of δ

,δ

for δ in (4.12). Finally, the invariance of [c, d] under F

···F

for all

∈ [θ

,θ

], 1 ≤ i ≤ N , follows from (a).

Section 4.5. Theorem 5.2 is essentially contained in Bhattacharya and

Lee (1988).

Extensions of Theorem 5.1 to unbounded f , g ≡ 1, but assuming η

has

a positive density (a · e)on

, may be found in Bhattacharya and Lee

(1995) and An and Huang (1996). We state the result in the form given

by the latter authors.

Theorem C5.1 Consider the model (5.1) with g ≡ 1. Suppose η

has a

density which is positive a.e (with respect to the Lebesgue measure on

R), and that E|η

| < ∞. Assume, in addition, that there exist constants

0 <λ<1 and c such that

| f (x)|≤λ max{|x

|:1≤ i ≤ k}+c (x ∈ R

). (C5.1)

Then the Markov process X

:= (U

n−k+1

, U

n−k+2

,...,U

n−1

)



, n ≥ k, has

a unique invariant probability π, and its transition probability p satisﬁes

sup

B∈B(R

)

(n)

(x, B) − π(B)

)

≤ c(x)ρ

(n ≥ 1), (C5.2)

for some nonnegative function c(x) and some constant ρ,0<ρ<1.

The exponential convergence (in total variation distance) toward equi-

librium, such as given in (C5.2), is often referred to as geometric ergod-

icity. Theorem C5.1 and other results on geometric ergodicity are gener-

ally derived using the so-called Foster–Tweedie criterion for irreducible

Markov processes, which requires, in addition to the hypothesis of local

minorization (see (9.29) in Chapter 2), that there exists a measurable

function V ≥ 1on(S, S) and constants β>0 and c such that

TV(x) − V (x) ≤−β V (x) + c1

(x), (C5.3)

4.9 Complements and Details 347

where A

is as in the hypothesis (2) of Theorem 9.2, Chapter 2, satisfying

(9.29) with N = 1 (for some probability measure ν with ν(A

) = 1). For

full details and complete proofs, see Meyn and Tweedie (1993, Chap-

ter 15).

Section 4.6. In order to prove singularity of π in Theorem 6.2 (b),

we need two important results on continued fractions (see Billingsley

1965),

+ a

+···+a

→∞

a.e. with respect to the Lebesgue measure on [0, 1] (C6.1)

and

lim

n→∞

log q

12 log 2

a.e. on [0, 1]. (C6.2)

Now let x ∈ (0, ∞) and let y = [a

, a

,...,a

]bethenth convergent

of x, where x is irrational. Then, since the series in (6.31) is alternating

with terms of decreasing magnitude,

F(x) − F(y

)

∞



i=n



−





1 + α



+···+a

i+1

)

≤



1 + α



+···+a

n+1

. (C6.3)

On the other hand, with y

= p

, p

and q

relatively prime integers,

one has (see Kinchin 1964, p. 17)

x − y

n+1

+ 1)

, (C6.4)

so that

)

F(x) − F(y

)

x − y

)

≤



1 + α



+···+a

n+1

+ 1). (C6.5)

Let M be a large number satisfying



1 + α



< 1, (C6.6)

348 Random Dynamical Systems: Special Structures

where γ = exp{π

/12 log 2)}. It follows from (C6.2) that for all x out-

side a set N

of Lebesgue measure zero, one has

+···+a

n+1

> M(n + 1) ∀ sufﬁciently large n. (C6.7)

Now by (C6.2) and using (C6.6), and (C6.7) in (C6.5), one shows that

for all x outside a set N of Lebesgue measure zero,

lim

n→∞

)

F(x) − F(y

)

x − y

)

= 0. (C6.8)

The proof of singularity is now complete by the Lebesgue differentiation

theorem (see Rudin 1966, Real and Complex Analysis, pp. 155, 166).

Proposition 6.1 is essentially due to Letac and Seshadri (1983),

who also obtained the interesting invariant distribution in Example 6.1.

Theorem 6.2 was originally derived in Chassaing, Letac, and Mora (1984)

by a different method. The present approach to this theorem is due to

Bhattacharya and Goswami (1998). In this section we have followed the

latter article and Goswami (2004).

Bibliographical Notes. The study of a linear stochastic difference Equa-

tion (3.7) has a long and distinguished history in econometrics and eco-

nomic theory (see, e.g., Mann and Wald 1943, Haavelmo 1943, and

Hurwicz 1944). For an extended discussion of the survival problem, see

Majumdar and Radner (1991, 1992). Two important papers appearing

in Economic Theory (2004, Symposium on Random Dynamical Sys-

tems) are Athreya (2004) and Mitra, Montrucchio, and Privileggi (2004).

There are several papers motivated by problems of biology that deal with

stochastic difference equations and go beyond the issues we have cov-

ered: see, for example, Jacquette (1972), Reed (1974), Chesson (1982),

Ellner (1984), Kot and Schaffer (1986), and Hardin, Tak´aˇc, and Webb

(1988).

Invariant Distributions: Estimation and Computation

I have but one lamp by which my feet are guided, and that is the lamp of expe-

rience. I know no way of judging the future but by the past.

Patrick Henry

This talk is a collection of stories about trying to predict the future. I have seven

stories to tell. One of them is about a prediction, not made by me, that turned out

to be right. One is about a prediction made by me that turned out to be wrong.

The other ﬁve are about predictions that might be right and might be wrong.

Most of the predictions are concerned with practical consequences of science

and technology....The moral of the stories is, life is a game of chance, and

science is too. Most of the time, science cannot tell what is going to happen.

Freeman J. Dyson.

5.1 Introduction

The practical gain in studying the criteria for stability in distribution of

a time series like

n+1

(x) = α

n+1

(x)) (1.1)

is to estimate long-run averages of some characteristic h(X

)ofX

based on past data. If the process is stable in distribution (on the average)

and

|h|dπ<∞ (where π is an invariant probability), then, according

to the ergodic theorem,

h,n

n + 1



j=0

h(X

)

converges to (the long-run average) λ

hdπ with probability 1, for

π − almost all initial states X

= x. But one does not know π and, in

349

350 Invariant Distributions: Estimation and Computation

general, there is no a priori guarantee that the initial states x belong to

this distinguished set. Indeed, the support of an invariant distribution

may be quite small (e.g., a Cantor set of Lebesgue measure zero). If π

is widely spread out, as in the case, e.g., when π has a strictly positive

density on an Euclidean state space S, one may be reasonably assured of

convergence.

A second important problem is to determine the speed of convergence

h,n

hdπ. One knows from general considerations based on

central limit theorems that this speed is no faster than O

−1/2

). Is this

optimal speed achieved irrespective of the initial state? An approach

toward resolving these issues is a primary theme of this chapter.

5.2 Estimating the Invariant Distribution

Let {X

}

∞

be a Markov process with state space (S, S), transition prob-

ability p(·, ·), and a given initial distribution µ (which may assign mass

1 to a single point). Recall that the transition probability p(·, ·) satisﬁes

(a) for any A ∈ S, p(·, A)isS-measurable and (b) for any x ∈ S, p(x, ·)

is a probability distribution over S. Assume that there is an invariant

distribution π on (S, S), i.e.,

π(A) =

p(x, A)π(dx) (2.1)

for every A in S. Suppose that we wish to estimate π(A) from observing

the Markov process {X

}for 0 ≤ j ≤ n, starting from a historically given

initial condition. A natural estimate of π (A) for any A in S is the sample

proportion of visits to A, i.e.,

ˆπ

(A) ≡

n + 1



), (2.2)

where 1

(x) = 1ifx ∈ A and0ifx /∈ A. We say that ˆπ

(A)isacon-

sistent estimator of π(A) under P

if ˆπ

(A) → π(A)asn →∞in

probability, i.e.,

∀ε>0, P

(|ˆπ

(A) −π (A)| >ε) → 0, (2.3)

where P

refers to the probability distribution of the process {X

}

∞

when

has distribution µ. Assuming that ˆπ

is such a consistent estimator,

it will be useful to know the accuracy of the estimate, i.e., the order of

5.3 A Sufﬁcient Condition for

√

n-Consistency 351

the magnitude of the error |ˆπ

(A) −π (A)|. Under fairly general sec-

ond moment conditions this turns out to be of the order O(n

−1/2

). The

estimator is then called

√

n-consistent. Under some further conditions,

asymptotic normality holds, asserting that

√

n(ˆπ

(A) −π (A))

→ N (0,σ

) (2.4)

for 0 <σ

< ∞ depending on A and possibly the initial distribution µ.

This can then be used to provide conﬁdence intervals for π(A) based on

the data {X

}

The above issues can be considered in a more general framework where

the goal is to estimate

hdπ, (2.5)

the integral of a reward function h that we require to be a real-valued

bounded S-measurable function. A natural estimate for λ

is the empir-

ical average:

h,n

≡

(n + 1)



h(X

). (2.6)

As before, it would be useful to ﬁnd conditions to assess the accu-

racy of

h,n

, i.e., the order of the magnitude of |

h,n

− λ

|. In particu-

lar, it is of interest to know whether this estimate is

√

n consistent, i.e.,

whether |

h,n

− λ

|is of the order O(n

−1/2

) and, further, whether asymp-

totic normality holds, i.e.,

√

h,n

− λ

) converges in distribution to

N (0,σ

) for 0 <σ

< ∞ depending on h, but irrespective of the initial

distribution µ.

5.3 A Sufﬁcient Condition for

√

n-Consistency

In this section we present some sufﬁcient conditions on h and p that

ensure

√

n-consistency and asymptotic normality of

h,n

deﬁned in (2.6),

irrespective of the initial distribution.

In what follows, if g is an S-measurable bounded real-valued function

on S,

Tg(x) ≡

g(y) p(x, dy) = E[g(X

) | X

= x] (3.1)

352 Invariant Distributions: Estimation and Computation

is the conditional expectation of g(X

), given X

= x. The conditional

variance of g(X

), given X

= x, is deﬁned by

Vg(x) ≡ variance [g(X

) | X

= x] = E[(g(X

) − Tg(x))

| X

= x]

= Tg

(x) − (Tg(x))

. (3.2)

5.3.1

√

n-Consistency

The following proposition provides a rather restrictive condition for the

estimate

h,n

of λ

((3.1) and (3.2)) to be

√

n-consistent for any ini-

tial distribution µ and, in particular, for any historically given initial

condition.

Proposition 3.1 Let π be an invariant distribution for p(·, ·) and h be a

reward function. Suppose there exists a bounded S-measurable function

g such that the Poisson equation

h(x) − λ

= g(x) − Tg(x) for all x in S (3.3)

holds.

Then, for any initial distribution µ,

(

h,n

− λ

)

≡ E



n + 1



j=0

h(X

) − λ



≤ (8/(n + 1)) max{g

(x): x ∈ S}. (3.4)

Proof. Since h and g satisfy (3.3), one has

h(x) − λ

= g(x) − Tg(x),

n + 1



h(X

) − λ

n + 1



(g(X

) − Tg(X

))

(n + 1)



[g(X

) − Tg(X

j−1

)]

n + 1

(g(X

) − Tg(X

)).