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

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

2.8 Recurrence and Steady State Distributions 163

positive recurrent. Then

(N )

(1)



N −1

r=1

(r+1)

− η

(r)

→ E

(2)

− η

(1)

= E

=∞a.s., as N →∞,

by the SLLN for the case of the inﬁnite mean. In particular, with N =

≡ N

( j),

)

( j)

→∞ and

( j)

)

→ 0 a.s., as n →∞.

Since η

)

≤ n, one then has

( j)

→ 0 a.s., as n →∞. (8.12)

But N

( j) =



m=1

=j]

. Hence taking expectation in (8.12) we

obtain



m=1

(m)

→ 0, as n →∞. (8.13)

Since i is arbitrary, (8.13) holds for all i . Multiplying both sides of

(8.13) by π

and summing over i,weget



m=1

(m)

/n → 0asn →∞.

But the left-hand side above equals π

> 0 ∀n, by invariance of

π, leading to a contradiction. Hence j is positive recurrent. Thus

(3) ⇒ (1).

Note that we have incidentally proved that π

is the ratio of the expected

time spent in state j between two successive visits to state i, to the

expected length of time between two successive visits to i .

(0)

= π

. (8.14)

164 Markov Processes

The arguments leading to (8.13) show that (8.13) holds for all null re-

current states i, j . As a corollary to Proposition 8.1 we then get

Corollary 8.1 If an irreducible Markov chain has a null recurrent state

then all states are null recurrent and (8.13) holds for all i, j.

Example 8.1 (Unrestricted birth-and-death chains on

Z) We take the

state space S ={0, ±1, ±2,...}=

Z. For a simple random walk on Z,

if the process is at state x at time n then at time n + 1 with probability

p it is at the state x + 1 and with probability q = 1 − p it is at the state

x − 1. Thus the probabilities of moving one-step forward or one-step

backward do not depend on the current state x. In general, however, one

may construct a Markov chain with transition probabilities

x,x+1

= β

, p

x,x

= α

, p

x,x−1

= δ

0 <β

< 1, 0 <δ

< 1,α

≥ 0,

+ β

+ δ

= 1(x ∈ Z). (8.15)

Such a Markov chain {X

: n = 0, 1,...}is called a birth-and-death chain

on S =

Z. Under the assumption β

> 0, δ

> 0 for all x, this chain is

clearly irreducible. Often one has α

= 0, x ∈ Z, but we well consider

the more general case α

≥ 0. In analogy with the simple random walk

(see Section 2.6), we may calculate the probability ϕ(x) that the birth-

and-death chain will reach d before c, starting at x, c < x < d (c, d ∈

Z).

By the Markov property,

ϕ(x) = P

({X

: n ≥ 0} reaches d before c, X

= x + 1)

+ P

({X

: n ≥ 0} reaches d before c, X

= x)

+ P

({X

: n ≥ 0} reaches d before c, X

= x − 1)

= β

ϕ(x + 1) +α

ϕ(x) + δ

ϕ(x − 1).

Writing α

= 1 − β

− δ

, one obtains the difference equation

(ϕ(x + 1) −ϕ(x)) = δ

(ϕ(x) − ϕ(x − 1)), c < x < d,

ϕ(c) = 0, ϕ(d) = 1. (8.16)

The second line of (8.16) gives the boundary conditions for ϕ. We can

rewrite the ﬁrst line as

ϕ(x + 1) −ϕ(x) =

(ϕ(x) − ϕ(x − 1)), c < x < d. (8.17)

2.8 Recurrence and Steady State Distributions 165

Iterating over x = c + 1,...,y − 1, y, and using ϕ(c) = 0, one

obtains

ϕ(y + 1) −ϕ(y) =

y−1

···δ

c+1

y−1

···β

c+1

ϕ(c + 1), c < y < d. (8.18)

Summing this over y = c + 1, c + 2,...,d − 1, and setting

ϕ(d) = 1,

1 − ϕ(c + 1) =



