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

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

4.6 Random Continued Fractions 333

Proof of proposition 6.3.

(a) We will make use of Lemma 6.2. Let F ⊂ (0, ∞) denote the sup-

port of π.Ifx ∈ F, then since X

= Z +

,θ+

∈ F and

∈ F, and,

in turn, θ + x ∈ F. Thus F is closed under inversion: x →

and un-

der translation by θ : x → x + nθ(n = 1, 2,...). Let 0 <θ≤ 1, and

∈ F. Then x

+ nθ ∈ F ∀n = 1, 2,..., and (x

+ nθ)

−1

∈ F ∀n,

and, therefore, 0 is the inﬁmum of F. Also, θ + (x

+ nθ)

−1

∈ F,

∀n, so that θ ∈ F. Let us show that every ﬁnite continued fraction

x = [a

θ; a

θ,...,a

θ] with n + 1 terms belong to F, where a

≥ 0,

≥ 1, for i ≥ 1, are integers. This is true for n = 0. Suppose this is

true for some integer n ≥ 0. Take a

≥ 1 ∀i = 0, 1,...,n. Then if a is

a nonnegative integer, [aθ; a

θ,a

θ,...,a

θ] = aθ +

∈ F. Thus all

continued fractions with n + 2 terms belong to F. Hence, by induction,

all continued fractions with ﬁnitely many terms belong to F. Thus the

closure of this latter set in (0, ∞) is contained in F. By Lemma 6.1,

F = (0, ∞).

(b) Let θ>1. Let F ⊂ (0, ∞) denote the support of π. As in (a), (i)

θ ∈ F, (ii) F is closed under inversion (i.e., if x ∈ F, then

∈ F) and

translation by θ (i.e., if x ∈ F, x + θ ∈ F). Consider now the Markov

chain (6.1) with X

= θ . From Lemma 6.2, and the fact that the distribu-

tion p

(n)

(θ,dy)ofX

has a ﬁnite support (for each n = 1, 2,...), it fol-

lows that F is the closure (in (0, ∞)) of the set ∪

∞

n=1

{y: p

(n)

(θ,{y}) > 0}.

This and (i) and (ii) imply that F is precisely the set of all continued

fractions of the form

θ; a

θ,a

θ,...](a

integers ∀i ≥ 0, a

≥ 0, a

≥ 1 ∀i > 0).

(6.27)

Now use the hypothesis θ>1 to see, using (6.21), that

Prob



< X <θ



= Prob



< Z +

<θ



= α Prob



<θ



+ β Prob



<θ+

<θ



= α Prob



<θ



+ β · 0 = α Prob



< X <θ



(6.28)

which implies π ((

,θ)) = 0, i.e., (

,θ) ∩ F =∅. More generally, the

only numbers x that cannot be expressed as (6.27) are of the form (see

334 Random Dynamical Systems: Special Structures

the proof of Lemma 6.1 and Remark 6.1 following it),

x = [a

θ; a

θ,...,a

θ, y], with

< y <θ. (6.29)

To show that F is nowhere dense in (0, ∞), let 0 < c < d. We will show

that there exists x ∈ (c, d) such that x /∈ F. This is obvious if either c or

d does not belong to F. So assume c, d ∈ F. This means c and d have

continued fraction expansions

c = [a

θ; a

θ,a

θ,...], d = [b

θ; b

θ,b

θ,...]. (6.30)

Since c < d, it is clear that a

≤ b

, and if a

= b

, then a

≥ b

If a

= b

, a

= b

, then a

≤ b

, and so on. Let N = min{k ≥ 0:

= b

}. First consider the case N is even. Then a

< b

.Nowifc =

θ; a

θ,...,a

θ] and y ∈



,θ



, then x:= [a

θ; a

θ,...,a

θ, y] >

c, and x < [a

θ; a

θ,...,a

N −1

θ,(a

+ 1)θ] ≤ d. Thus x ∈ (c, d); but,

