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

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

5.3 A Sufﬁcient Condition for

√

n-Consistency 353

Thus,

n + 1



h(X

) − λ

(n + 1)



(n + 1)

(g(X

) − Tg(X

)),

(3.5)

where Y

= g(X

) − Tg(X

j−1

) for 1 ≤ j ≤ n. By the Markov property

of {X

} and the deﬁnition of Tg, it follows that {Y

}

∞

is a martingale

difference sequence, i.e.,

E(Y

| X

, X

,...,X

j−1

) = 0.

For the conditional expectation on the left-hand side equals that of Y

given X

j−1

, namely, Tg(X

j−1

) − Tg(X

j−1

) = 0. This implies that {Y

1 ≤ 1 ≤ n} are uncorrelated and have mean zero. Thus, for any initial

distribution µ,







= 0 and (3.6)







= V









) =



where E

and V

stand for mean and variance under the initial distribu-

tion µ.

Using (a + b)

≤ 2(a

+ b

) repeatedly, we get from (3.5) and (3.6)

that



n + 1



h(X

) − λ



≤

(n + 1)



) +

(n + 1)

(Tg(X

))

+ E

(g(X

))

)

≤

(n + 1)



(2E

) + 2E

(Tg(X

))

)

(n + 1)

(Tg(X

))

+ E

(g(X

))

) ≤

n + 1

where c = 4(max

(x) + max

(Tg(x))

) ≤ 8 max

(x). (3.7)

Deﬁnition 3.1

h,n

is said to be a

√

n-consistent estimate,orestimator,

of λ

√

h,n

− λ

)isstochastically bounded, i.e., for ∀ε>0, ∃K

354 Invariant Distributions: Estimation and Computation

such that for all n,



√

)

n + 1



h(X

) − λ

)

> K



≤ ε, (3.8)

whatever be the initial distribution µ. In this case, one also says that

h,n

− λ

is O

−1/2

), or of order n

−1/2

in probability.

Corollary 3.1 Under the hypothesis of Proposition 3.1,

h,n

is a

√

consistent estimate of λ

Proof. By Chebyshev’s inequality, ∀K > 0,



√

)

n + 1



h(X

) − λ

)

> K



≤



n + 1



h(X

) − λ



≤ c/K

where c is as in (3.7). Hence for ∀ε>0, there exists a K

such that (3.8)

holds, namely, K

= (c/ε)

1/2

A natural question is this: Given a reward function h, how does one

ﬁnd a bounded function g such that the Poisson Equation (3.3) holds?

Rewriting (3.3) as

g =

h + Tg,

where

h(x) = h(x) − λ

, and iterating this we get

g =

h + T (

h + Tg) =

h + T

g =···

h + T

h +···+T

h + T

n+1

This suggests that

g ≡

∞



h (3.9)

is a candidate for a solution. Then we face the question of the convergence

and boundedness of the inﬁnite series



∞

h. This can often be ensured

by the convergence of the distribution of X

to π at an appropriate rate

in a suitable metric.

5.3 A Sufﬁcient Condition for

√

n-Consistency 355

Corollary 3.2 Suppose π is an invariant distribution for p(·, ·) and h is

a bounded measurable function such that the series (3.9) converges uni-

formly for all x ∈ S. Then the empirical

h,n

is a

√

n-consistent estimator

of λ

Proof. Check that g(x) deﬁned by (3.9) satisﬁes the Poisson equation

(3.3), and apply Corollary 3.1.

We give two examples involving random dynamical systems of mono-

tone maps, in which the convergence of the inﬁnite series



∞

n=0

h can

be established.

Example 3.1 Assume that the state space S is an interval and

Theorem 5.1 (Chapter 3) holds. Then

sup

x∈S

(n)

(x, J ) − π(J )|≤(1 − ˜χ)

[n/N]

where J is a subinterval of S.

In particular,

sup

x,y

∞



n=1

(n)

(x, (−∞, y] ∩ S) −π ((−∞, y] ∩ S)| < ∞.

Let h(z) = 1

(−∞,y]∩S

and

h(z) = h(z) − π((−∞, y] ∩ S). Then

h(x) = p

(n)

(x, (−∞, y] ∩ S) −π ((−∞, y] ∩ S), n ≥ 1.

Hence,

sup

∞



n=m+1

h(x)|≤

∞



n=m+1

(1 − ˜χ )

[n/N]

→ 0asm →∞.

This implies the uniform convergence over S of



n=0

h)(x)asm →∞.

Hence, the empirical distribution function

n + 1



j=0

(−∞,y]∩S

)

is a

√

n-consistent estimator of π((−∞, y] ∩ S).

356 Invariant Distributions: Estimation and Computation

Example 3.2 For this example, we restrict the interval S to be bounded,

say, [c, d], and continue to assume that X

n+1

= α