d−1



y=c+1

y−1

···δ

c+1

y−1

···β

c+1



ϕ(c + 1),

ϕ(c + 1) =

1 +



d−1

y=c+1

y−1

···δ

c+1

y−1

···β

c+1

Applying this to (8.17) and summing over y = x − 1, x − 2,...,

c + 1,

ϕ(x) − ϕ(c + 1) =

x−1



y=c+1

y−1

···δ

c+1

y−1

···β

c+1

ϕ(c + 1),

ϕ(x) =

1 +



x−1

y=c+1

y−1

···δ

c+1

y−1

···β

c+1

1 +



d−1

y=c+1

y−1

···δ

c+1

y−1

···β

c+1

(c < x < d). (8.19)

One may similarly obtain (Exercise) the probability ψ(x) of reaching

c before d, starting at x, c ≤ x ≤ d,as

ψ(x) =



d−1

y=x

y−1

···δ

c+1

y−1

···β

c+1

1 +



d−1

y=c+1

y−1

···δ

c+1

y−1

···β

c+1

, c < x < d,

ψ(c) = 1,ψ(d) = 0. (8.20)

Since ϕ(x) + ψ(x) = 1, starting from x, c < x < d, the chain reaches

the boundary {c, d} (in ﬁnite time) almost surely:P

{c,d}

< ∞) = 1.

Another way of arriving at (8.20) is to show by a direct argument

that P

{c,d}

< ∞) = 1, c < x < d (Exercise), which implies ψ(x) =

1 − ϕ(x).

Exercise 8.4 In Example 8.1, let c < x < d. (a) Prove that P(T

{c,d}

≥

d−c−1 | X

= x) ≤ 1−(δ

c+1

+···+δ

+ β

x+1

+···+β

d−1

) ≤

1 − λ, where λ = min {δ

c+1

+···+δ

+ β

+···+β

d−1

: c + 1 ≤

166 Markov Processes

x ≤ d − 1} > 0. (b) Use (a) to show that P(T

{c,d}

≥ n(d − c − 1) |

= x) ≤ (1 − λ)

∀n = 1, 2,....

Proposition 8.2 The birth-and-death chain is recurrent if



y=−∞

y+1

···β

y+1

···δ

=∞ and

∞



y=0

···δ

···β

=∞, (8.21)

and it is transient if at least one of the two sums above converges.

Proof. By setting d ↑∞in (8.20) one gets ρ

= 1 for c < x if and

only if the limit of ψ(x) in (8.20), as d ↑∞, is 1. The latter holds if and

only if

∞



y=c+1

c+1

c+2

···δ

y−1

c+1

c+2

···β

y−1

=∞. (8.22)

If c + 1 = 0, this is the second condition in (8.21). Suppose c + 1 < 0.

Then ﬁrst subtracting the ﬁnite sum from y = c + 1 through y =−1, and

then dividing the remaining sum by δ

c+1

c+2

···δ

−1