in view of (6.29), x /∈ F.Ifc is not equal to [a

θ; a

θ,...,a

θ],

then c = [a

θ; a

θ,...,a

θ,r

N +1

] with 0 <

N +1

<θ, i.e., r

N +1

.If

y ∈ (

, r

N +1

∧ θ), then again c < x:= [a

θ; a

θ,...,a

θ, y] and x <

θ; a

θ,...,a

N −1

θ,a

θ,r

N +1

∧ θ] ≤ d. Thus x ∈ (c, d), x /∈ F. The

case of N odd is similar.

Finally, note that F has no isolated point, since π is nonatomic.

We now give a computation of the fascinating invariant distribution

for the case θ = 1.

Theorem 6.2 Let π denote the invariant probability of the Markov

process (6.1), where P(Z

= 0) = α, P(Z

= 1) = 1 −α, 0 <α<1.

(a) The distribution function F of π is given by

F(x) =

∞



i=0



−





1 + α



+···+a

i+1

, 0 < x ≤ 1,

F(x) = 1 −





,x> 1. (6.31)

Here x = [a

, a

,...] is the usual continued fraction expansion of

x ∈ (0, 1]. That is, writing [y] for the integer part of y,





, x

−





−





,...,

n−1

−



n−1



,..., a

i+1





(i ≥ 1), (6.32)

4.6 Random Continued Fractions 335

with the understanding that the series on the right-hand side in (6.31) is

a ﬁnite sum that terminates at i = n, in the case n is the smallest index

such that x

n+1

= 0. (b) π is singular with full support S = (0, ∞).

Proof.

(a) It has been shown that π is nonatomic (Proposition 6.2). From the

basic relation (6.21), we get

F(x) = α



1 − F





, 0 < x ≤ 1, (6.33)

or writing

for x,

F(x) = 1 −





,1≤ x < ∞. (6.34)

Also, from (6.21),

F(x) = 1 −α F





− (1 −α)F



x − 1



, x > 1. (6.35)

Using (6.34) in (6.35), one gets

F(x) = 1 −α

(1 − F(x)) − (1 − α)F



x − 1



, x > 1, (6.36)

F(x) = 1 −

1 + α



x − 1



, x > 1. (6.37)

If x > 2, then

x−1

< 1, so that using (6.33) in (6.32), one has

F(x) = 1 −

1 + α

(1 − F(x − 1))

1 + α

F(x − 1), x > 2. (6.38)

Iterating this, one gets

F(m + y) = 1 −



1 + α



m−1



1 + α



m−1

F(1 + y),

(m = 1, 2,...;0< y ≤ 1). (6.39)

336 Random Dynamical Systems: Special Structures

Now use (6.37) in (6.39) to get

F(m + y) = 1 −



1 + α







(m = 1, 2,...;0 < y ≤ 1). (6.40)

For 0 < x < 1, use (6.34) and then (6.40) to get

F(x) = α



1 − F







1 + α



[

]



−







. (6.41)

Finally, use (6.34) in (6.41) to arrive at the important recursive relation

F(x) =



1 + α



−



1 + α





−





. (6.42)

Iterating (6.42) one arrives at the ﬁrst relation in (6.31). If x is rational,

the iterative scheme terminates when x

n+1

= 0, so that F(x

n+1

) = 0. If x

is irrational, one arrives at the inﬁnite series expansion. If x ≥ 1, (6.35)

gives the second relation in (6.31).

(b) By Propositions 6.2 and 6.3, π is nonatomic and has full sup-

port (0, ∞). The proof that π is singular (with respect to the Lebesgue

measure) is given in Complements and Details.

Exercise 6.1 Show that, if X has the invariant distribution π of Theorem

6.2, then E[X] = 1, where [X] is the integer part of X . In particular, 1 <