n+1

(n ≥ 0), with

(n ≥ 1) i.i.d. monotone, and that the hypothesis of Theorem 5.1 of

Chapter 3 holds.

Consider h(z) = z, so that

h(z) = z −

yπ(dy). Note that (see

Exercise 3.1)

h)(x) = E[

h(X

) | X

= x]

= E[X

| X

= x] −

yπ(dy)

[c,d]

Prob(X

> u | X

= x) du −

[c,d]

π((u, d]) du

[c,d]

[1 − p

(n)

(x, [c, u]) − (1 − π([c, u]))] du

[c,d]

(n)

(x, [c, u]) − π ([c, u])] du

so that

sup

h(x)|≤

[c,d]

(1 − ˜χ )

[n/N]

du = (d − c)(1 − ˜χ)

[n/N]

Hence, as before,

sup

∞



n=m+1

h(x)|≤(d − c)

∞



n=m+1

(1 − ˜χ )

[n/N]

→ 0asm →∞,

and we have uniform convergence of



n=0

h(x)asm →∞

Thus, by Corollary 3.1, the empirical mean

h,n

n + 1





j=0



is a

√

n-consistent estimate of the equilibrium mean

yπ(dy).

Exercise 3.1 Suppose Z ≥ c a.s. Prove that

EZ − c =

[c,∞)

P(Z > u) du.

5.3 A Sufﬁcient Condition for

√

n-Consistency 357

[Hint: First assume EZ < ∞. Write

[c,∞)

P(Z > u) du =

[c,∞)



{Z(ω)>u}

dP(ω) du =



[c,∞)

{Z(ω)>u}

du d P(ω) (by Fubini) =



(Z(ω) − c) dP(ω). For the case EZ =∞, take Z ∧ M, and let

M ↑∞.]

Exercise 3.2 Suppose Z ≥ c a.s. Then for every r > 0,

E(Z − c)

= r

(0,∞)

r−1

P(Z > c + u) du.

[Hint:

∞

r−1

P(Z > c + u) du =



∞

r−1

{Z(ω)>c+u}

du d P(ω) =



(

Z(ω)−c

r−1

du) dP(ω) =



(Z(ω) − c)

dP(ω) = (1/r)E(Z −

Example 3.3 Assume the hypothesis of Example 3.2. Consider the

problem of estimating the rth moment of the equilibrium distribution:

[c,d]

π(du)(r = 1, 2,...). Letting h(z) = (z − c)

, one has, by

Exercise 3.2, and Theorem 5.1 of Chapter 3,

h(z)|=

)

E(X

− c)

−

(u − c)

π (du)

)

(0,∞)

r−1

[

P(X

> c + u) −π ((c + u, d]

]

)

≤ r

(0,d−c]

r−1

(1 − ˜χ )

[

]

du ≤ (d − c)

(1 − ˜χ )

[

]

Therefore, by Corollary 3.2,

n,c,r

n + 1



j=0

− c)

is a

√

n-consistent estimator of

c,r

(z − c)

π(du)(r = 1, 2,...).

From this, and expanding (X

− c)

and (z − c)

, it follows that

the rth empirical (or sample) moment

n,r

= 1/(n + 1)



j=0

is a

√

n-consistent estimator of the rth moment m

of π, for every r =

1, 2,...(Exercise).

358 Invariant Distributions: Estimation and Computation

A broad generalization of Example 3.1 is proved by the following

theorem:

Theorem 3.1 Assume the general splitting hypothesis (H

) of Theorem

5.2 (Chapter 3). Then for every A belonging to the splitting class A,

ˆπ

(A):= 1/(n + 1)



) is a

√

n-consistent estimator of π(A).

Proof. Let h = 1

h = 1

− π(A) ≡ h − λ

. Note that, by Theorem

5.2 (Chapter 3),

h(x)|=|Eh(X

| X

= x) − π(A)|=|p

(n)

(x, A) − π (A)|

≤ (1 − ˜χ )

[n/N]

∀ n ≥ 1, ∀x ∈ S.

Hence the series (3.9) converges uniformly ∀x ∈ S. Now apply Corol-

lary 3.2.

To apply Theorem 3.1 to random dynamical systems generated by

i.i.d. monotone maps on a closed set S ⊂

, recall that (see Chapter 3

(5.23)) the splitting class A of Corollary 5.2 (Chapter 3) comprises all

sets A of the form

A ={y ∈ S: φ(y) ≤ x}, φ continuous and monotone

on S into

, x ∈ R



. (3.10)

Then Corollary 5.2 of Chapter 3 and Theorem 3.1 above immediatly lead

to the following result, where X

n+1

= α

n+1

(n ≥ 0) with {α

: n ≥ 1}

i.i.d. monotone and continuous on S into S.

Corollary 3.3 Let S be a closed subset

