[PDF] Part IB - Markov Chains (Theorems with proof)

View - Download Part IB - Markov Chains (Theorems with proof)

Previous PDF

Next PDF

Part IB - Markov Chains

Theorems with proof

Based on lectures by G. R. Grimmett

Notes taken by Dexter Chua

Michaelmas 2015

These notes are not endorsed by the lecturers, and I have modiified them (oftensigniificantly) after lectures. They are nowhere near accurate representations of what

was actually lectured, and in particular, all errors are almost surely mine.

Discrete-time chains

Deifinition and basic properties, the transition matrix. Calculation ofn-step transition probabilities. Communicating classes, closed classes, absorption, irreducibility. Calcu- lation of hitting probabilities and mean hitting times; survival probability for birth and death chains. Stopping times and statement of the strong Markov property. [5] Recurrence and transience; equivalence of transience and summability ofn-step transi- tion probabilities; equivalence of recurrence and certainty of return. Recurrence as a class property, relation with closed classes. Simple random walks in dimensions one, two and three. [3] Invariant distributions, statement of existence and uniqueness up to constant multiples. Mean return time, positive recurrence; equivalence of positive recurrence and the existence of an invariant distribution. Convergence to equilibrium for irreducible, positive recurrent, aperiodic chains *and proof by coupling*. Long-run proportion of time spent in a given state. [3] Time reversal, detailed balance, reversibility, random walk on a graph. [1] 1 ContentsIB Markov Chains (Theorems with proof)Contents

0 Introduction 3

1 Markov chains 4

1.1 The Markov property . . . . . . . . . . . . . . . . . . . . . . . . .

4

1.2 Transition probability . . . . . . . . . . . . . . . . . . . . . . . .

5

2 Classiification of chains and states 6

2.1 Communicating classes . . . . . . . . . . . . . . . . . . . . . . . .

6

2.2 Recurrence or transience . . . . . . . . . . . . . . . . . . . . . . .

6

2.3 Hitting probabilities . . . . . . . . . . . . . . . . . . . . . . . . .

11

2.4 The strong Markov property and applications . . . . . . . . . . .

13

2.5 Further classiification of states . . . . . . . . . . . . . . . . . . . .

13

3 Long-run behaviour 15

3.1 Invariant distributions . . . . . . . . . . . . . . . . . . . . . . . .

15

3.2 Convergence to equilibrium . . . . . . . . . . . . . . . . . . . . .

19

4 Time reversal 22

2

0 IntroductionIB Markov Chains (Theorems with proof)0 Introduction

3

1 Markov chainsIB Markov Chains (Theorems with proof)1 Markov chains

1.1 The Markov property

Proposition.

(i)λis adistribution, i.e.λi≥0,P iλi= 1. (ii)Pis astochastic matrix, i.e.pi,j≥0 andP jpi,j= 1 for alli.

Proof.

(i)

Ob vioussince λis a probability distribution.

(ii)pi,j≥0 sincepijis a probability. We also have X jp i,j=X jP(X1=j|X0=i) = 1

sinceP(X1=· |X0=i) is a probability distribution function.Theorem.Letλbe a distribution (onS) andPa stochastic matrix. The

sequenceX= (X0,X1,···) is a Markov chain with initial distributionλand transition matrixPifff P(X0=i0,X1=i1,···,Xn=in) =λi0pi0,i1pi1,i2···pin-1,in(∗) for alln,i0,···,in Proof.LetAkbe the eventXk=ik. Then we can write (∗) as P(A0∩A1∩ ··· ∩An) =λi0pi0,i1pi1,i2···pin-1,in.(∗) We ifirst assume thatXis a Markov chain. We prove (∗) by induction onn. Whenn= 0, (∗) saysP(A0) =λi0. This is true by deifinition ofλ.

Assume that it is true for alln < N. Then

P(A0∩A1∩ ··· ∩AN) =P(A0,···,AN-1)P(A0,···,AN|A0,···,AN-1)

