1y ago

23 Views

2 Downloads

235.52 KB

12 Pages

Transcription

18.445 Introduction to Stochastic ProcessesLecture 3: Markov chains: time-reversalHao WuMIT18 February 2015Hao Wu (MIT)18.44518 February 20151 / 11

RecallConsider a Markov chain with state space Ω and transition matrix P :P[Xn 1 y Xn x] P(x, y ).A probability measure π is stationary if π πP.If P is irreducible, there exists a unique stationary distribution.Today’s goalErgodic TheoremTime-reversal of Markov chainBirth-and-Death chainsTotal variation distanceHao Wu (MIT)18.44518 February 20152 / 11

Ergodic TheoremTheoremLet f be a real-valued function defined on Ω. If (Xn )n is an irreducibleMarkov chain with stationary distribution π, then for any startingdistribution µ, we haven1Xlimf (Xj ) πf ,n nPµ a.s.j 0In particular,n1X1[Xj x] π(x),n nlimPµ a.s.j 0Hao Wu (MIT)18.44518 February 20153 / 11

Detailed balance equationsDefinitionSuppose that a probability measrue π on Ω satisfiesπ(x)P(x, y ) π(y )P(y , x), x, y Ω.These are called detailed balance equations.LemmaAny distribution π satisfying the detailed balance equations isstationary for P.DefinitionA chain satisfying detailed balance equations is called reversible.Hao Wu (MIT)18.44518 February 20154 / 11

Simple random walk on graphExample Consider simple random walk on graph G (V , E) (which isconnected). The measureπ(x) deg(x),2 E x Ωsatisﬁes detailed balance equations ; therefore the simple random walkon G is reversible.Hao Wu (MIT)18.44518 February 20155 / 11

Time-reversal of Markov chainTheoremLet (Xn ) be an irreducible Markov chain with transition matrix P andb to bestationary distribution π. Define Pπ(y )P(y , x)b.P(x,y) π(x)b is stochasticPbn ) be a Markov chain with transition matrix P.b Then π is alsoLet (Xbstationary for P.For any x0 , ., xn Ω, we haveb0 xn , ., Xbn x0 ].Pπ [X0 x0 , ., Xn xn ] Pπ [Xb the time-reversal of X .We call Xb PRemark If a chain with transition matrix P is reversible, then Pband X has the same law as X .Hao Wu (MIT)18.44518 February 20156 / 11

Birth-and-Death chainsA birth-and-death chain has state space Ω {0, 1, ., N}.The current state can be though of as the size of some population ; in asingle step of the chain there can be at most one birth or death. Thetransition probabilities can be specified by {(pk , rk , qk )Nk 0 } wherepk rk qk 1 for each k andpk is the probability of moving from k to k 1 when 0 k N ;pN 0qk is the probability of moving from k to k 1 when 0 k N ;q0 0rk is the probability of remaining at k when 0 k N.TheoremEvery birth-and-death chain is reversible.Hao Wu (MIT)18.44518 February 20157 / 11

Total variation distanceDefinitionThe total variation distance between two probability measures µ and νon Ω is defined by µ ν TV max µ(A) ν(A) .A ΩLemmaThe total variation distance satisfies triangle inequality : µ ν TV µ η TV η ν TV .Hao Wu (MIT)18.44518 February 20158 / 11

Three ways to characterize the total variation distanceLemma µ ν TV 1X µ(x) ν(x) .2x ΩLemma µ ν TV Hao Wu (MIT)1sup{µf νf : f satisfying max f (x) 1}.x Ω218.44518 February 20159 / 11

Three ways to characterize the total variation distanceDefinitionA coupling of two probability measures µ and ν is a pair of randomvariables (X , Y ) defined on the same probability space such that themarginal law of X is µ and the marginal law of Y is ν.Lemma µ ν TV inf{P[X 6 Y ] : (X , Y ) is a coupling of µ, ν}.DefinitionWe call (X , Y ) the optimal coupling if P[X 6 Y ] µ ν TV .Hao Wu (MIT)18.44518 February 201510 / 11

Homework 1 due Feb. 23rdHao Wu (MIT)18.44518 February 201511 / 11

MIT OpenCourseWarehttp://ocw.mit.edu18.445 Introduction to Stochastic ProcessesSpring 2015For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.

18.445 Introduction to Stochastic Processes Lecture 3: Markov chains: time-reversal Hao Wu MIT 18 February 2015. Hao Wu (MIT) 18.445. 18 February 2015 1 / 11

Related Documents: