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

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

2.14 Supplementary Exercises 243

restated as

= px

i+1

+ qx

i−1

for i ≥ 1,

= px

The solution (recall from Chapter 1) is given by

= A + An if p = q

= A − A

(

q/ p

)

n+1

if p = q

Verify that if q ≥ p, the only bounded solution is x

= 0. If q < p, A = 1

gives the maximal solution x

= 1 −

(

q/ p

)

n+1

(e) Consider a Markov chain with state space

{

0, 1, 2,...

}

and

transition matrix of the form

p =







qpr00...

0 qpr0 ...

00qpr...

.. .. .. .. .. . . .







We can interpret this as a queuing model: if there are i customers in

the queue and i ≥ 1, the customer at the front is served and leaves, and

then 0, 1, 2 new customers arrive with probabilities q, p, r. This creates

a queue of length i − 1, i ,ori + 1. If i = 0, no one is served, and the

new arrivals bring the queue length to 0, 1, 2. Assume that q > 0, r > 0,

so that the chain is irreducible.

For i

= 0, the system

(

14.6

)

= px

+rx

= qx

k−1

+ px

+rx

k+1

, k ≥ 2. (14.7)

Show that the second line of

(

14.7

)

has the form

= αx

k+1

+ βx

k−1

, k ≥ 2. (14.8)

Verify that the solution to

(

14.8

)



B((β/α)

− 1) if q = r

Bk if q = r,

(14.9)

where α = r/(q + r),β = q/(q + r).

Hence, show that if q < r, the chain is transient and the queue size

goes to inﬁnity.

244 Markov Processes

Now consider the problem of computing an invariant distribution

π =

(

)

satisfying π



p = π. Using the structure of p we get π

απ

k−1

+ βπ

k+1

(k ≥ 1).



A + B

(

α/β

)

if r = q

A + Bk if r = q

for k ≥ 2. Show that (a) if q < r, there is no stationary distribution,

(b) if q = r , there is again no stationary distribution, and (c) if q > r ,

compute π =

(

)

. Show that there is a “small” probability of a large

queue length.

(f) Suppose that the states are 0, 1, 2,...and the transition matrix is

p =







00...

0 p

0 ...

00p

...

.. .. .. .. . . .







where p

and q

are positive. The state i represents the length of a success

run, the conditional chance of a further success being p

. A solution

of the system

(

14.6

)

for checking transience must have the form x

/ p

···p

k−1

, and so there is a bounded, nontrivial solution if and only

if 

k=1

(

1 − q

)

is bounded away from 0, which holds if and only if



< ∞. Thus the chain is recurrent if and only if



=∞.

Any solution of the steady state equations π



p = π has the form

= π

···p

k−1

, and so there is a stationary distribution if and only



···p

converges.

(5) Analyze the Markov chain with the following transition matrix

> 0 for i = 0, 1, 2,...).

p =







...

100...

010...

001...

... ... ... ...







[Hint: Concentrate on the case when the process starts from state 0.]

Random Dynamical Systems

One way which I believe is particularly fruitful and promising is to study what

would become of the solution of a deterministic dynamic system if it were

exposed to a stream of erratic shocks that constantly upsets the evolution.

Ragnar Frisch

3.1 Introduction

A random dynamical system is described by a triplet (S,,Q) where

S is the state space,  an appropriate family of maps from S into itself

(interpreted as the set of all admissible laws of motion), and Q is a

probability distribution on (some sigmaﬁeld of) . The evolution of

the system is depicted informally as follows: initially, the system is in

some state x in S; an element α

of  is chosen by Tyche according

to the distribution Q, and the system moves to the state X

= α

(x)in

period 1. Again, independently of α

, Tyche chooses α

from  according

to the same Q, and the state of the system in period 2 is obtained as

= α

), and the story is repeated. The initial state x can also be a

random variable X

chosen independently of the maps α

. The sequence

so generated is a Markov process. It is an interesting and signiﬁcant

mathematical result that every Markov process on a standard state space

may be represented as a random dynamical system. Apart from this