So it is true forNas well. Hence we are done by induction. Conversely, suppose that (∗) holds. Then forn= 0, we haveP(X0=i0) =λi0.

Otherwise,

P(Xn=in|X0=i0,···,Xn-1=in-1) =P(An|A0∩ ··· ∩An-1) P(A0∩ ··· ∩An)P(A0∩ ··· ∩An-1) =pin-1,in, which is independent ofi0,···,in-2. So this is Markov. Theorem(Extended Markov property).LetXbe a Markov chain. Forn≥0, anyHgiven in terms of the past{Xi:i < n}, and anyFgiven in terms of the future{Xi:i > n}, we have

P(F|Xn=i,H) =P(F|Xn=i).

4

1 Markov chainsIB Markov Chains (Theorems with proof)1.2 Transition probability

Theorem(Chapman-Kolmogorov equation).

p i,j(m+n) =X k∈Sp i,k(m)pk,j(n). 5

2 Classiification of chains and statesIB Markov Chains (Theorems with proof)2 Classiification of chains and states

2.1 Communicating classes

Proposition.↔is an equivalence relation.

Proof.

(i)

Relflexiv e:w eha vei↔isincepi,i(0) = 1.

(ii)

Symmetric: trivial b ydeifinition.

(iii)Transitive: supposei→jandj→k. Sincei→j, there is somem >0 such thatpi,j(m)>0. Sincej→k, there is somensuch thatpj,k(n)>0.

Thenpi,k(m+n) =P

rpi,r(m)prk(n)≥pi,j(m)pj,k(n)>0. Soi→k. Similarly, ifj→iandk→j, thenk→i. Soi↔jandj↔kimplies thati↔k.Proposition.A subsetCis closed ifff "i∈C,i→jimpliesj∈C".

Proof.

AssumeCis closed. Leti∈C,i→j. Sincei→j, there is somemsuch thatpi,j(m)>0. Expanding the Chapman-Kolmogorov equation, we have p i,j(m) =X i

1,···,im-1p

i,i1pi1,i2,···,pim-1,j>0. So there is some routei,i1,···,im-1,jsuch thatpi,i1,pi1,i2,···,pim-1,j>0. Sincepi,i1>0, we havei1∈C. Sincepi1,i2>0, we havei2∈C. By induction, we get thatj∈C. To prove the other direction, assume that "i∈C,i→jimpliesj∈C". So for anyi∈C,j̸∈C, theni̸→j. So in particularpi,j= 0.2.2 Recurrence or transience

Theorem.iis recurrent ifffP

npi,i(n) =∞.

Theorem.

P i,j(s) =δi,j+Fi,j(s)Pj,j(s),

Proof.Using the law of total probability

p i,j(n) =nX m=1P i(Xn=j|Tj=m)Pi(Tj=m)

Using the Markov property, we can write this as

nX m=1P(Xn=j|Xm=j)Pi(Tj=m) nX m=1p j,j(n-m)fi,j(m). 6

2 Classiification of chains and statesIB Markov Chains (Theorems with proof)We can multiply through bysnand sum over allnto obtain