EX < 2. [Hint: P(X ≤ 1) = α/(1 + α), using (6.33), and P(X ≥ m +

1) = (1/α)(α/(1 + α))

α/(1 + α)(m = 0, 1, 2,...) by (6.40). Hence,

by Lemma 2.1, E[X ] =



∞

m=0

P(X ≥ m + 1) = 1.]

Exercise 6.2 For the general model (6.1), prove that if X has the invariant

distribution, then EX ≥ (EZ)/2 +

1 + (EZ/2)

. [Hint: EX = EZ +

) ≥ EZ + 1/EX, by Jensen’s inequality.]

4.7 Nonnegativity Constraints

We now consider a process in which the relevant state variable is required

to be nonnegative. Formally, let {ε

} be a sequence of i.i.d.random vari-

ables, and write

n+1

= max(X

+ ε

n+1

, 0). (7.1)

4.7 Nonnegativity Constraints 337

Here the state space S = [0, ∞), and the random maps α

= f

are

deﬁned as

x = f

(x), where f

(x) = (x + θ )

, (θ ∈ R). (7.2)

Then

(x) = f

n+1

··· f

(x). (7.3)

Theorem 7.1 Assume −∞ ≤ Eε

< 0. The Markov process {X

} has

a unique invariant probability π , and X

converges in distribution to π ,

no matter what X

is.

Proof. The maps f

are monotone increasing and continuous, and S

has a smallest point, namely, 0. Writing the backward iteration

(x) = f

··· f

(x),

we see that Y

(0) increases a.s. to Y ,say.IfY is a.s. ﬁnite, then the

distribution of Y

is an invariant probability π of the Markov process

. One can show that this is the case if Eε

< 0, and that if Eε

< 0,

the distribution p

(n)

(z, dy)ofX

(z) converges weakly to π, whatever be

the initial state z ∈ [0, ∞). To prove this, we ﬁrst derive the following

identity:

··· f

(0) = max{θ

, (θ

+ θ

)

,...,(θ

+ θ

+···+θ

)

}

= max{(θ

+···+θ

)

:1≤ j ≤ n},

∀ θ

,...,θ

∈ R, n ≥ 1. (7.4)

For n = 1, (7.4) holds since f

(0) = θ

. As an induction hypothesis,

suppose (7.4) holds for n − 1, for some n ≥ 2. Then

··· f

(0) = f

( f

··· f

(0))

= f

(max{(θ

+···+θ

)

:2≤ j ≤ n})

= (θ

+ max{(θ

+···+θ

)

:2≤ j ≤ n})

= (max{θ

+ θ

,θ

+ (θ

+ θ

)

,...,θ

+(θ

+···+θ

)

})

