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

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

2.8 Recurrence and Steady State Distributions 173

Because the states are aperiodic, there exist n

, n



such that p

(n)

> 0

∀n

 n

and p

(n)



> 0 ∀n  n



(by part (b) of the lemma). This im-

plies p

+n)

> 0 ∀n  n

and p

+n)



> 0 ∀n  n



.Ifm is an integer

greater than both n

+ n

and n

+ n



, then it follows that p

(m)

> 0 and

(m)



> 0, so that the m-step transition probability

(m)

(i ,i



),( j, j



)

≡ p

(m)





= Prob((X

, X



) = ( j, j



) | (X

, X



) = (i, i



))



> 0,

establishing irreducibility of p

. Since p

has an invariant probability

π × π, it now follows that the Markov chain on S × S is recurrent.

Consider now the chain {(X

, X



): n  0} as above, with X

≡ i and



having the distribution π . Deﬁne

τ := inf{n

 0: X

= X



}. (8.41)

Then Prob(τ<∞) = 1, by recurrence and aperiodicity of the chain on

S × S. Also, τ is a stopping time for {(X

, X



): n  0}, i.e., {τ = m} be-

longs to the sigmaﬁeld σ ({X

, X



): 0 ≤ n ≤ m})(m = 1, 2,...). Now

modify {X



: n  0} as follows:



if n <τ,

if n  τ,

(n = 0, 1,...). (8.42)

By the strong Markov property of {(X

, X



): n  0} (see Theorem 6.2),

: n  0} has the same distribution as {X



: n  0}. For every A ⊂ S,

one has

)



j∈A

(n)

− π

)

=|P(X

∈ A) − P(Y

∈ A)|

=|P(X

∈ A, Y

= X

) + P(X

∈ A, Y

= X

)

