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

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

2.13 Complements and Details 203

Proof. Fix a state j, and let B

={r ≥ 1: p

(r)

> 0}. Observe that B

is closed under addition. By hypothesis, g.c.d. of B

is 1. The set G

{m − n: m, n ∈ B

} is an additive subgroup of Z and is, therefore, of

the from d

Z ≡{dn: n ∈ Z} for some positive integer d. Since G

⊃ B

d = 1. For all elements of B

are divisible by d, so that g.c.d. of B

no less than d. Hence 1 ∈ G

. Therefore, there exists an integer r ≥ 1,

such that both r and r + 1 belong to B

(so that (r + 1) −r = 1 ∈ G

If n > (2r + 1)

+ 1, write n = t(2r + 1) + q, where q = 0, 1,...,2r

(and t ≥ 2r + 1). Then n may be expressed as n = (t + q)(r + 1) +

(t − q)r, with both (t + q)(r + 1) (a multiple of r + 1) and (t − q)r

(a multiple of r) belong to B

. Hence n ∈ B

Finally, for each i ∈ S, there exists n

such that p

)

> 0. It fol-

lows that p

(n+n

)

> 0 ∀n > (2r + 1)

+ 1. Let ν

= (2r + 1)

+ 2 +

max{n

: i ∈ S\{j}}.

Section 2.6. The class G, say, of sets F in the Kolmogorov sigmaﬁeld

F = S

⊗∞

for which (6.2) holds is easily seen to satisfy the following:

(i)  ∈ G, (ii) A, B ∈ G, A ⊂ B ⇒ B\A ∈ G, and (iii) G is closed under

monotone increasing and decreasing limits. Since the class A of ﬁnite-

dimensional sets in S

⊗∞

is a ﬁeld, and A ⊂ G, it follows by a standard

monotone class theorem that σ (A) ⊂ G. But σ (A) = S

⊗∞

, by deﬁnition,

so that G = S

⊗∞

. (Note that this argument holds for Markov processes

on more general state spaces (S, S), in which case A is the class of all

measurable ﬁnite-dimensional sets.) See Billingsley (1986, pp. 36–39)

for the above monotone class theorem known as Dynkin’s π–λ theorem.

Also see Dynkin (1961).

Section 2.7. The statement that the random cycles, or blocks, W

(r)

, X

(r)

,...,X

(r+1)

), r ≥ 1, are i.i.d. is proved in detail as fol-

lows. Given any m ≥ 1 and states i

, i

,...,i

m−1

∈ S\{x}, the event

:={W

= (x, i

, i

,...,i

m−1

, x)} is the same as the event {η

(r+1)

(r)

+ m,(X

(r)

)

= i

for n = 1, 2,...,m − 1}. By the strong Markov

property, the conditional probability of the last event, given the pre-η

(r)

sigmaﬁeld F

(r)

, is P

= i

, X

= i

,...,X

m−1

= i

m−1

, X

= x).

Since the latter (conditional) probability is a constant, i.e., nonrandom,

is independent of F

(r)

(and, therefore, of A

;0≤ j ≤ r − 1), and

since this probability does not depend on r, we have established that W

’s

are independent and have the same distribution (r ≥ 1).

204 Markov Processes

Theorem 7.2 was proved by Polya (1921). For a proof of Stirling’s

formula, see Feller (1968, pp. 52–54).

Section 2.8. We will solve Equation (8.24) for the expected time m(x)

to reach the boundary {c, d}, starting from x, c ≤ x ≤ d. For this

introduce u

= 1 +



x−1

y=c+1

c+1

···δ

/(β

c+1

···β

), c + 2 ≤ x ≤ d,

u(c) = 0, u(c + 1) = 1. Then (8.24) may be expressed as

m(x + 1) − m(x)

x+1

− u

−

m(x) −m(x − 1)

− u

x−1

=−

c+1

...β

c+1

...δ

, c + 1 ≤ x ≤ d − 1.

Summing over x = c + 1,...,y, yields

m(y + 1) − m(y)

y+1

− u

− m(c + 1)

=−



x=c+1

c+1

...β

c+1

...δ