= max{(θ

+ θ

)

, (θ

+ (θ

+ θ

)

,...,

(θ

+ (θ

+···+θ

)

}. (7.5)

338 Random Dynamical Systems: Special Structures

Now check that (y + z

)

= max{0, y, y + z}=max{y

, (y + z)

Using this in (7.5) we get f

··· f

(0) = max{θ

, (θ

+ θ

)

(θ

+ θ

)

,...,(θ

+ θ

+···+θ

)

}, and the proof of (7.4) is com-

plete. Hence

(0) = max{(ε

+···+ε

)

, 1 ≤ j ≤ n}. (7.6)

By the strong law of large numbers (ε

+···+ε

)/n → Eε

< 0 a.s. as

n →∞. This implies ε

+···+ε

→−∞a.s. Hence ε

+···+ε

0 for all sufﬁciently large n, so that outside a P-null set, (ε

+···+

)

= 0 for all sufﬁciently large j. This means that Y

(0) = constant

for all sufﬁciently large n, and therefore Y

(0) converges to a ﬁnite

limit Y

a.s. The distribution π of Y is, therefore, an invariant probabi-

lity.

Finally, note that, by (7.4),

(z) = f

... f

n−1

(z) = f

... f

n−1

(0)

= max{ε

, (ε

+ ε

)

,...,(ε

+ ε

+···+ε

n−1

)

(ε

+ ε

+···+ε

n−1

+ ε

+ z)

}. (7.7)

Since ε

+···+ε

→−∞a.s., ε

+···+ε

n−1

+ z < 0 for all suf-

ﬁciently large n. Hence, by (7.6), Y

(z) = Y

n−1

(0) ≡ max{ε

, (ε

)

,...,(ε

+ ε

+···+ε

n−1

)

} for all sufﬁciently large n, so that

(z) converges to Y a.s. as n →∞. Thus X

(z) converges in distribu-

tion to π as n →∞, for every initial state z. In particular, π is the unique

invariant probability.

Remark 7.1 The above proof follows Diaconis and Freedman (1999).

The condition “Eε

< 0” can be relaxed to “



∞

n=1

(1/n)P(ε

+···+

> 0) < ∞” as shown in an important paper by Spitzer (1956). Ap-

plications to queuing theory may be found in Baccelli and Bremaud

(1994).

4.8 A Model with Multiplicative Shocks, and the Survival

Probability of an Economic Agent

Suppose that in a one-good economy the agent starts with an initial stock

x. A ﬁxed amount c > 0 is consumed (x > c), and the remainder x − c is

invested for production in the next period. The stock produced in period

4.8 A Model With Multiplicative Shocks 339

1isX

= ε

− c) = ε

(x − c), where ε

is a nonnegative random

variable. Again, after consumption, X

− c is invested in production of

a stock of ε

− c), provided X

> c.IfX

≤ c, the agent is ruined.

In general,

= x, X

n+1

= ε

n+1

− c)(n ≥ 0), (8.1)

where {ε

: n ≥ 1} is an i.i.d. sequence of nonnegative random variables.

The state space may be taken to be [0, ∞) with absorption at 0. The

probability of survival of the economic agent, starting with an initial

stock x > c,is

ρ(x): = P(X

> c for all n ≥ 0 | X

= x). (8.2)

If δ: = P(ε

= 0) > 0, then it is simple to check that P(ε

= 0 for

some n ≥ 0) = 1, so that ρ(x) = 0 for all x. Therefore, assume

P( ε

> 0) = 1. (8.3)

From (8.1) one gets, by successive iteration,

n+1

> c

iff X

> c +

n+1

iff X

n−1

> c +

c +

n+1

= c +

n+1

...

iff X

≡ x > c +

+···+

...ε

n+1

Hence, on the set {ε

> 0 for all n},

> c for all n}=



x > c +

+···+

···ε

for all n





x ≥ c + c

∞



n=1

···ε





∞



n=1

···ε

≤

− 1



In other words,

ρ(x) = P



∞



n=1

···ε

≤

− 1



. (8.4)

340 Random Dynamical Systems: Special Structures

This formula will be used to determine conditions on the common dis-

tribution of ε

, under which (1) ρ(x) = 0, (2) ρ(x) = 1, (3) ρ(x) < 1

(x > c). Suppose ﬁrst that E log ε

exists and E log ε

< 0. Then, by the

Strong Law of Large Numbers,



r=1

log ε

a.s.

−→

E log ε

< 0,

so that log ε

···ε

→−∞a.s., or ε

···ε

→ 0 a.s. This implies

that the inﬁnite series in (8.4) diverges a.s., that is,

ρ(x) = 0 for all x,ifE log ε

< 0. (8.5)

Now, by Jensen’s inequality, E log ε

≤ log Eε

, with strict inequality

unless ε

is degenerate. Therefore, if Eε

< 1, or Eε

= 1 and ε

nondegenerate, then E log ε

< 0. If ε

is degenerate and Eε

= 1, then

P(ε

= 1) = 1, and the inﬁnite series in (8.4) diverges. Therefore, (8.5)

implies

ρ(x) = 0 for all x,ifEε