−P(Y

∈ A, X

= Y

) − P(Y

∈ A, X

= Y

=|P(X

∈ A, Y

= X

) − P(Y

∈ A, X

= Y

≤ P(X

= Y

)

≤ P(τ>n). (8.43)

Letting A be in turn, I

: ={j ∈ S: p

(n)

 π

}, I

−

: ={j ∈ S: p

(n)

}, and adding up, one then gets (8.40).

174 Markov Processes

Exercise 8.6 Show that τ, deﬁned by (8.41), is a stopping time for the

chain {(X

, X



): n  0}. [Hint: τ = T

, where D :={(i, i): i ∈ S}is the

diagonal set in S × S and T

is the ﬁrst passage time to D.]

Example 8.4 (A thermostat model of managerial behavior) Consider

a manager supervising an activity, who decides at the beginning of each

period t = 0, 1,... whether or not to allocate effort during the period

to improving the operation of the activity. Let U(t) denote a measure of

performance of the activity in period t. The sequence U(t) is assumed to

be a stochastic process. During a period in which the manager makes an

effort to improve the activity, performance can be expected to improve,

at least on the average, whereas during a period in which the manager

makes no such effort, performance can be expected to deteriorate. The

situation is formally modeled as follows. Let {X(t)} and {Y (t)} each be a

sequence of independent, identically distributed random variables, with

the two sequences mutually independent. Let

EX(t) = ξ<0

EY(t) = η>0. (8.44)

If an improvement effort is made in period t, then the increment in per-

formance is Y (t), whereas if no such effort is made, the increment in

performance is X(t). Let a(t) denote the manager’s allocation of im-

provement (action) effort in period t, with a(t) = 1 denoting an effort

and a(t) = 0 denoting no effort. Then

Z(t) ≡ U (t

) − U (t − 1)

= a(t)Y (t) + [1 − a(t)]X (t). (8.45)

A behavior is a sequence of functions A

, which determine the man-

ager’s actions on the basis of past performance levels. Thus, A

is a

function of U(0),...,U (t − 1) and takes values 0 and 1 and

a(t) = A

[U(0),...,U (t − 1)], t = 1, 2,.... (8.46)

A simple behavior, which is similar to that of a thermostat with ﬁxed up-

per and lower settings, say A and B, respectively, is the following. If the

initial performance level U(0) is less than A, then the manager makes an

improvement effort until the ﬁrst time that performance reaches or goes

above A. At that time the manager ceases effort until the performance

drops to or below B. The manager then renews his improvement effort

2.8 Recurrence and Steady State Distributions 175

until performance reaches or goes above A, etc. If the initial performance

level U (0) is at least A, then the manager starts with no effort and pro-

ceeds as above. This is called the conservative thermostat behavior, with

settings A and B(A > B). Formally, for t ≥ 1,

if a(t − 1) = 0, then a(t) =





as U(t − 1) =



≤



if a(t − 1) = 1, then a(t) =





as U(t − 1) =



≥



A. (8.47)

We will assume A − B > 2.

Given the manager’s behavior, and the distributions of the random

variables X(t) and Y (t), we are interested in the long-run properties

of the sequence {

U (t)} of performance levels and the sequence {a(t)}

of actions, for example, the long-run average level of performance and

the long-run frequency of periods in which an improvement effort is

made. The following simplifying assumptions are made about the random

variables X(t) and Y (t):

X(t) and Y (t) can take only the values −1, 0, and +1 with

Prob{X(t) =+1}=p

, Prob{Y (t) =+1}=p

Prob{X(t) = 0}=r

, Prob{Y (t) = 0}=r

Prob{X(t) =−1}=q

, Prob{Y (t) =−1}=q

. (8.48)

+ q

= p

+ q

=1 p

> 0, q

> 0, r

> 0 i =0, 1.

Thus, performance can change by at most one unit in any time period,

irrespective of improvement effort, and we have

ξ = EX(t) = p

− q

< 0,

η = EY(t) = p

− q

> 0. (8.49)

The sequence of pairs [a(t), U (t)] is a Markov chain. The state space of

this chain in the set S ={(a, U ): a = 0, 1, and U an integer, B ≤ U ≤ A}

∪{(1, U): U an integer, U < B}∪{(0, U ): U an integer, U > A}.

176 Markov Processes

Thus, the state space S is countably inﬁnite and it is irreducible and

aperiodic. Note that aperiodicity follows from r

> 0(i = 0, 1).

We will show that (0, B)isapositive recurrent state, which would

then imply that all states are positive recurrent, in view of irreducibil-

ity (Theorem 8.1). Now, starting from (0, B) one has a(t) = 1 ∀t until

the time η

(0,A)

of the ﬁrst visit to (0, A). During this period U (t) =

U (t − 1) +Y (t)(1 ≤ t ≤ η

(0,A)

), behaving as the simple random walk

of Example 6.3, with E

(0,B)

(0,A)

= (A − B)/( p

− q

). Similarly, start-

ing from (0, A), U(t) = U (t − 1) + X (t) until U (t) reaches (0, B) (i.e.,

for 1 ≤ t ≤ η

(0,B)

). Again, by the ﬁnal computations in Example 6.3,

(0,A)

(0,B)

= (A − B)/(q

− p

). Hence

(0,B)

≤ E

(0,B)

(0,A)

+ E

(0,A)

(0,B)

< ∞,

proving the desired positive recurrence. By Theorem 8.2, there exists a

unique invariant probability π = (π

: j ∈ S), and



j∈S

)

(n)

− π

)

→ 0asn →∞, ∀i ∈ S. (8.50)

Note that if r

= 0 = r

, the chain is still irreducible and the proof

of positive recurrence remains unchanged. But the chain is no longer

aperiodic. One then applies Theorem 8.1 to infer the existence of a unique

invariant probability π and, in place of (8.50), the convergence

lim

n→∞



j∈S

)



m=1

(m)

− π

)

= 0 ∀i ∈ S. (8.51)

Exercise 8.7 Write down the transition probabilities of the Markov chain

in Example 8.4.

2.9 Markov Processes on Measurable State Spaces: Existence

of and Convergence to Unique Steady States

This section is devoted to the extension to general state spaces of two

of the main results for Markov chains, namely, Theorem 5.1 (or Corol-

lary 5.1) and Theorem 8.1.

Let the state space S be a nonempty set, and S a sigmaﬁeld on it, i.e.,

(S, S)isameasurable space. For example, S may be

or [0, ∞)

(k ≥

1), or a compact interval [c, d], in which cases S is the Borel sigmaﬁeld