, c + 1 ≤ y ≤ d − 1. (C8.1)

Multiplying both sides by u

y+1

− u

and then summing over y = d −

1,...,c + 1, one computes

m(c + 1) =



d−1

y=c+1



x=c+1

···δ

···β

1 +



d−1

y=c+1

c+1

···δ

c+1

···β

. (C8.2)

Multiplying (C8.1) by u

y+1

and summing (C8.1) over y = d − 1,...,x,

one ﬁnally arrives at

m(x) =

d−1



y=x



z=c+1

···δ

···β

− m(c + 1)

d−1



y=x

c+1

···δ

c+1

···β

, c + 1 ≤ x ≤ d − 1. (C8.3)

Turning to the Ehrenfest heat exchange problem in Example 8.3, let

m(x):= E

, when T

= inf{n ≥ 0: X

= d}. Then, as in the preceding

case, one has

(

m(x + 1) −

m(x))β

− (

m(x) −

m(x − 1))δ

=−1(1 ≤ x ≤ 2d − 1),

but with boundary conditions

m(d) = 0,

m(2d) −

m(2d − 1) = 1.

Solving it, in a manner analogous to that described above, one

2.13 Complements and Details 205

obtains

m(x) =



y=1

y+1

···β

2d−1

y+1

···δ

2d−1



y=1

2d−1



z=y

···β

···δ

,1≤ x ≤ 2d − 1,

m(0) = 0, m(2d) = 1 +m(2d − 1). (C8.4)

Here β

= 1 − y/2d,δ

= y/2d(1 ≤ y ≤ 2d − 1),β

= 0,δ

= 1.

In particular, the expected time to reach disequilibrium (namely, the

state 0 or 2d), starting from the equilibrium (namely, the state d) is easily

seen to be

m(d) =



1 + 0





, as d →∞. (C8.5)

On the other hand, the expected time

m(0) of reaching equilibrium (state

d) starting from the extreme disequilibrium state 0 (or 2d) may be shown,

in the same manner as above, to satisfy

m(0) ≤ d log d + d + 0(1) as d →∞. (C8.6)

For d = 10, 000 balls, and rate of transition 1 ball per second,

m(d) is nearly 10

6000

years,

m(0) < 29 hours. (C8.7)

A proof of Theorem 8.2 may be found in Kolmogorov (1936). Our

proof is adapted from Durrett (1996, pp. 82–83). The idea of meeting

together, or coupling, of two independent positive recurrent aperiodic

Markov chains {X

}

n≥0

, {X



}

n≥0

, having the same transition probability,

but one with initial state x and the other with the invariant initial distri-

butions, is due to Doeblin (1937). For the history behind the Ehrenfest

model, see Kac (1947). Also see Waymire (1982).

For comprehensive and standard treatments of Markov chains, we refer

to Doob (1953), Feller (1968), Chung (1967), and Karlin and Taylor

(1975, 1981). Our nomenclature of Markov chains as Markov processes

with countable state spaces follows these authors.

206 Markov Processes

Finally, specializing (C8.2) and (C8.3) to the case of the simple random

walk of Example 6.4, we get

m(x) =











(d−x )(x−c)

p+q

for c ≤ x ≤ d, if p = q,

d−c

p−q



1−

x−c

1−

d−c



−

x−c

p−q

, c ≤ x ≤ d, if p = q.

(C8.8)

Section 2.9. Consider a sequence {Y

: n ≥ 1} of i.i.d. positive integer-

valued random variables and Y

a nonnegative integer-valued random

variable independent of {Y

: n ≥ 1}. The partial sum process S

= Y

+···+Y

(k ≥ 1) deﬁnes the so-called delayed renewal process

: n ≥ 1}:

:= inf{k ≥ 0: S

≥ n}(n = 0, 1,...), (C9.1)

with Y

as the delay and its distribution as the delay distribution.Inthe

case Y

≡ 0, {N

: n ≥ 0} is simply referred to as a renewal process.

This nomenclature is motivated by classical renewal theory in which

components subject to failure (e.g., light bulbs) are instantly replaced

upon failure, and Y

, Y

,...,represent the random durations or lifetimes

of the successive replacements. The delay random variable Y