formal proposition (see Complements and Details, Proposition C1.1),

many important Markov models in applications arise, and are effectively

analyzed, as random dynamical systems. It is the purpose of this chapter

to study the long-run behavior of such systems from a uniﬁed point of

view. We identify conditions under which there is a unique invariant

distribution, and, furthermore, study the stability of the process. The

formal deﬁnitions are collected in Sections 3.2 and 3.3. We move on to

245

246 Random Dynamical Systems

discuss the role of uncertainty in inﬂuencing the evolution of the process

through simple examples in Section 3.4. Two general themes – splitting

and average contraction – are developed in later sections. Applications

and examples are treated in some detail.

This chapter is largely self-contained, that is, independent of Chap-

ter 2.

3.2 Random Dynamical Systems

Let S be a metric space and S be the Borel sigmaﬁeld of S. Endow ,

a family of maps from S into S, with a sigmaﬁeld  such that the map

(γ,x) → (γ (x)) on ( × S,⊗ S) into (S, S) is measurable. Let Q

be a probability measure on (, ).

On some probability space (, F, P), let (α

)

∞

n=1

be a sequence of

random functions from  with a common distribution Q.Foragiven

random variable X

(with values in S), independent of the sequence

(α

)

∞

n=1

, deﬁne

≡ α

) ≡ α

, (2.1)

n+1

= α

n+1

) ≡ α

n+1

···α

(n ≥ 0). (2.2)

We write X

(z) for the case X

= z. Then X

is a Markov process with

a stationary transition probability p(x, dy) given as follows: for x ∈ S,

C ∈ S,

p(x, C) = Q({γ ∈ : γ (x) ∈ C}). (2.3)

Recall that (see Deﬁnition 11.1 of Chapter 2) the transition probability

p(x, dy) is said to be weakly continuous or to have the Feller prop-

erty if for any sequence x

converging to x, the sequence of probability

measures p(x

, ·) converges weakly to p(x, ·). One can show that if 

consists of a family of continuous maps, p(x, dy) has the Feller property

(recall Example 11.2 of Chapter 2 dealing with a ﬁnite ): if x

→ x, then

Tf(x

) ≡ Ef(α

) → Ef(α

, x) ≡ Tf(x), for every bounded contin-

uous real-valued function f on S. To see this, note that α

(ω) is a contin-

uous function on S (into S) for every ω ∈ , so that α

(ω)x

→ α

(ω)x.

This implies f (α

(ω)x

) → f (α

(ω)x). Taking expectation, the result

follows.

3.3 Evolution 247

3.3 Evolution

To study the evolution of the process (2.2), it is convenient to recall

the deﬁnitions of a transition operator and its adjoint. Let B(S) be the

linear space of all bounded real-valued measurable functions on S. The

transition operator T on B(S) is given by (see Chapter 2, Deﬁnition 9.1)

(Tf )(x) =

f (y) p(x, dy), f ∈ B (S), (3.1)

and T

∗

is deﬁned on the space M(S) of all ﬁnite signed measures on

(S, S)by

∗

µ(C) =

p(x, C)µ(dx) =



µ(γ

−1

C)Q(dγ ),µ∈ M(S).

(3.2)

As before, let P(S) be the set of all probability measures on (S, S). An

element π of P(S)isinvariant for p(x, dy) (or for the Markov process

) if it is a ﬁxed point of T

∗

, i.e.,

π is invariant iff T

∗

π = π. (3.3)

Now write p

(n)

(x, dy) for the n-step transition probability with p

(1)

≡

p(x, dy). Then p

(n)

(x, dy) is the distribution of α

···α

x. Recall that

∗n

is the nth iterate of T

∗

∗n

µ = T

∗(n−1)

∗

µ)(n ≥ 2), T

∗1

= T

∗

, T

∗0

= identity. (3.4)

Then for any C ∈ S,

∗n

µ)(C) =

(n)

(x, C)µ(dx), (3.5)

so that T

∗n

µ is the distribution of X

when X

has distribution µ.To

express T

∗n