2.9 Markov Processes on Measurable State Spaces 177

of S;orS may be a countable set, and S the class of all subsets of S,as

considered in the preceding sections. Let p(x, A)(x ∈ S, A ∈ S)bea

transition probability on (S, S). As before, we will denote by {X

: n =

0, 1, 2,...,} a Markov process on (S, S) with transition probability p,

deﬁned on some probability space (, F, P).

Deﬁnition 9.1 The transition operator T of a Markov process {X

} is

the linear map on the space B(S) of all real-valued bounded measur-

able functions on S deﬁned by (Tf)(x) = E( f (X

n+1

| X

= x)(n  0).

That is,

(Tf)(x):=

f (y) p(x, dy), ( f ∈ B(S)). (9.1)

Its adjoint T

∗

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

on (S, S) into itself by

∗

µ(A) =

p(x, A)µ(dx). (9.1



)

Note that T

∗

maps P(S), the set of all probability measures on (S, S),

into itself. For m ≥ 1, T

∗m

is the mth iterate of T

∗

. Observe that X

has

the distribution T

∗m

µ if X

has distribution µ.

For the bilinear functional ( f,µ):=

fdµ,

(Tf,µ) = ( f, T

∗

µ)( f ∈ B(S),µ∈ M(S)) (9.1



)

justifying the notation T

∗

as the adjoint of T .

Theorem 9.1 (Doeblin minorization) Let p(x, A) be a (one-step) tran-

sition probability on a measurable state space (S, S) such that there

exist N ≥ 1 and some nonzero measure λ for which the N-step transi-

tion probability p

(N )

satisﬁes

(N )

(x, A) ≥ λ(A) ∀x ∈ S, A ∈ S. (9.2)

Then there exists a unique invariant probability π for p, and one has

sup

x∈S,A∈S

(n)

(x, A) − π (A)|≤(1 − ¯χ)

[

]

, n ≥ 1, (9.3)

where ¯χ = λ(S) > 0.

Proof. Note that λ(S) ≤ p

(N )

(x, S) = 1. If λ(S) = 1, then p

(N )

(x, A) =

λ(A) ∀x ∈ S, A ∈ S. In other words, π := λ is an invariant probability

178 Markov Processes

for p

(N )

(since p

(N )

(x, A) does not depend on x); also, p

(n)

(x, A) =

(N )

(y, A)p

(n−N)

(x, dy) = λ(A) ∀n ≥ N . This establishes (9.3), with

both sides equal to zero for n ≥ N and, interpreting 0

= 1 takes care of

the case n < N .

Consider now the important and nontrivial case 0 < ¯χ<1. Deﬁne

the distance d

on P(S)by

(µ, ν)

= sup



)

fdµ −

fdν

)

: f measurable, sup

| f (x)|≤1



. (9.4)

For the proof of the theorem, ﬁrst note that

∗m

µ, T

∗m

ν) ≤ d

(µ, ν), (m ≥ 1,µ,ν ∈ P(S)) (9.5)

since, x → g(x):=

f (y) p

(m)

(x, dy) is bounded by 1, if f is bounded

by one.

Next, write

(N )

(x, A) = λ(A) + (p

(x, A) − λ(A))

= ¯χλ

¯χ

(A) +(1 − ¯χ)q

¯χ

(x, A), (9.6)

where λ

¯χ

is the probability measure λ

¯χ

= λ/ ¯χ, and q

¯χ

(x, A) ≡

(N )

(x, A) − λ(A))/(1 − ¯χ) is a transition probability (i.e., x →

¯χ

(x, A) is a probability measure on (S, S) for every x ∈ S, and x →

¯χ

(x, A) is measurable for every A ∈ S). Then, for every measurable

real-valued f on S, with | f (x)|≤1 ∀x ∈ S, one has

f (y) p

(N )

(x, dy) = ¯χ

f (y)λ

¯χ

(dy) + (1 − ¯χ)

f (y)q

¯χ

(x, dy),

(9.7)

so that

f (x)(T

∗N

µ)(dx) = ¯χ



f (y)λ

¯χ

(dy)



µ(dx)

+(1 − ¯χ)



f (y)q