represents

the length of time remaining in the life of the initial component with

respect to some speciﬁed time origin. For a more general context consider,

as in Example 1, a Markov chain {X

: n ≥ 0} on a (countable) state

space S, and ﬁx a state y such that the ﬁrst passage time T

≡ η

(0)

state y is ﬁnite a.s., as are the successive return times η

(k)

to y(k ≥ 1).

By the strong Markov property, Y

:= η

(0)

, Y

: = η

(k)

− η

(k−1)

(k ≥ 1),

are independent, with {Y

: k ≥ 1} i.i.d. The renewal process may now

be deﬁned with S

= η

(k)

(k ≥ 1), the kth renewal occurring at time η

(k)

if η

(0)

= 0, i.e., y is the initial state. Let N

= inf{k ≥ 0:η

(k)

≥ n}.

It may be helpful to think of the partial sum process {S

: k ≥ 0} to

be a point process 0 ≤ S

< S

< ··· realized as a randomly lo-

cated increasing sequence of renewal times or renewal epochs on

{0, 1, 2,...}. The processes {S

: k ≥ 0} and {N

: n ≥ 0} may be thought

of as (approximate) inverse functions of each other on

. Another

related process of interest is the residual lifetime process deﬁned by

:= S

− n = inf{S

− n: k such that S

− n ≥ 0}. (C9.2)

The indices n for which R

= 0 are precisely the renewal times.

2.13 Complements and Details 207

Deﬁnition C9.1 A random variable τ taking values in Z

∪ {∞} is said

to be a {F

}

k≥0

-stopping time with respect to an increasing sequence of

sigmaﬁelds {F

: k ≥ 0} if {τ ≤ k}∈F

∀k ≥ 0. The pre-τ sigmaﬁeld

is deﬁned as the class of all events {A: A ∩ [τ = k]}∈F

∀k ≥ 0}.

Proposition C9.1 Let f be the probability mass function (p.m.f.) of Y

Then the following hold:

(a) {R

: n ≥ 0} is a Markov chain on S =

with the transition

probability matrix p = ( p

i, j

) given by

0, j

= f ( j + 1) for j ≥ 0, p

j, j −1

= 1 for j ≥ 1. (C9.3)

(b) If µ ≡ EY

< ∞, then there exists a unique invariant probability

π ={π

: j ≥ 0} for {R

: n ≥ 0} given by

∞



i=j+1

f (i)/µ ( j = 0, 1, 2,...). (C9.4)

=∞, then ¯π



∞

i=j+1

f (i)(j ≥ 0) provides an invari-

ant measure ¯π ={¯π

: j ≥ 0}for p, which is unique up to a multiplicative

constant.

Proof.

(a) Observe that {N

: n ≥ 0}are {F

: k ≥ 0}– stopping times, where

= σ {Y

:0≤ j ≤ k}. We will ﬁrst show that V

:= S

(n ≥ 0) has

the (inhomogeneous) Markov property. For this note that if S

> n,

then N

n+1

= N

and S

n+1

= S

, and if S

= n, then N

n+1

= N

+ 1

and S

n+1

= S

+ Y

. Hence

n+1

= S

>n}

+ (S

+ Y

= n}

= S

>n}

+ (S

)

= n}

, (C9.5)

where S

is the after-N

process {(S

)

:= S

: k = 0, 1, 2,...}. It

follows from (C9.5) and the strong Markov property that the conditional

distribution of V

n+1

≡ S

n+1

, given the pre-N

sigmaﬁeld G

≡ F

depends only on V

= S

. Since V

is G

-measurable, it follows that

: n ≥ 0} has the Markov property, and that its time-dependent

208 Markov Processes

transition probabilities are

(n, n + j) ≡ P(V

n+1

= n + j | V

= n) = P(Y

= j )

= f ( j), j ≥ 1,

(m, m) = 1 m > n. (C9.6)

Since R

= V

− n(n ≥ 0), {R

: n ≥ 0} has the Markov property, and

its transition probabilities are P(R

n+1

= j | R

= 0) ≡ P(V

n+1

= n +

1 + j | V

= n) = f ( j + 1)( j ≥ 0), P(R

n+1

= j − 1 | R

= j) ≡