and A the class of all sets A

of the form (3.10). Suppose there exist z

∈ R

, a positive integer N , and

χ>0 such that

P(X

(x) ≤ z

∀x ∈ S) ≥ χ,

P(X

(x) ≥ z

∀x ∈ S) ≥ χ. (3.11)

Then, ˆπ

(A) is a

√

n-consistent estimator of π (A) ∀A ∈ A, π being the

unique invariant probability for the transition probability of the Markov

process X

(n ≥ 0).

Remark 3.1 By letting φ be the identity map, φ(y) = y, it is seen that A

includes all sets of the form S ∩ (X



j=1

(−∞, x

]) ∀x = (x

, x

,...,x

)

∈

. Thus, for each x ∈ R

, the distribution function π ({y: y ≤ x})

5.3 A Sufﬁcient Condition for

√

n-Consistency 359

(extending π to all R

, taking π(R

\S) = 0) is estimated

√

n-consistently

by [1/(n + 1)] # {j:0≤ j ≤ n, X

≤ x}.

The ﬁnal result of this section assumes Doeblin minorization (Theorem

9.1 (Chapter 2) or Corollary 5.3 (Chapter 3)) and provides

√

n-consistent

estimation of λ

for every bounded measurable h.

Theorem 3.2 Let p(x, A) be the transition probability of a Markov pro-

cess on a measurable state space (S, S) such that there exist N ≥ 1 and

a nonzero measure ν for which the N -step transition probability p

(N )

satisﬁes

(N )

(x, A) ≥ ν(A ) ∀x ∈ S, ∀A ∈ S. (3.12)

Then, for every bounded measurable h on S, the series (3.9) converges

and

h,n

is a

√

n-consistent estimator of λ

Proof. Let h be a (real-valued) bounded measurable function on S,

h = h −

hdπ ≡ h − λ

where π is the unique invariant probability

for p. Let h

∞

: = sup{|h(x)|: x ∈ S}. From Theorem 9.1 (Chapter 2)

and Remark 9.2 (Chapter 2), it follows that

h(x)|≡

)

h(y)p

(n)

(x, dy) −

h(y)π(dy)

)

≤ 2h

∞

sup

A∈S

(n)

(x, A) − π (A)|≤2h

∞

(1 − χ )

[n/N]

(3.13)

where χ = ν(S). Hence the series on the right-hand side of (3.9) con-

verges uniformly to a bounded function g, which then satisﬁes the Pois-

son equation (3.3). Now apply Corollary 3.2.

Remark 3.2 By Proposition 3.1, if the solution g = g

of the Poisson

equation (3.3), with h = 1

(

h = 1

− π(A)), is bounded on S uniformly

over a class A of sets A, then (see (3.4))

sup

A∈A

E(ˆπ

(A) −π (A))

≤

n + 1

sup{g



∞

: A ∈ A}=

n + 1

,say.

(3.14)

One may in this case say that the estimator ˆπ

(A)ofπ (A)isuniformly

√

n-consistent over the class A (also see Corollary 3.1, and note that

in (3.8) may be taken to be (

c/ε)

1/2

∀A ∈ A). In Theorem 3.1,

360 Invariant Distributions: Estimation and Computation

ˆπ

(A) is uniformly

√

n-consistent over the splitting class A; and in

Theorem 3.2, ˆπ

(A) is uniformly

√

n-consistent over the entire sig-

maﬁeld S = A. To see this check that the series on the right-hand

side of (3.9) is bounded by



∞

n=0

(1 − χ )

[n/N]

≤



∞

n=0

(1 − χ )

(n/N)−1

(1 − χ )

−1

(1 − (1 − χ)

1/N

)

−1

, where χ = ˜χ is as in Theorem 5.2

(Chapter 3) under the hypothesis of Theorem 3.1, and χ = ¯χ as given in

Theorem 9.1 (Chapter 2) in the case of Theorem 3.2.

5.4 Central Limit Theorems

Theorems 3.1, 3.2 of the preceding section may be strengthened, or

reﬁned, by showing that if h is bounded and if the series (3.9) converges

uniformly to g, then whatever the initial distribution µ,

√

n(λ

h,n

− λ

)

→ N (0,σ

)asn →∞, (4.1)

:= E

(g(X

) − Tg(X

))

(x)π (dx) −

(Tg(x))

π(dx),

where

→ means “converges in law, or distribution,” and N (0,σ

)is

the normal distribution with mean 0 and variance σ

. Note that (4.1)

implies

h,n

− λ

| >

√

) → Prob(|Z | > K )asn →∞, ∀K > 0,

(4.2)

where Z has the distribution N (0,σ

). Thus, in the form of (4.2), the

central limit theorem CLT (4.1) provides a fairly precise estimate of

the error of estimation

h,n

− λ

as Z /

√