¯χ

(x, dy)



µ(dx),

(µ ∈ P(S)). (9.8)

2.9 Markov Processes on Measurable State Spaces 179

Therefore, writing g(x) =

f (y)q

¯χ

(x, dy), one has

)

fd(T

∗N

µ) −

fd(T

∗N

ν)

)

= (1 − ¯χ)

)

g(x)µ(dx) −

g(x)ν(dx)

)

≤ (1 − ¯χ)d

(µ, ν), (µ, ν ∈ P(S)), (9.9)

since |g(x)|≤1. Thus,

∗N

µ, T

∗N

ν) ≤ (1 − ¯χ)d

(µ, ν), (µ, ν ∈ P(S). (9.10)

Iterating (9.10) k times, one gets

∗kN

µ, T

∗kN

ν) ≤ (1 − ¯χ)

(µ, ν), (k = 1, 2,...). (9.11)

Combining this with (9.5) for 1 ≤ m < n, one arrives at

∗n

µ, T

∗n

ν) ≤ (1 − ¯χ)

[

]

(µ, ν), n ≥ 1. (9.12)

Now (9.10) says T

∗N

is a uniformly strict contraction so that, by the

contraction mapping theorem (Theorem 2.2, Chapter 1), T

∗

has a unique

ﬁxed point π: T

∗

π = π. Therefore, by (9.12) with (ν = π),

∗n

µ, π ) ≤ (1 − ¯χ )

[

]

(µ, π )(n ≥ 1). (9.13)

In particular, with µ = δ

in (9.13) (δ

is the Dirac probability measure

at x, δ

({x}) = 1),

(n)

(x, dy),π) ≤ (1 − ¯χ)

[

]

(δ

,π). (9.14)

Since (see Remark 9.2)

sup

A∈S

|µ(A) −ν(A)|=

(µ, ν), (9.15)

(9.3) follows from (9.14).

Remark 9.1 An alternative proof based on a general theorem on “split-

ting” is given (for the case of S, a Borel subset of a Polish space) in

Chapter 3 (Section 3.5.3).

Remark 9.2 To prove (9.15), let f be a simple function



i=1

where |α

|≤1 ∀

, and A

,...,A

are disjoint. Then, writing I

for the

180 Markov Processes

set of i such that µ(A

) ≥ ν(A

) and I

−

for those with µ(A

) <ν( A

)

fdµ−

fdν

)



i∈I

(µ(A

)−ν(A

))+



i∈I −

(µ(A

)−ν(A

))

)

≤

)



i∈I

(µ(A

)−ν(A

))

)



i∈I −

(µ(A

)−ν(A

))

)

≤



i∈I

|α

|(µ(A

)−ν(A

))+



i∈I −

|α

|(ν(A

)−µ(A

))

≤



i∈I

(µ(A

) − ν(A

)) +



i∈I −

(ν(A

) − µ( A

))

= µ( A

) − ν(A

) + ν(A

−

) − µ( A

−

)

:=∪

i∈I

, A

−

:=∪

i∈I

−

]

≤ 2 sup{|µ( A) − ν(A)|: A ∈ S}. (9.16)

Hence d

(µ, ν) ≤ 2 sup{|µ(A) − ν(A)|: A ∈ S}. Conversely, for an ar-

bitrary A ∈ S, let f = 1

− 1

, i.e., f = 1onA and −1onA

,so

that

)

fdµ −

fdν

)

=|µ(A ) − µ(A

) −{ν(A) −ν(A

)}|

=|µ(A ) − ν( A) −{µ(A

) − ν(A

)}|

=|µ(A ) − ν( A) −{1 − µ( A) − (1 −ν(A))}|

=|2(µ(A ) − ν( A))|=2|µ(A) − ν( A)|.

(9.17)

Hence, taking supremum over A ∈ S,weget

(µ, ν) ≥ 2 sup{|µ(A) − ν(A)|: A ∈ S},

establishing (9.15).

Remark 9.3 For the application of the contraction mapping theorem

(Theorem 2.1, Chapter 1), one needs to show that the metric space

(P(S), d

) is complete. For this, let {µ

: n ≥ 1} be a Cauchy sequence

for the metric d