/(β

c+1

c+2

···β

−1

(8.22) is shown to be equivalent to the second condition in (8.21). Simi-

larly, if c + 1 > 0, then by adding a ﬁnite sum and then multiplying by a

ﬁxed factor, (8.22) is shown to be equivalent to the second condition in

(8.21). Thus the second condition in (8.21) is equivalent to ρ

= 1 for

all x, c with c < x.

To show that the ﬁrst condition in (8.21) is equivalent to ρ

= 1 for all

y, d with y < d, one may take the limit of ϕ(x) in (8.19) as c ↓−∞.For

this one may express ϕ(x), on multiplying both the denominator and the

numerator by β

c+1

c+2

···β

/(δ

c+1

c+2

···δ

), in a more convenient

form

ϕ(x) =



x−1

y=c

y+1

y+2

···β

y+1

y+2

···δ



d−1

y=c

y+1

y+2

···β

y+1

y+2

···δ

, c < x < d. (8.23)

Now letting c ↓−∞one obtains ρ

. An argument analogous to that

given for ρ

, c < x, shows that ρ

= 1 for all y < d if and only

if the ﬁrst condition in (8.21) holds. Since ρ

= δ

x,x−1

+ α

x,x+1

, it follows that ρ

≡ (δ

x,x−1

+ β

x,x+1

)/(δ

+ β

) equals

1 if and only if (8.21) holds. An alternative, and simpler, argument may be

2.8 Recurrence and Steady State Distributions 167

based on relabeling the states x →−x, as indicated before the statement

of the proposition (Exercise).

In order to compute the expected time E

of a birth-and-death chain

to return to x, starting from x, or to decide when it is ﬁnite or inﬁnite, con-

sider again integers c < x < d. Let m(x) = E

{c,d}

.Then, again consid-

ering separately the cases X

=+1, 0,−1, we get

m(x) = 1 + β

m(x + 1) + α

m(x) +δ

m(x − 1).

Writing α

= 1 − β

− δ

, one obtains the difference equation

(m(x + 1) − m(x)) +δ

(m(x) −m(x − 1)) =−1,

c < x < d, m(c) = m(d) = 0. (8.24)

The solution to (8.24) is left to Complements and Details. Letting c ↓−∞

or d →∞in m(x), one computes E

= E

(x < d)orE

(c < x). If both are ﬁnite for some x, c with x > c, and some x, d

with x < d, then the chain is positive recurrent, implying, in particular,

that

= 1 + β

y+1

+ α

+ δ

y−1

< ∞

(i.e., E

= (1 − α

)

−1

[1 + β

y+1

+ δ

y−1

] < ∞).

Else, the birth-and-death chain is null recurrent. We will now provide

a different and simple derivation of the criteria for null and positive

recurrence for this chain. For this, write

θ(x) =

···β

x−1

···δ

(x > 0), θ(x) =

x+1

x+2

···δ

x+1

cdotsβ

−1

(x < 0).

(8.25)

Proposition 8.3

(a) A birth-and-death chain on S =

Z is positive recurrent if and

only if

∞



x=1

θ(x) < ∞ and

−1



x=−∞

θ(x) < ∞, (8.26)

and, in this case it has the unique invariant distribution π given by

≡ π({x}) =

θ(x)

1 +



−1

x=−∞

θ(x) +



∞

x=1

θ(x)

, (x ∈

Z). (8.27)

168 Markov Processes

(b) A birth-and-death chain is null recurrent if (8.21) holds and at

least one of the sums in (8.26) diverges.

Proof. To prove (a) we only need to ﬁnd an invariant probability: π;

namely, solve, for x ∈

x,x

+ π

x+1

x+1,x

+ π

x−1

x−1,x

= π

or, π

+ π

x+1

+ π

x−1

= π

or, π

x+1

+ π

x−1

= π

(β

+ δ

). (8.28)

Writing a(x) = π

, b(x) = π

, the last relation may be expressed

as a(x + 1) − a(x) = b(x) −b(x − 1), which on summing over x = y,

y − 1,...,z yields

a(y + 1) −a(z) = b(y) − b(z − 1) (z < y).

Letting z ↓−∞(assuming π

→ 0as|z|→∞), one gets a(y + 1) =

b(y)orπ

y+1

= π

, or

y+1

(y ∈ Z), (8.29)

yielding, for x > 0,

, π

,...,

x−1

···β

···δ

= θ (x)π

(x > 0). (8.30)

Similarly, for x < 0, one gets, using (8.29) in the form π

= (δ

y+1

)π

y+1

, the following:

−1

, π

−2

−1

−2

−1

−2

−1

,...,

x+1

···δ

−1

···β

−2

−1

= θ (x)π

(x < 0). (8.31)

For π to be a probability, one must have





x>0

θ(x) +



x<0

θ(x)



+ π

= 1,

2.8 Recurrence and Steady State Distributions 169

so that



1 +



x=0

θ(x)



−1

, i.e.,



x>0

θ(x) and



x<0

θ(x)

must both converge, which is the condition (8.26). Part (b) follows im-

mediately.

Example 8.2 (Birth-and-death chain on Z

={0, 1, 2,...} with reﬂec-

tion at 0). Here (8.15) holds for x > 0, and one has

= α

, p

= β

(β

> 0,α

≥ 0, α

+ β

= 1). (8.32)

Arguments entirely analogous to those for Example 8.1 lead to the fol-

lowing result.

Proposition 8.4

(a) The birth-and-death chain on

with the reﬂecting boundary

condition (8.32) is recurrent if

∞



y=1

···δ

···β

=∞, (8.33)

and it is transient if the above sum converges.

(b) The chain is positive recurrent if and only if, with θ(x) as in (8.25)

for x > 0,

∞



x=1

θ(x) < ∞. (8.34)

In this case the unique invariant probability π is given by



1 +

∞



x=1

θ(x)



−1

, π

= θ (x)π

(x > 0). (8.35)



x>0

θ(x) =∞.

Exercise 8.5 For Example 8.2, show that (a) ρ

= 1 for 0 ≤ x < d

and (b) ρ

is the same as in Example 8.1, i.e., given by the limit

of ψ(x) in (8.20) as d ↑∞, for 0 ≤ c < x. (Hint: (a) Let A

be the

170 Markov Processes

event that the chain reaches d in rd units of time or less (r ≥ 1).

Then P( A

) = P(A

) P( A

| A

) ···P(A

| A

r−1

) ≤ (1−ϑ )

, where

ϑ: = β

···β

d−1

is less than or equal to the probability that the chain

reaches d in d steps or less, starting at a point y < d.)

Example 8.3 (Ehrenfest model of heat exchange) Physicists P. and

T. Ehrenfest in 1907, and later Smoluchowski in 1916, used the fol-

lowing model of heat exchange between two bodies in order to resolve

an apparent paradox that nearly wrecked Boltzman’s kinetic theory of

matter at the beginning of the twentieth century. In this model, the tem-

peratures are assumed to change in steps of one unit and are represented

by the numbers of balls in two boxes. The boxes are marked I and II,

and there are 2d balls labeled 1, 2,...,2d. We denote by X

the num-

ber of balls in box I at time n (so that the number of balls in box II is

2d − X

). One considers {X

: n ≥ 0} to be a Markov chain on the state

space S ={0, 1,...,2d} with transition probabilities

i,i−1

, p

i,i+1

= 1 −

(i = 1, 2,...,2d − 1);

= 1, p

2d,2d−1

= 1, p

= 0 otherwise. (8.36)

That is, at each time period, one of the boxes gives up a ball to the

other. The probability that box j gives up a ball equals the fraction of the

2d balls it possesses ( j = I, II).

This is a birth-and-death chain with two reﬂecting boundaries 0 and

2d. Note that

: = E

− d) = E