P(V

n+1

= n + j | V

= n + j) = 1( j ≥ 1). Thus {R

: n ≥ 0}is a time-

homogeneous Markov process on S =

with transition probabilities

given by (C9.3).

(b) Assume µ ≡ EY

< ∞.Ifπ ={π

: j ≥ 0} is an invariant prob-

ability for p then one must have

∞



j=0

j,0

= π

0,0

+ π

1,0

= π

f (1) + π

∞



j=0

j,i

= π

0,i

+ π

i+1

i+1,i

= π

f (i + 1) + π

i+1

(i ≥ 1). (C9.7)

Thus

− π

i+1

= π

f (i + 1)(i ≥ 0). (C9.8)

Summing (C9.8) over i = 0, 1,..., j − 1, one gets π

− π



i=1

f (i), or π

= π



∞

i=j+1

f (i)(j ≥ 0). Summing over j , one

ﬁnally obtains π

= 1/µ, since



∞

j=0

(1 − F( j)) = µ, with F( j) =



i=0

f (i).

: j ≥ 0} is an invariant measure for p then it satis-

ﬁes (C9.7) and (C9.8) with ¯π

replacing π

(i ≥ 0). Hence, by the com-

putation above, ¯π

= ¯π

(1 − F( j)) ( j ≥ 0). One may choose ¯π

> 0

arbitrarily, for example, ¯π

= 1.

Thus the residual lifetime process {R

: n ≥ 0} is a stationary Markov

process if and only if (i) µ ≡ EY

< ∞ and (ii) the delay distribution is

given by π in (C9.4). This proposition plays a crucial role in providing a

successful coupling for a proof of Feller’s renewal theorem below. Deﬁne

the lattice span d of the p.m.f. f on the set

of positive integers as

the g.c.d. of {j ≥ 1: f ( j) > 0}.

2.13 Complements and Details 209

Theorem C9.1 (Feller’s renewal theorem) Let the common p.m.f. f

of Y

on Z

( j ≥ 1) have span 1 and µ ≡ EY

< ∞. Then whatever

the (delay) distribution of Y

one has for every positive integer m,

lim

n→∞

E(N

n+m

− N

) =

. (C9.9)

Proof. On a common probability space (, F, P), construct two in-

dependent sequences of random variables {Y

, Y

,...} and {

,...} such that (i) Y

(k ≥ 1) are i.i.d. with common p.m.f. f

and the same holds for

(k ≥ 1), (ii) Y

is independent of {Y

: k ≥ 1}

and has an arbitrary delay distribution, while

is independent of

{

: k ≥ 1} and has the equilibrium delay distribution π of (C9.4). Let

: k ≥ 0}, {

: k ≥ 0} be the partial sum processes, and {N

: n ≥ 0},

{

: n ≥ 0} the renewal processes, corresponding to {Y

: k ≥ 0} and

{

: k ≥ 0}, respectively. The residual lifetime processes {R

: = S

−

n: n ≥ 0} and {

: =

− n: n ≥ 0} are independent Markov chains

={0, 1, 2,...} each with transition probabilities given by (C9.3).

Since the span of f is 1, it is simple to check that these are aperiodic and

irreducible. Hence, by Theorem 8.1, the Markov chain {(R

): n ≥ 0}

× Z

is positive recurrent, so that

T := inf{n ≥ 0:(R

) = (0, 0)} < ∞ a.s. (C9.10)

Deﬁne



if T > n,

if T ≤ n.

(C9.11)

Then {R



: n ≥ 0} has the same distribution as {R

: n ≥ 0}. Note also

that

n+m

− N

n+m



j=n+1

=0}

n+m

−

n+m



j=n+1

{

=0}

, (C9.12)

n+m

−

) =

n+m



j=n+1

= 0) = mπ

= m/µ. (C9.13)

Now