in terms of the common distribution Q of the i.i.d. maps, let



denote the usual Cartesian product  ×  ×···× (n terms), and let

be the product probability Q × Q ×···×Q on (



⊗n

), where



⊗n

is the product sigmaﬁeld on 

. Thus Q

is the ( joint) distribution

of α = (α

,α

,...,α

). For γ = (γ

,γ

,...,γ

) ∈ 

, let ˜γ denote

the composition

˜γ := γ

n−1

···γ

. (3.6)

Then, since T

∗n

µ is the distribution of X

= α

···α

, one has,

∗n

µ)(A) = Prob(X

∈ A) = Prob(X

∈ ˜α

−1

A), where ˜α = α

248 Random Dynamical Systems

n−1

···α

, and by the independence of ˜α and X

∗n

µ)(A) =



µ(˜γ

−1

A)Q

(dγ )(A ∈ S,µ∈ P(S)). (3.7)

Finally, we come to the deﬁnition of stability.

Deﬁnition 3.1 A Markov process X

is stable in distribution if there

is a unique invariant probability measure π such that X

(x) converges

in distribution to π irrespective of the initial state x, i.e., if p

(n)

(x, dy)

converges weakly to the same probability measure π for all x. In the case

one has (1/n)



m=1

(m)

(x, dy) converging weakly to the same invariant

π for all x, we may deﬁne the Markov process to be stable in distribution

on the average.

3.4 The Role of Uncertainty: Two Examples

Our ﬁrst example contrasts the steady state of a random dynamical system

(S,,Q) with the steady states of deterministic laws of .

Example 4.1 Let S = [0, 1] and consider the maps

f and

f on S into

S deﬁned by

f (x) = x/2

f (x) = x/2 +

Now, if we consider the deterministic dynamical systems (S,

f ) and

(S,

f ), then for each system all the trajectories converge to a unique

ﬁxed point (0 and 1, respectively) independently of initial condition.

Think of the random dynamical system (S,,Q) where  ={

f ,

f }

and Q({

f }) = p > 0, Q({

f }) = 1 − p > 0. It follows from Theorem

5.1 that, irrespective of the initial x, the distribution of X

(x) converges

in the Kolmogorov metric (see (5.3)) to a unique invariant distribution π,

which is nonatomic (i.e., the distribution function of π is continuous).

Exercise 4.1 If p =

, then the uniform distribution over [0, 1] is the

unique invariant distribution.

The study of existence of a unique invariant distribution and its sta-

bility is relatively simple for those cases in which the transition proba-

bility p(x, dy) has a density p(x, y), say, with respect to some reference

3.4 The Role of Uncertainty: Two Examples 249

measure µ(dy) on the state space S. We illustrate a dramatic difference

between the cases when such a density exists and when it does not.

Example 4.2 Let S = [−2, 2] and consider the Markov process

n+1

= f (X

) + ε

n+1

n ≥ 0,

where X

is independent of {ε

}, and {ε

}is an i.i.d. sequence with values

in [−1, 1] on a probability space (, F, P), and

f (x) =



x + 1if−2 ≤ x ≤ 0,

x − 1if0< x ≤ 2.

First, let ε

be Bernoulli, i.e.,

P(ε

= 1) =

= P(ε

=−1).

By direct computation (see Bhattacharya and Waymire 1990, p. 181 for

details), one can verify that if x ∈ (0, 2], {X

(x), n ≥ 1} is i.i.d. with

a common (two-point) distribution π

. In particular, π

is an invariant

distribution. It assigns mass

each to {x − 2}and {x}. On the other hand,

if x ∈ [−2, 0], then {X

(x), n ≥ 1} is i.i.d. with a common distribution

x+2

, assigning mass

to {x + 2}and {x}. Thus, there is an uncountable

family of mutually singular invariant distributions {π

:0< x < 1}∪

{π

x+2

: −1 ≤ x ≤ 0}.

On the other hand, suppose ε

is uniform over [−1, 1], i.e., has the

density

on [−1, 1] and 0 outside. One can check that {X

(x), n ≥ 1}