, and deﬁne µ(A):= lim

n→∞

(A), A ∈ S (this limit

exists due to the completeness of the set [0,1] of real numbers). From this

the properties 0 ≤ µ( A) ≤ 1(A ∈ S),µ(S) = 1, and ﬁnite additivity of

2.9 Markov Processes on Measurable State Spaces 181

µ follow immediately. Since the convergence µ

(A) → µ(A) is uniform

for A ∈ S, countable additivity of µ follows from that of the µ

(n  1).

Thus µ ∈ P(S) and µ

−→ µ.

Observe that Theorem 5.1 and Corollary 5.1 in Section 2.5 follow

immediately from Theorem 9.1.

Another proof of Theorem 9.1 may be based on the following result,

which is of independent interest. To state it we deﬁne



n,m

: = sup

x,y∈S, AεS

)

(n)

(x, A) − p

(m)

(y, A)

)



: = 

n,n

. (9.18)

Proposition 9.1 A necessary and sufﬁcient condition for the exponential

convergence of p

(n)

(x, dy) to a probability measure π in the distance

, uniformly for all x ∈ S, is that there exists some N ≥ 1 such that



< 1. In this case π is the unique invariant probability for p(x, dy).

Proof. To prove necessity, suppose p

(n)

(x, dy) converges to π(dy)in

the distance d

exponentially fast, uniformly for all x ∈ S. Then there

exists N ≥ 1 such that

(N )

(x, ·),π) <

∀x ∈ S. (9.19)

By (9.15) and (9.19),

)

(N )

(x, A)−p

(N )

(y, A)

)

≤

)

(N )

(x, A)−π(A)

)

(N )

(y, A)−π(A)

)

≤



(N )

(x, ·),π





(N )

(y, ·),π



∀x ∈ S∀∈S.

(9.20)

Hence 

To prove sufﬁciency, ﬁrst write µ

(A; x, y) = p

(n)

(x, A) − p

(n)

(y, A),

and let µ

(A; x, y) − µ

−

(A; x, y) be the Jordan–Hahn decomposition of

the signed measure µ

(·; x, y) (see Lo`eve 1963, pp. 86–87).

182 Markov Processes

Recall that µ

(S; x, y) = sup{µ

(A; x, y): A ∈ S}≤

. Also, since

(S; x, y) = 0, one has µ

(S; x, y) = µ

−

(S; x, y). Therefore,

(n+m)

(x, A) − p

(n+m)

(y, A)

(m)

(z, A)



(n)

(x, dz) − p

(n)

(y, dz)



(m)

(z, A)



(dz; x, y) − µ

−

(dz; x, y)



≤ sup{p

(m)

(z, A): z ∈S}µ

(S; x, y)

−inf



(m)

(z, A):z ∈S



−

(S; x, y)

= µ

(S; x, y)



sup



(m)

(z, A):z ∈ S



− inf



(m)

(z, A): z ∈ S



= µ

(S; x, y)



sup



(m)

(x, A) − p

(m)

(y, A):x, y ∈ S



≤ 



. (9.21)

Interchanging x and y, one can take the absolute value on the left.

Taking supremum over x, y, A we arrive at the relation



n+m

≤ 



,

≤ 

[n/N]

(9.22)

since 

≤ 1 ∀r . Hence, if 

< 1, 

→ 0 exponentially fast as n →

∞. Next note that

(n+m)

(x, A)−p

(n)

(y, A)=

(n)

(z, A)−p

(n)

(y, A))p

(m)

(x, dz)

≤ sup



(n)

(z, A)−p

(n)

(y, A):z,y ∈ S



≤

Therefore,



n,n+m

≤ 

. (9.23)

Hence, for every x,

(n+m)

(x, ·), p

(n)

(x, ·)) ≤ 2

n,n+m

≤ 2

→ 0, (9.24)

implying the existence of a limit π,say,of p

(n)

(x, ·) in total variation

distance. Since 

→ 0, this limit is independent of x. On letting m →

∞ in (9.24) one gets

(n)

(x, ·),π) ≤ 2

≤ 2

[n/N]

. (9.25)

Now take supremum of the left-hand side over x ∈ S to obtain the desired

result.