n−1

− d + (X

− X

n−1

)]

= E

n−1

− d) + E

− X

n−1

)

= e

n−1

+ E



2d − X

n−1

−

n−1



= e

n−1

+ E



d − X

n−1



= e

n−1

−

n−1



1 −



n−1

which yields on iteration, noting that e

= i − d,



1 −



(i − d) = (i − d)e

−νt

(8.37)

with n = tτ and ν =−log[(1 − (1/d)]

, τ being the frequency of tran-

sitions per second in the physical model. The relation (8.37) is precisely

Newton’s law of cooling, so the model used is physically reasonable.

2.8 Recurrence and Steady State Distributions 171

One can show as in Example 8.2, but more simply, that the chain has the

invariant distribution π given by





−2d

( j = 0, 1,...,2d), (8.38)

a symmetric binomial distribution Bin(2d, 1/2).

According to thermodynamics, heat exchange is an irreversible pro-

cess and thermodynamic equilibrium is achieved when the temperatures

of the two bodies equal, i.e., when boxes I and II both have (nearly) the

same number of balls. In the random heat exchange model, however, the

process of heat exchange is not irreversible, since the chain is (positive)

recurrent and after reaching j = d, the process will go back to the states

of extreme disequilibrium, namely, 0 and 2d, in ﬁnite time. Historically,

it was Poincar´e who ﬁrst pointed out that statistical mechanical systems

have the recurrence property. Then the scientist Zermelo strongly argued

that such a system is physically invalid since it contradicts the second law

of thermodynamics, which asserts irreversibility. Finally, the Ehrenfests

and Smoluchowski demonstrated what Boltzmann had argued earlier

without providing compelling justiﬁcation: starting from a state far from

equilibrium, the process approaches the equilibrium state j = d fairly

fast, while starting from the equilibrium state j = d to reach 0 or 2d, it

takes an enormously large time even compared to cosmological times.

In other words, after reaching equilibrium the process will not go back

to disequilibrium in physical time. Also, instead of considering the state

j = d as the thermodynamical equilibrium, kinetic theory implies that

π is the state of thermodynamical equilibrium. Because of the enormity

of the number of molecules in a physical system, the temperature of a

body that one would feel or measure is given by the average with respect

to π.

For an indication of the timescales involved, note that (See (8.1),

(7.14), and (8.38)

(d!)

(2d)!

√

πd

1/2

(1 + 0(1)) as d →∞,

= E

= 2

. (8.39)

Also see Complements and Details.

The ﬁnal result of this section strengthens Theorem 8.1.

172 Markov Processes

Theorem 8.2 The n-step transition probability of an irreducible, posi-

tive recurrent, aperiodic Markov chain converges to its unique invariant

distribution π in total variation distance, i.e.,



j∈S

)

(n)

− π

)