is an i.i.d. sequence whose common distribution does not depend on x,

and has a density

π(y) =

2 −

, −2 ≤ y ≤ 2.

The same is true of the sequence {X

2n+1

(x): n ≥ 1}. Thus, π(y)dy is

the unique invariant probability and stability holds.

Remark 4.1 Example 4.2 illustrates the dramatic difference between the

cases when ε

assumes a discrete set of values, and when it has a density

(with respect to the Lebesgue measure), in the case of a nonlinear trans-

fer function f on an interval S. One may modify the above function f

near zero, so as to make it continuous, and still show that the above phe-

nomena persist. See Bhattacharya and Waymire (1990, Exercise II.14.7,

p. 212).

250 Random Dynamical Systems

3.5 Splitting

3.5.1 Splitting and Monotone Maps

Let S be a nondegenerate interval (ﬁnite or inﬁnite, closed, semiclosed,

or open) and  a set of monotone maps from S into S; i.e., each element

of  is either a nondecreasing function on S or a nonincreasing function.

We will assume the following splitting condition:

(H) There exist z

∈ S,˜χ

> 0(i = 1, 2) and a positive N such

that

(1) P(α

N −1

···α

x  z

∀x ∈ S)  ˜χ

(2) P(α

N −1

···α

x  z

∀x ∈ S)  ˜χ

Note that conditions (1) and (2) in (H) may be expressed, respectively,

({γ ∈ 

: ˜γ

−1

[x ∈ S: x ≤ z

] = S})  ˜χ

, (5.1)

and

({γ ∈ 

: ˜γ

−1

[x ∈ S: x ≥ z

] = S})  ˜χ

. (5.2)

Here ˜γ = γ

N −1

··· γ

The splitting condition (H) remains meaningful when applied to

a Borel subset S of



with the partial order x ≤ y if x

≤ y

for

all i = 1....,  (x = (x

,...,x



), y = (y

...,y



) ∈ S). One writes x ≥ y

if y ≤ x. Thus a monotone function f : S → S is one such that either (i)

f (x) ≤ f (y)ifx ≤ y (monotone nondecreasing), or (ii) f (x) ≥ f (y)if

x ≤ y (monotone nonincreasing).

The following remarks clarify the role of the splitting condition:

Remark 5.1 Let S = [a, b] and α

(n  1) a sequence of i.i.d. continu-

ous nondecreasing maps on S into S. Suppose that π is the unique invari-

ant distribution of the Markov process (see Theorem 11.1 in Chapter 2).

If π is not degenerate, then the splitting condition holds. We verify this

claim. Since p

(n)

(x, dy) is the distribution of X

(x) = α

···α

x,itis

therefore also the distribution of Y

(x) = α

···α

x. Note that Y

n+1

(a) =

···α

n+1

a  α

···α

a = Y

(a) (since α

n+1

a  a). Let Y

the limit of the nondecreasing sequence Y

(a)(n  1). Then p

(n)

(a, dy)

converges weakly to the distribution π

,say,ofY

. Similarly, Y

n+1

(b) 

(b) ∀n, and the nonincreasing sequence Y

(b) converges to a limit

Y , so that p

(n)

(b, dy) converges weakly to the distribution ¯π of

Y .By

3.5 Splitting 251

uniqueness of the invariant π, π = ¯π = π. Since Y



Y , it follows that

Y (a.s.) = Y , say. Assume π is not degenerate. Then there ex-

ist a



, b



∈ (a, b), a



< b



such that P(Y < a



) > 0 and P(Y > b



) > 0.

Since Y

(a) ↑ Y and Y

(b) ↓ Y , there exists a positive integer N such

that (i) ˜χ

:= P(Y

(b) < a



) > 0, and (ii) ˜χ

:= P(Y

(a) > b



) > 0.

But then P(X

(x) < a



∀x ∈ [a, b]) = P(Y

(x) < a



∀x ∈ [a, b]) =

P(Y

(b) < a



) = ˜χ

