Limit theorems for markov processes generated by iterations of random maps

(1)

LIMIT THEOREMS FOR MARKOV PROCESSES GENERATED BY ITERATIONS OF RANDOM MAPS

OESOOK LEE

1. Introduction

Let p(x,dy) be a transition probability function on (S,p), where S is a complete separable metric space. Then a Markov process X

n

which has p(

x,

dy) as its transition probability may be generated by random iterations of the form X n ⁺

¹

⁼ ^f(X n,en ⁺

^{1 ),}

^where en ^{is a}

sequence of independent and identically distributed random variables (See, e.g.,Kifer(1986), Bhattacharya and Waymire(1990))

In this paper we consider the case f(x, e)

=

fe(x). We consider a discrete time Markov process {X

_{n }}

on a complete separable met- ric space(S,p), represented as X

n =

fnfn-l···flXO, where X o is a given random variable with values on S and {f n} is a sequence of in- dependent and identically distributed random maps on S into itself.

Also, X o and {f n} are independent.

It

is assumed that there exist a positive integer

mo

and a measurable function G on

f(mo)

such that V,,/ E r(mo),p("(x,,,/y)

_~

G("()p(x,y) and E[G(f

mo

···rdJ < 1. {X

n }

obtained by random affine maps on Rn can be treated as a special case of this type. It is proved that under an additional assumption, there exists a unique invariant probability ?r, where pn(x, dy) converges weakly to ?r( dy) an n

~ ⁰⁰

for every x E S. It is also shown that a functional central limit theorem and a strong law of large numbers hold for Lipschitzian functions. Theorems are proved without mentioning irreducibility or any kind of mixing type conditions. This generalizes an earlier results of Bhattacharya and Lee(1988), in which successive com- positions of random maps were assumed to be contractions eventually.

Received January 31, 1996.

1991 AMS Subject Classification: 60J05, 60F05.

Key words: Markov process, invariant probability, weak convergence, strong law of large numbers, functional central limit theorem.

(2)

The case that r has only finitely many maps has been studied by EI- ton(1987) and Barnsley and Elton(1988). Laskot and Rudnicki(1995) considered the case of mo

=

1. 2. Main Results

Let (S, p) be a complete separable metric space and B(S) its Borel sigma field. Let r be a set of continuous maps on S into itself. Let C be the sigma field on r such that the map (" x)

~

,(x) is a measurable function on (r x S,C®B(S». Let P be a probability measure on (r,C).

On some probability space(U,:F, Q) define a sequence of independent and identically distributed random maps r

_b

r

2 ,⁰^{• •}

with common dis- tribution P and a random variable X

0

with values in S independent of the sequence {rn}. Define. Xl = ^rIX

^O, ^{••• ,}

^X

n

= ^{r nXn-l} =

r

^{n .••}

r IX

O'

Here, we write

IX

for the value of the map

I E

r at x, and In'·· 11 for the composition of the maps Ib ..., In. Then X n is a Markov process with transition probability p( x, dy) given by

p(x,B)

=

P( hE r:

I(X)E

B}),

x E

S,B

E

B(S).

pn(x, dy) denotes the n-step transition probability function, i.e. the distribution ofr nrn-l··· r

1

x. We shall write Xn(x) for X n with X o

⁼

x. Note that r

n···

r

1

x has the same distribution as r

₁⁰^{• •}

r

nX.

Write r

^m

for the usual Cartesian product r

x

r

^{X • •• X}

r, and let pm denote the product probablilty on (rm,cm). Let r(m) be the set of all compositions Im··· 11 with

li

E r,

I _~

i

~ m.

For the sigma field c(m) on r(m) ,take the class of all sets B whose inverse under the map Cll'

⁰ ^{• •}

"m)

~

Im··· 11 are in cm

⁰

Let p(m) be the induced probability measure on (r(m), c(m».

We make the following assumptions:

There exist

Xo E

S, a positive integer mo and a nonnegative measurable function G: r(mo)

~

R such that

(AI) V, E r(mo),pC/x'IY)

_~

G(/)p(x,y), Vx,y E S (A2) >.:= E[G(r

mo •••

r

1 )]

< I

(A3) for each r 2: 0, SUPp(x,xo)$rEp(Xn(x),xo) <

^00,

n

=

1,2, ..

⁰^, moo

(3)

THEOREM

2.1. Assume for some

Xo

,positive integer

mo

and

a

non- negative measurable function G on

^r(m^o),

(A1)-(A3) hold. Then there exists a unique invariant probability 1r(dy) for p(x,dy), and pn(x,dy) converges weakly to 1r(dy) for every x E S.

First let us show a lemma.

LEMMA 2.1.

H the hypotheses of the theorem 2.1 hold, then (2.1)

and (2.2)

supEp(Xn(xo),xo) <

⁰⁰

n

sup Ep(Xn(x),Xn(y))

^-+

0

x,yEe

for every compact set C, as n

-+ 00.

Proof. We define Hn(x):= Ep(Xn(x),xo),n = 1,2, ... and let n?

1 be such that N

mo

< n

~

(N + ¹

^)mo

for some nonnegative integer N.

Then by using the assumption that {r n} is independent and identically distributed, we have

Hn(xo)

=

Ep(r

1 •• ,

r nXO, xo)

~

E[p(r

1 . , .

r nXO, r

1 . . .

r moXO) + p(r

1 . . .

r moXO, xo)]

~

E[G(r _{1 .,.} r mo)] Ep(r moH ... r nXO, xo) + K

~

..\ [ ..\Ep(rZmo +

1 •••

r nXO, xo) + K] + K

~ (..\N

+

^..\N-l

+ ... + 1) K

~

K(1- ..\)-1

for all n, where K

:=

sUP1$n$mo Hn(xo) <

^00,

and hence (2.1) holds.

Fix a compact set C in S. For every two points x,

y

E C

(2.3)

Ep(Xn(x),Xn(y))

=

Ep(r n'" r

1

x, r n··· r

1

y)

~

..\ Ep(r n-mo ... r

1

x, r n-mo··· r

1

y)

~ ..\N(Hn-Nmo(x) + Hn-Nmo(y))

~

2K1..\N,

(4)

where K

1

:= sUPl<n<mo sUPxEcHn(x) <

^00,

by the assumption (A3).

Letting n

--t 00 ,

Ce.-N

--t 00

in (2.3), we have (2.2).

On the set of peS) of all probability measures on (S,8(S)) define the bounded Lipschitzian distance

I/JL - v IIBL

:=sup{IJ fdJL- J fdvl:I/fl/=~l,I/fl/L~l} (JL,VEP(S)), where 1/ f 1/== sup{lf(x)1 : x

E

S}, 1/ f I/L= sup{lf(x) - f(y)1J p(x, y) : x

=1=

YES}.

It

is known that (P(S), 1/ . I/BL) is a complete metric space and 1/ .1IBL metrizes the weak-star topology on peS) (Dudley(1968)).

Proof of theorem 2.1. For any xI, X2 E C, C is a compact set, we have

(2.4)

11

pn(XI, dy) - pn(X2' dy) I/BL

= sup{ IEf(Xn(Xl)) - E(f(Xn(X2)) I ^:1/ ^f I/=~ 1,1/ f IIL~ I}

$ E[P(Xn(Xl),Xn(X2)) /\

^2] ^--t ⁰

^as n

^--t 00

by (2.2). Now writing B(xo, M) for the ball of radius M centered at xo,

1/ pn+m(xo,dy) - pn(xo,dy) IlBL

$ E[p(r

1 .• ,

r nrn+l r n+mXO, r1g.otsr nXO) /\ 2]

$ E[{p(f

1 '"

f nfn+l f n+mXO, _{f 1 ... f} nXO) /\ 2}

I{p(rn+1oo.r

n+",Xo,xo)~M}]

(2.5) + E[{p(f

1 •..

f nf n+l'" f n+mXo,f1··· f nXO) /\ 2}

I{p(rn+1 .. or n+",

Xo ,xo)::;M}]

~ 2Q(p(fn+l ...

f

n+mXO,

xo)

~ M)

+ sup E[p(r

1 . . .

r nY, r

1 . . .

r nXO) /\ 2]

yEB(xo,M)

for every M> O. By (2.1) and Chebyshev's inequality, for given

€

> 0, we may choose M = Me such that,

(2.6) Q(p(fn+l ...

f

n+mXO,

xo) ~

Me) < €/4,

\/m =

1,2, ....

(5)

From (2.2),

SUPyEB(xQ,M.)

Ep(r

1 •..

r nY, r

1 ...

r nXO)

-+

0 as n

-+ 00,

which together with (2.5),(2.6) implies for all sufficient large n,

Vm= 1,2....

Completeness of (P(S),

11 .

IIBL) ensures the existence of a probablilty measure 7r such that

(2.7)

11

pn(xo, dy) - 7r(dy) IIBL

^-+

0

as n -+ 00.

(2.4) and (2.7) imply that pn(x,dy)

-+

7r(dy) weakly for every

x

E S.

Since {X

_{n }}

is Feller, 7r is the unique invariant probablilty.

REMARK.

Suppose (A1)-(A3) are satisfied for

mo = 1.

Then (A3) holds if Ep(r1Xo, xo) <

00,

since Ep(X1(x), xo) :::; Ap(X, xo)+Ep(r1Xo, xo).

THEOREM

2.2. Let tbe bypotbeses of tbeorem 2.1 bold and let 7r be tbe unique invariant probability. Tben wbatever tbe initial distribution

IS,

(2.8) a.e. , n

^-+ 00

for any Lipscbitz function f on S.

Proof. Let f be Lipschitzian, i.e. If(x)- f(y)/:::; Mp(x,y) Vx,y

E

S for some M > O. Then J Ifld7r <

^00,

since J p(x,xo)d7r(x) <

^00.

Let {X

n }

be the process with initial invariant distribution 7r, then by Birkhofl"'s Ergodic theorem,

Let

J.L

be any probability measure on S, and let {X

_{n :} n ~

O} be the process with initial distribution

J.L

and define

X~(w)

^{= {}

^Xo(w)

Xo

if

^w E

n

r

if wEn - n

r

(6)

where

Q_r

= {w : p(Xo(w), xo)

~

r}. Let the distribution of X o ^be

^pr

and let

{X~

:

n

:2: O} be the process with initial distribution pr. Now given € > 0, set An

=

{w : _If(X~) - f(Xn)1 > €}. Then by similar manner used in (2.3),

where N is the integer part of...!L. Moreover for 0

_mo ~

i

~mo -

1,

where

Kz = sup sup Ep(Xi(X),XO) + jp(y,xo)-1r(dy) <

^00.

p(x,xo)$r O$i$mo-1

Hence

(2.9)

By Borel-Cantelli lemma,

(2.10)

~ ~

n-1

^f(X;)

^{- t}

j ^fd1r ^a.s..

But * E~';01 f(Xn

⁼

* ^{E~';o1 f(X}

^{i )}

^on

^Q^r

^and ^P(Q

^{r )} ^--t

^{1 as r}

^--t ^00,

which, together with (2.10), completes the proof.

Assume the hypotheses of theorem 2.1 hold and

1r

is the unique invariant probability measure for p(x, dy). Let T be the transition operator on £Z(S, 1r),

Tf(x):= j f(y)p(x,dy), f

E

L

^Z

(S,1r).

(7)

Then (TnJ)(x)

=

J f(y)pn(x,dy). Let 1 denote the identity operator.

We denote the L 2-norm on L 2(S,11") by 11 . lb. Write J = J f d11". Fix

f

^E

^L

²

^(S, 11"). For each positive integer

n,

write (2.11)

[ntJ

_1. " " [ -

[nt] - ]

Yn(t)

^:=

n

²

L..J (f(Xi) - J) + (t - -)(f(X[ntJ+l) - f) (t 2: 0),

i=O

n .

where [nt] is the integer part of nt.

If, for fixed f, Y

_{n (.)}

converges in distribution to a Brownian mo- tion,then we say that the functional central limit theorem(FCLT) holds for the function f.

THEOREM

2.3. Under the hypotheses of the theorem 2.1 ,

(1) if the initial distribution of X

_o

is 11", then for every bounded Lipschitzian f, FCLT holds with mean zero and variance pa- rameter 11

9 II~

- 11 Tg

II~,

where (T - l)g

=

f - f.

(2) if ,in addition, J p2(x,xo)d11" < 00, then for every Lipschitzian, FCLT holds.

(3) convergences in (1) and (2) hold regardless of the initial dis- tribution.

Proof. Let f be Lipschitzian on S, If(x) - f(y)1 ::; Mp( x, y), Vx, Y

E

S. Note that

To prove (1) and (2),it is enough to show that for each case, f

^E

L 2(S,11") and 2::=0 11 Tn(f - J) 112< 00 (See Bhattacharya and Lee(1988».

(1) Assume that for some L > 0, If(x)1 ::; L, Vx E S. Then clearly f E L2(S, 11") and

ITnm0(f - J)(x)1

² ::;

2L{/ IEf(Xnmo(x» - Ef(Xnmo (y»I11"(dy») ::; 2LM / Ep(Xnmo(x),Xnmo(Y»11"(dy)

::; 2LM>..n / p(x,y)11"(dy).

(8)

If we let a

:=

J p(x, xo)d7r(x), then a <

⁰⁰

and

11 Tnm0(f - J) II~~ 2LM)..n / / p(x,y)7r(dY)7r(dx)

=

(4aLM) ..n.

Since

T

is a contraction, we get

11 Tnmo+k(f - J)

112~1I

Tnm0(f - J) Ib,

^k ⁼

0,1,2, ... ,

mo -

1,

and therefore

00 00

L

¹¹

^{Tn(f -} ^J) 112~ L

^{mo 11}

^{Tnm0(f -} ^J) ¹¹²

n=O n=O

(4aLM)1/2 mo

< /\ <

^00.

- (I-v)..)

(2) f E L2(S,7r) follows from the assumption b:= J p2(x,xo)7r(dx)

<

^00.

11 Tnm0(f - J) II~::; ^M ² / ( / Ep(Xnmo(x),Xnmo(y))7r(dY)?7r(dx) ::; M 2 )..2n / ( / p(x, Y)7r(dY)?7r(dx)

::; M 2(b+3a2)..2n.

Therefore we have

2:

00 ¹¹

^{Tn(f -} J)

112::;

M Vb + 3a2mo(1 -

^)..)-1

<

^00.

n=O

(3) Let {X

_{n }}

be the process whose initial distribution is

fL, fL

is an

arbitrary probability measure on (S, 8(S)) and let Y

_{n (.)}

be the process

defined by (2.11). Let Y':-(.) and Y

n (.)

be the corresponding processes

with {Xn} replaced by {X~} and {.in} respectively. Here {X~} and

(9)

{X

n }

are defined in the proof of theorem 2.2. Then we have, for fixed Lipschitzian f,

which goes to 0 as n

---+ 00.

From the fact that Y;(t)

=

Yn(t) on nr,

and P(n

r ) ---+

1

as r ---+ 00,

the conclusion follows.

COROPPARY

2.1. In addition to the assumptions of theorem 2.1, assume

_E[G~(rmo ...

r

1 )]

< 1 and

sUP1<n<mo

E[p2(Xn(XO)' xo)] <

^00.

Then

FC~T

holds for every Lipschitzian function.

Proof. By theorem 2.3, it remains to show that limsup E[p2(Xn(xo), xo)] <

^00,

which is obtained by the following inequality:

(E[p2(Xn(XO)' X 0)])

^1/2

:s _E[p2(r1... r nXO, r

1 ...

r

^moXo)])1/2

+ (E[p2(r 1 r mo XO'XO)])1/2

.:s 1J(E[p2(r

^mo+!

r nXO, xo)])1/2 + ^K 3 :S(1J[':ol+ ... +1J+ 1)K3 :s K 3(1-1J)-\

References

1. Barnsley M. F. and Elton, J. H., A new class of Markov processes for image encoding, Advanced Applied Probability 20 (1988), 14-32.

2. Bhattacharya R. N. and Lee, 0., Ergodicity and central limit theorem for a class of Markov processes., Journal of Mutivariate Analysis 27 (1988), 80-90.

3. Bhattacharya R. N. and Waymire, E.C.,Stochastic Processes and Applications, Wiley, New York., 1990.

4. Billingsley P., Convergence of Probability Measures, Wiley, New York, 1968.

5. Dudley, R. M., Distance of probability measures and random variables, Annals of Mathematical Statistics 39 (1968), 1563-1572.

(10)

6. Elton, J. H., An Ergodic theorem for iterated maps, Ergodic Theory and Dy- nam. System 7 (1987), 481-488.

7. Elton, J. H.and Piccioni, M., Iterated function systems arising from recursive estimation problems, Probability Theory and Related Fields91(1992),103-114.

8.Kifer, Y., Ergodic Theory of Random Transformations, Birkhiiuser,Boston., 1986.

9. Lasota, A. and Mackey, M.,Stochastic perturbation of dynamical systems: The weak convergence of measures, Journal of Mathematical Analysis and Applica- tions 138 (1989), 232-248.

10. Loskot, K. and Rudnicki, R., Limit theorems for stochastically perturbed dy- namical systems, Journal of Applied Probability32 (1995), 459-469.

11.Nummelin,E., General Irreducible Markov Chains and Nonnegative Operators, Cambridge Univ. Press, Cambridge (1984).

Limit theorems for markov processes generated by iterations of random maps