→ 0 as n →∞ (∀i ∈ S). (8.40)

We will need a preliminary lemma to prove this theorem.

Lemma 8.1

(a) Let B be a set of positive integers, which is closed under addition.

If the greatest common divisor (g.c.d.) of B is 1, then there exists an

integer n

such that B contains all integers larger than or equal to n

(b) Let j be an (essential) aperiodic state of a Markov chain with

transition probability matrix p. Then there exists n

such that p

(n)

> 0

∀n ≥ n

Proof. (a) Let G be the set of all integers of the form a − b with a, b, ∈

B ∪{0}. It is simple to check that G is the smallest subgroup of

under addition, containing B (Exercise). Suppose the g.c.d. of the inte-

gers in B is 1. Then the smallest positive element of G must be 1 (i.e.,

G =

Z). For if this element is d > 1, then G comprises 0, and all posi-

tive and negative multiples of d; but this would imply that all elements

of B are multiples of d, a contradiction. Thus, either (i) 1 = 1 − 0 ∈ B

or (ii) there exist a, b ∈ B such that a − b = 1. In case (i), one may

take n

= 1. In case (ii), one may take n

= (a + b)

+ 1. For if n ≥ n

then it may be expressed as n = q(a + b) + r, where q and r are the

integers satisfying q

 (a + b), 0 ≤ r < a + b. Thus n = q(a + b) +

r(a − b ) = (q + r)a + (q − r)b ∈ B. (b) Let B ={n ≥ 1: p

(n)

> 0}

and apply (a).

Proof of Theorem 8.2. Consider two independent Markov chains

: n  0} and {X



: n  0} on S having the (same) transition prob-

ability matrix p. Then {(X

, X



): n  0} is a Markov chain on S × S,

having the transition probability (i, i



) → ( j, j



) given by p



((i, i



( j, j



) ∈ S × S). Denote this probability matrix by p

. It is simple to

check that the product probability π × π is invariant under this tran-

sition probability. We will now show that this transition probability p

is irreducible. Fix (i, i



) and ( j, j



) arbitrarily. Because p is irreducible,

there exist positive integers n

and n

such that p

)

> 0 and p

)



> 0.