X n=1p i,j(n)sn=∞X n=1n X m=1p j,j(n-m)sn-mfi,j(m)sm.The left hand side isalmostthe generating functionPi,j(s), except that we are missing ann= 0 term, which ispi,j(0) =δi,j. The right hand side is the "convolution" of the power seriesPj,j(s) andFi,j(s), which we can write as the productPj,j(s)Fi,j(s). So P i,j(s)-δi,j=Pj,j(s)Fi,j(s). Lemma(Abel's lemma).Letu1,u2,···be real numbers such thatU(s) =P nunsnconverges for 0< s <1. Then lim s→1-U(s) =X nu n.

Theorem.iis recurrent ifffP

npii(n) =∞. Proof.Usingj=iin the above formula, for 0< s <1, we have P i,i(s) =11-Fi,i(s). Here we need to be careful that we are not dividing by 0. This would be a problem ifFii(s) = 1. By deifinition, we have F i,i(s) =∞X n=1f i,i(n)sn.

Also, by deifinition offii, we have

F i,i(1) =X nf So for|s|<1,Fi,i(s)<1. So we are not dividing by zero. Now we use our original equation P i,i(s) =11-Fi,i(s), and take the limit ass→1. By Abel's lemma, we know that the left hand side is lims→1Pi,i(s) =Pi,i(1) =X np i,i(n).

The other side is

lim s→111-Fi,i(s)=11-Pfi,i(n).

Hence we have

X np i,i(n) =11-Pfi,i(n). SincePfi,i(n) is the probability of ever returning, the probability of ever returning is 1 if and only ifP npi,i(n) =∞.7

2 Classiification of chains and statesIB Markov Chains (Theorems with proof)Theorem.LetCbe a communicating class. Then

(i) Either ev erystate in Cis recurrent, or every state is transient. (ii)

If Ccontains a recurrent state, thenCis closed.

Proof.

(i)Leti↔jandi̸=j. Then by deifinition of communicating, there is some msuch thatpi,j(m) =α >0, and somensuch thatpj,i(n) =β >0. So for eachk, we have p i,i(m+k+n)≥pi,j(m)pj,j(k)pj,i(n) =αβpj,j(k).

So ifP

kpj,j(k) =∞, thenP rpi,i(r) =∞. Sojrecurrent impliesi recurrent. Similarly,irecurrent impliesjrecurrent. (ii) IfCis not closed, then there is a non-zero probability that we leave the class and never get back. So the states are not recurrent.Theorem.In a ifinite state space, (i)

There exists at least on erecurren tstate.

(ii) If the c hainis irreducible, ev erystate is recurren t.

Proof.

(ii) follows immediately from (i) since if a chain is irreducible, either all states are transient or all states are recurrent. So we just have to prove (i).

We ifirst ifix an arbitraryi. Recall that

P i,j(s) =δi,j+Pj,j(s)Fi,j(s).

Ifjis transient, thenP

npj,j(n) =Pj,j(1)<∞. Also,Fi,j(1) is the probability of ever reachingjfromi, and is hence ifinite as well. So we havePi,j(1)<∞.

By Abel's lemma,Pi,j(1) is given by

P i,j(1) =X np i,j(n). Since this is ifinite, we must havepi,j(n)→0.

Since we know thatX

j∈Sp i,j(n) = 1, if every state is transient, then since the sum is ifinite, we knowPpi,j(n)→0 asn→ ∞. This is a contradiction. So we must have a recurrent state. Theorem(P´olya's theorem).ConsiderZd={(x1,x2,···,xd) :xi∈Z}. This generates a graph withxadjacent toyif|x-y|= 1, where| · |is the Euclidean norm. 8

2 Classiification of chains and statesIB Markov Chains (Theorems with proof)d= 1d= 2Consider a random walk inZd. At each step, it moves to a neighbour, each

chosen with equal probability, i.e.

P(Xn+1=j|Xn=i) =(

12d|j-i|= 1

0 otherwise

This is an irreducible chain, since it is possible to get from one point to any other point. So the points are either all recurrent or all transient.

The theorem says this is recurrent ifffd= 1 or 2.

Proof.

We will start with the cased= 1. We want to show thatPp0,0(n) =∞. Then we know the origin is recurrent. However, we can simplify this a bit. It is impossible to get back to the origin in an odd number of steps. So we can instead considerPp0,0(2n). However, we can write down this expression immediately. To return to the origin after 2nsteps, we need to have madensteps to the left, andnsteps to the right, in any order. So we have p

0,0(2n) =P(nsteps left,nsteps right) =2n

n 12 2n To show if this converges, it is not helpful to work with these binomial coeiÌifiÌicients n. If we plug this in, we get p This tends to 0, but really slowly, and even more slowly than the harmonic series.

So we havePp0,0(2n) =∞.

In thed= 2 case, suppose after 2nsteps, I have takenrsteps right,ℓsteps left,usteps up anddsteps down. We must haver+ℓ+u+d= 2n, and we need 9

2 Classiification of chains and statesIB Markov Chains (Theorems with proof)r=ℓ,u=dto return the origin. So we letr=ℓ=m,u=d=n-m. So we get

p0,0(2n) =14 2nnX m=0 2n m,m,n-m,n-m 14 2nnX m=0(2n)!(m!)2((n-m)!)2 14 2n2n n nX m=0 n!m!(n-m)! 2 14 2n2n n nX m=0 n m n n-m We now use a well-known identity (proved in IA Numbers and Sets) to obtain 14 2n2n n 2n n 2n n 12 2n#2

1πn

So the sum diverges. So this is recurrent. Note that the two-dimensional probability turns out to be the square of the one-dimensional probability. This is not a coincidence, and we will explain this after the proof. However, this does not extend to higher dimensions.

In thed= 3 case, we have

p

0,0(2n) =16

2nX i+j+k=n(2n)!(i!j!k!)2. This time, there is no neat combinatorial formula. Since we want to show this is summable, we can try to bound this from above. We have p

0,0(2n) =16

2n2n n

Xn!i!j!k!

2 12 2n2n n Xn!3 ni!j!k! 2 Why do we write it like this? We are going to use the identityX i+j+k=nn!3 ni!j!k!=

1. Where does this come from? Suppose we have three urns, and thrownballs

into it. Then the probability of gettingiballs in the ifirst,jin the second andk in the third is exactlyn!3 ni!j!k!. Summing over all possible combinations ofi,j andkgives the total probability of getting in any conifiguration, which is 1. So we can bound this by 12 2n2n n maxn!3 ni!j!k! Xn!3 ni!j!k! =12 2n2n n maxn!3 ni!j!k! 10

2 Classiification of chains and statesIB Markov Chains (Theorems with proof)To ifind the maximum, we can replace the factorial by the gamma function and

use Lagrange multipliers. However, we would just argue that the maximum can be achieved wheni,jandkare as close to each other as possible. So we get 12 2n2n n n!3 n

1⌊n/3⌋!

3 for some constantCusing Stirling's formula. SoPp0,0(2n)<∞and the chain is transient. We can prove similarly for higher dimensions.2.3 Hitting probabilities

Theorem.The vector (hAi:i∈S) satisifies

h Ai=(

1i∈AP

j∈Spi,jhAji̸∈A, and isminimalin that for any non-negative solution (xi:i∈S) to these Proof.By deifinition,hAi= 1 ifi∈A. Otherwise, we have h

Ai=Pi(HA<∞) =X

j∈SP i(HA<∞ |X1=j)pi,j=X j∈Sh

Ajpi,j.

SohAiis indeed a solution to the equations.

To show thathAiis the minimal solution, supposex= (xi:i∈S) is a non-negative solution, i.e. x i=(

1i∈AP

j∈Spi,jxjA i̸∈A, Ifi∈A, we havehAi=xi= 1. Otherwise, we can write x i=X jp i,jxj X j∈Ap i,jxj+X j̸∈Ap i,jxj X j∈Ap i,j+X j̸∈Ap i,jxj X j∈Ap i,j =Pi(HA= 1). 11

2 Classiification of chains and statesIB Markov Chains (Theorems with proof)By iterating this process, we can write

x i=X j∈Apquotesdbs_dbs19.pdfusesText_25

[PDF] show that x is a random variable

[PDF] show that [0

[PDF] show the mechanism of acid hydrolysis of ester

[PDF] show ? n 2 1 n log np converges if and only if p > 1

[PDF] shredded workout plan pdf

[PDF] shredding diet

[PDF] shredding workout plan

[PDF] shrm furlough

[PDF] shuttle paris

[PDF] si clauses french examples

[PDF] si clauses french exercises

[PDF] si clauses french practice

[PDF] si clauses french practice pdf

[PDF] si present

[PDF] siao 93