, and P(X

(x) > b



∀x ∈ [a, b]) = P(Y

(x) > b



∀x ∈ [a, b]) = P(Y

(a) > b



) = ˜χ

. Choose any z

in (a



, b



). The split-

ting condition is now veriﬁed. The assumption of continuity of α

may

be dispensed with here since, as shown in Complements and Details (see

Lemma C5.2), if α

are monotone nondecreasing and p

(n)

(x, dy) con-

verges weakly to π (dy) for every x ∈ S, then π is the unique invariant

probability on [c, d].

Remark 5.2 We say that a Borel subset A of S is closed under p if

p(x, A) = 1 for all x in A. If the state space S has two disjoint closed

subintervals that are closed under p or under p

(n)

for some n, then the

splitting condition does not hold. This is the case, for example, when

these intervals are invariant under α almost surely.

Denote by d

(µ, ν) the Kolmogorov distance on P(S). That is, if F

denote the distribution functions (d.f.) of µ and ν, respectively, then

(µ, ν):= sup

x∈R

|µ((−∞, x] ∩ S) −ν(−∞, x] ∩ S)|

≡ sup

x∈R

(x) − F

(x)|, µ, ν ∈ P((S)). (5.3)

Remark 5.3 It should be noted that convergence in the distance d

P(S) implies weak convergence in P(S). (See Theorem C11.2(d) of

Chapter 2.)

Theorem 5.1 Assume that the splitting condition (H) holds on a nonde-

generate interval S.

Then

(a) the distribution T

∗n

µ of X

:= α

···α

converges to a proba-

bility measure π on S exponentially fast in the Kolmogorov distance d

irrespective of X

. Indeed,

∗n

µ, π )  (1 − ˜χ )

[n/N]

∀µ ∈ P(S), (5.4)

where ˜χ := min{˜χ

, ˜χ

} and [y] denotes the integer part of y.

252 Random Dynamical Systems

(b) π in (a) is the unique invariant probability of the Markov process

Proof. Suppose (H) holds, i.e., (5.1), (5.2) hold. Fix γ monotone, and

µ, ν ∈ P(S) arbitrarily. We will ﬁrst show that, for all x,

|µ(γ

−1

(−∞, x]) − ν(γ

−1

(−∞, x])|  d

(µ, ν). (5.5)

For this, note that the only possibilities are the following:

(i) γ

−1

(−∞, x] = φ (i.e., γ (z) > x∀z ∈ S),

(ii) γ

−1

(−∞, x] = (−∞, y] ∩ S,

(iii) γ

−1

(−∞, x] = (−∞, y) ∩ S,

(iv) γ

−1

(−∞, x] = [ y, ∞) ∩ S,

(v) γ

−1

(−∞, x] = ( y, ∞) ∩ S.

If γ

−1

(−∞, x] = φ, then cases (ii) and (iii) may arise when γ is

nondecreasing, and cases (iv) and (v) may arise when γ is nonincreasing.

In case (i), the left-hand side of (5.5) vanishes. In case (ii), (5.5) holds

by deﬁnition. In case (v), (5.5) holds by complementation:

|µ((y, ∞) ∩ S) − ν((y, ∞) ∩ S)|

=|1 − µ((−∞, y] ∩ S) − (1 − ν((−∞, y] ∩ S))|

=|ν((−∞, y] ∩ S) − µ((−∞, y] ∩ S)|

 d

(µ, ν).

To derive (5.5) in case (iii), let y

↑ y ( y

< y) ∀n. Then

|µ((−∞, y) ∩ S) − ν((−∞, y) ∩ S)|

= lim

n→∞

|µ((−∞, y

] ∩ S) − ν((−∞, y

] ∩ S)|  d

(µ, ν).

For the remaining case (iv), use the result for the case (iii) and com-

plementation. Thus (5.5) holds in all cases. Taking supremum over x in

(5.5), we get (see (3.7))

∗

µ, T

∗

ν) = sup

x∈R

)



(µ(γ

−1

(−∞, x]) − ν(γ

−1

(−∞, x]))Q(dγ )

)

 d

(µ, ν). (5.6)