≤ 1. (8.6)

It is not true, however, that E log ε

> 0 implies ρ(x) = 1 for large x.

To see this and for some different criteria, deﬁne

m: = inf{z ≥ 0: P(ε

≤ z) > 0}, (8.7)

the smallest point of the support of the distribution of ε

Let us show that

ρ(x) < 1 for all x,ifm ≤ 1. (8.8)

For this, ﬁx A > 0, however large. Find n

such that

> A

∞

r=1



1 +



. (8.9)

4.8 A Model With Multiplicative Shocks 341

This is possible, as

(1 + 1/r

) < exp{



1/r

} < ∞.Ifm ≤ 1 then

P(ε

≤ 1 + 1/r

) > 0 for all r ≥ 1. Hence,

0 < P(ε

≤ 1 + 1/r

for 1 ≤ r ≤ n

)

≤ P







r=1

···ε

≥



r=1

j=1

1 +





≤ P







r=1

···ε

≥

∞

j=1

1 +





≤ P





r=1

···ε

> A



≤ P



∞



r=1

···ε

> A



Because A is arbitrary, (8.4) is less than 1 for all x, proving (8.8).

One may also show that, if m > 1, then

ρ(x) =



< 1ifx < c



m−1



=1ifx ≥ c



m−1



(m > 1). (8.10)

To prove this, observe that

∞



n=1

···ε

≤

∞



n=1

m − 1

with probability 1 (if m > 1). Therefore, (8.4) implies the second rela-

tion in (8.10). In order to prove the ﬁrst relation in (8.10), let x < cm /

(m − 1) − cδ for some δ>0. Then (x/c) − 1 < 1/(m − 1) −δ. Choose

n(δ) such that

∞



r=n(δ)

, (8.11)

and then choose δ

> 0(1≤ r ≤ n(δ) − 1) such that

n(δ)−1



r=1

(m + δ

) ···(m + δ

)

n(δ)−1



r=1

−

. (8.12)

342 Random Dynamical Systems: Special Structures

Then

0 < P(ε

< m + δ

for 1 ≤ r ≤ n(δ) − 1)

≤ P



n(δ)−1



r=1

···ε

n(δ)−1



r=1

−



≤ P



∞



r=1

···ε

∞



r=1

− δ



= P



∞



r=1

···ε

m − 1

− δ



If δ>0 is small enough, the last probability is smaller than



1/(ε

···ε

) > x/c − 1), provided x/c − 1 < 1/(m − 1), i.e., if

x < cm/(m − 1). Thus for such x, one has 1 −ρ(x) > 0, proving the

ﬁrst relation in (8.10).

These results are due to Majumdar and Radner (1991). The proofs

follow Bhattacharya and Waymire (1990, pp. 182–184).

4.9 Complements and Details

Section 4.3.

Proof of Lemma 3.1. Let λ

,...,λ

be the eigenvalues of A. This means

det(A − λI) = (λ

− λ)(λ

− λ) ···(λ

− λ), where det is shorthand for

determinant and I is the identity matrix. Let λ

have the maximum

modulus among the λ

, i.e., |λ

|=r(A). If |λ| > |λ

|, then A − λI is

invertible, since det( A − λI ) = 0. Indeed, by the deﬁnition of the inverse,

each element of the inverse of A − λI is a polynomial in λ (of degree

m − 1orm − 2) divided by det(A − λI). Therefore, one may write

(A−λI)

−1

= (λ

− λ)

−1

···(λ

− λ)

−1

+ λA

+···+λ

m−1

)

(|λ| > |λ

|), (C3.1)

where A

(0 ≤ j ≤ m − 1) are m × m matrices that do not involve λ.

Writing z = 1/λ, one may express (C3.1) as

(A − λI)

−1

= (−λ)

−m

(1 − λ

/λ)

−1

···(1 − λ

/λ)

−1

m−1



j=0

(1/λ)

m−1−j