E(N

n+m

− N

) = E((N

n+m

− N

{T >n}

) + E((

n+m

−

{T ≤n}

)

= E((N

n+m

− N

{T >n}

) − E((

n+m

−

{T >n}

)

+E(

n+m

−

). (C9.14)

210 Markov Processes

Since the ﬁrst two terms on the right-hand side of the last equal-

ity are each bounded by mP(T > n) → 0asn →∞, the proof is

complete.

Corollary C9.1 If f has a lattice span d > 1 and µ ≡ EY

< ∞ then,

whatever the delay distribution on the lattice {kd: k = 1, 2,...},

lim

n→∞

E(N

nd+md

− N

) =

(m = 1, 2,...). (C9.15)

Proof. Consider the renewal process for the sequence of lifetimes

/d: k = 1, 2,...}, and apply Theorem 13.1, noting that EY

/d =

µ/d.

Deﬁnition C9.2 Suppose that {X

}

∞

n=0

is a Markov process with values in

a measurable state space (S, S) having transition probabilities p(x, dy).

If there is a set A

∈ S, a probability ν on (S, S) with ν(A

) = 1, a

positive integer N , and a positive number λ such that

(i) P(X

∈ A

for some n ≥ 1 | X

= x) = 1 for all x ∈ S,

(ii) (local minorization) p

(N )

(x, A) ≥ λ · ν(A) for all A ∈ S, x ∈ A

then we say {X

}

∞

n=0

is A

-recurrent and locally minorized. Such a set

is called ν(N )-small or, simply, a small set.

We ﬁrst consider the case N = 1. Let

(0)

≡ η

(0)

= 0,η

( j)

≡ η

( j)

= inf

n >η

( j−1)

: X

∈ A

, j = 1, 2,..., (C9.16)

denote the successive times at which the process {X

}

∞

n=0

visits A

We will now show that, in view of the local minorization on A

, cycles

between visits to A

may be deﬁned to occur at times ρ

(1)

, ρ

(2)

,...,called

regeneration times so as to make the cycles between these times i.i.d. As

a result of this regenerative structure, one may then obtain convergence

to the invariant probability by independent coupling.

Proposition C9.2 (Regeneration lemma) Let {X

}

∞

n=0

be a Markov

process on a Polish state space (S, S),whichis A

-recurrent and lo-

cally minorized on A

with N = 1. Then (a){X

}

∞

n=0

has a representa-

tion by i.i.d. random cycles between regeneration times ρ

(1)

,ρ

(2)

,...,

2.13 Complements and Details 211

namely,

:= (X

( j)

,...,X

( j+1)

), j = 0, 1, 2,..., (C9.17)

which are independent for j ≥ 0 and identically distributed for j ≥ 1.

(b) If, in addition, c := sup{E(η

(1)

| X

= x):x ∈ A

} < ∞, then

E(ρ

( j)

− ρ

( j−1)

) ≤ c/λ.

Proof. Assume without loss of generality that 0 <λ<1. One may

express p(x, dy)as

p(x, B) = [λν(B) + (1 − λ)q(x, B)]1

(x) + p(x, B)1

S\A

(x),

(C9.18)

where, for x ∈ A

, q(x, dy) is the probability measure on (S, S)given

q(x, B):= (1 − λ)

−1

[p(x, B) − λν(B)] (x ∈ A

, B ∈ S). (C9.19)

This suggests that if X

= x is in A

then X

n+1

may be constructed

as θ Z + (1 − θ )Y , where θ, Z, Y are independent, with (i) θ Bernoulli

(λ): P(θ = 1) = λ, P(θ = 0) = 1 − λ, (ii) Z has distribution ν on

(S, S) and Y has distribution q(x, dy). If X

= x /∈ A

, then X

n+1

taken to have distribution p(x, dy). We now make this precise.

Let {(X

,θ

, Z

,α

): n = 1, 2,...} be an independent family on

(, F, P): (1) X

has an arbitrary (initial) distribution on (S, S), (2) {θ

n ≥ 0} is an i.i.d. Bernoulli B

(λ) sequence, (3) {Z

: n ≥ 1} is an i.i.d.

sequence with common distribution ν on (S, S), and (4) {α

: n ≥ 1} is

an i.i.d. sequence of random maps on (S, S) such that

P(α

x ∈ B) = q(x, B)1

(x) + p(x, B)1

S\A

(x), (x ∈ S, B ∈ S).

(C9.20)

Note that the right-hand side is a transition probability on (S, S), so that

an i.i.d. sequence {α

: n ≥ 1} satisfying (C9.21) exists (see Chapter 3,

Proposition C1.1 in Complements and Details. Now deﬁne recursively

n+1

= f (X

, Z

n+1

; θ

,α

n+1

)(n ≥ 0), (C9.21)

where

f (x, z; θ,γ) =







z if x ∈ A

, θ = 1,

γ (x)ifx ∈ A

, θ = 0,

γ (x)ifx /∈ A

(C9.22)

212 Markov Processes

Observe that {θ

, Z

n+1

,α

n+1

} is an independent triple, which is in-

dependent of {X

, X

,...,X

} since, by (C9.21), the latter are func-

tions of X

; θ

,θ

,...,θ

n−1

; Z

, Z

,...,Z

; α

,α

,...,α

. Hence the

conditional distribution of X

n+1

,given{X

,...,X

}, is the distribu-

tion of

[θ

n+1

+ (1 −θ

)α

n+1

(x)]1

(x) + a

n+1

(x)1

S\A

(x) (C9.23)

on the set {X

= x}. The distribution of (C9.23) is p(x, dy) in view

of (C9.18). Thus {X

: n ≥ 0} is Markov with transition probability

p(x, dy).

The above argument also shows that {W

:= (X

,θ

): n ≥ 0} is also

a Markov process, as θ

is independent of (X

,θ

),...,(X

n−1

,θ

n−1

)

and X

. Consider the stopping times (for {W

: n ≥ 0}) η

( j)

deﬁned by

(C9.16), and ρ

( j)

deﬁned by

(0)

:= inf{n ≥ 0: X

∈ A

,θ

= 1},

( j)

:= inf{n >ρ

( j−1)

: X

∈ A

, θ

= 1}( j ≥ 1). (C9.24)

To show that ρ

( j)

< ∞ a.s., we will ﬁrst establish that {θ

( j)

: j ≥ 0} is

an i.i.d. B

(λ) sequence. For this deﬁne F

= σ {(X

,θ

),...,(X

,θ

)}

( j ≥ 0) and the pre-η

( j)

sigmaﬁeld F

( j)

= [A ∈ F: A ∩{η

( j)

≤ n}∈F

∀n]. By the strong Markov property, the conditional distribution of

{(X

( j)

,θ

( j)

): m ≥ 0},givenF

( j)

, is the distribution of {(X

,θ

m ≥ 0} under the initial state (x,θ) = (X

( j)

,θ

( j)

). In particular, the

conditional distribution of θ

( j+1)

,givenF

( j)

, is the same as the dis-

tribution of θ

(1)

for the process {(X

,θ

): m ≥ 0} evaluated at the ini-

tial state (x,θ) set at (X

( j)

,θ

( j)

). But whatever the initial state (x,θ),

Prob(θ

(1)

= 1) =



∞

m=1

Prob(η

(1)

= m, θ

= 1) =



∞

m=1

Prob(η

(1)

m)· Prob(θ

= 1) =



∞

m=1

Prob(η

(1)

= m)λ = λ, since θ

is indepen-

dent of G

≡ σ {X

, X

,...,X

} and {η

(1)

= m}∈G

This shows that θ

( j+1)

is independent of F

( j)

and it is B

(λ). It fol-

lows that {θ

( j)

: j ≥ 0} is an i.i.d. B

(λ) sequence. The above argument

actually shows that θ

( j+1)

is independent of F

( j)

and (X

( j+1)

,η

( j+1)

since {X

∈ B,η

( j+1)

= m}∈G

and θ

is independent of G

.Now

the event {ρ

(1)

< ∞} equals the event ∪

∞

j=1

{η

( j)

< ∞, θ

( j)

= 1} whose

probability is the same as that of ∪

∞

j=1

{θ

( j)

= 1} since η

( j)

< ∞ a.s. for

all j , by hypothesis. But the probability of ∪

∞

j=1

{θ

( j)

= 1} is the same

as that of the event {θ

= 1 for some n = 1, 2,...}, where θ

are i.i.d.