n, asymptotically, where Z is

N (0,σ

In order to prove (4.1) we will make use of the martingale CLT, whose

proof is given in Complements and Details.

Let {X

k,n

:1≤ k ≤ k

} be, for each n ≥ 1, a square integrable mar-

tingale difference sequence, with respect to an increasing family of

sigmaﬁelds {

k,n

:0≤ k ≤ k

} : E(X

k,n

k−1,n

) = 0 a.s. (1 ≤ k ≤ k

Write

k,n

:= E(X

k,n

k−1,n

); s

k,n



j=1

j,n

; s



j=1

j,n

≡ s

(ε):=



j=1

E(X

j,n

{|X

j,n

|>ε}

| F

j−1,n

); S



j=1

j,n

. (4.3)

5.4 Central Limit Theorems 361

Proposition 4.1 (Martingale CLT) Assume that, as n →∞, (i) s

→

≥ 0 in probability, and (ii) L

(ε) → 0 in probability for every ε>0.

Then S

converges in distribution to a normal distribution with mean 0

and variance σ

: S

→ N (0,σ

We are now ready to prove a reﬁnement of Theorem 3.2.

Theorem 4.1 Assume the Doeblin hypothesis of Theorem 3.2. Then

(4.1) holds for every bounded measurable h : S →

R, no matter what the

initial distribution µ is.

Proof. Fix an initial distribution µ (of X

). Write X

k,n

:= n

−1/2

(g(X

) − Tg(X

k−1

)), 1 ≤ k ≤ n = k

, and let F

k,n

≡ F

= σ {X

:0≤

j ≤ k}, the sigmaﬁeld of all events determined by X

,0≤ j ≤ k. Since

g and Tgare bounded, for every ε>0, 1

{|X

j,n

|>ε}

= 0∀ sufﬁciently large

n. Hence L

(ε) = 0 for all sufﬁciently large n. Also,

= n

−1



k=1

[(g(X

) − Tg(X

k−1

))

k−1,n

]

= n

−1



k=1

[Tg

k−1

) − (Tg)

k−1

)]. (4.4)

Since Tg

is bounded, one may use the fact that the series (3.9) converges

uniformly with Tg

in place of h, to get, by Proposition 3.1,



−1



k=1

k−1

) −

dπ



= O





→ 0, (4.5)

which implies, by Chebyshev’s inequality,

−1



k=1

k−1

) →

dπ in P

-probability, as n →∞.

(4.6)

But, by invariance of π,

d π =

dπ. Similarly,

−1



k=1

(Tg)

k−1

) →

(Tg)

dπ in probability. (4.7)

Therefore,

→ σ

in probability. (4.8)

362 Invariant Distributions: Estimation and Computation

If σ

> 0, then we have veriﬁed the hypothesis of Proposition 4.1 to

arrive at the CLT (4.1). If σ

= 0, then using the ﬁrst inequality in (3.7),

one shows that

(

√

h,n

− λ

))

≤

(n + 1)



(n + 1)

(Tg(X

))

+ E

(g(X

))

]. (4.9)

The ﬁrst term on the right-hand side equals (2n/(n + 1)

→σ

= 0

by (4.8) (and boundedness of s

), while the second term on the right-

hand side in (4.9) is O(1/n). Thus the left-hand side of (4.9) goes to zero,

implying

√

h,n

− λ

) converges in distribution to δ

{0}

= N (0, 0).

For deriving the next CLT, we assume that X

n+1

= α

n+1

with {α

n ≥ 1} i.i.d. continuous and nondecreasing on a closed subset S of

Note that in Theorem 3.1 we assumed that α

(n ≥ 1) are continuous

and monotone. Thus the reﬁnement of

√

n-consistency in the form of the

CLT (4.1) is provided under an additional restriction here.

Theorem 4.2 Assume the general splitting hypothesis (H

) of Corollary

5.2 of Chapter 3 for i.i.d. continuous monotone nondecreasing maps {α

n ≥ 1} on a closed subset S of

. Then for every h : S → R, which

may be expressed as the difference between two continuous bounded

monotone nondecreasing functions on S, the CLT (4.1) holds.

Proof. First let h be continuous, bounded, and monotone nonde-

creasing. If c ≤ h(x) ≤ d∀x ∈ S, then h

(x):= h(x) −c is nonnegative

and monotone nondecreasing, and

(x) ≡ h

(x) −

dπ =

h(x) =

h(x) −

hdπ. It then follows, mimicking the calculations in Example

3.2, that

h(x) = T

(x) = E(

) | X

= x)

[0,d−c]

)> u | X

=x) du −

[0,d−c]

)> u) du

[c,d]

(h(X

) > u | X

= x) du −

[c,d]

(h(X

) > u) du

=−

[c,d]

(n)

(x, A(u)) − π (A(u))] du, (4.10)