# 18.445 Introduction To Stochastic Processes

1y ago
23 Views
235.52 KB
12 Pages
Last View : 8m ago
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

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:

Jul 09, 2010 · Stochastic Calculus of Heston’s Stochastic–Volatility Model Floyd B. Hanson Abstract—The Heston (1993) stochastic–volatility model is a square–root diffusion model for the stochastic–variance. It gives rise to a singular diffusion for the distribution according to Fell

are times when the fast stochastic lines either cross above 80 or below 20, while the slow stochastic lines do not. By slowing the lines, the slow stochastic generates fewer trading signals. INTERPRETATION You can see in the figures that the stochastic oscillator fluctuates between zero and 100. A stochastic value of 50 indicates that the closing

440.42500 445.42500 W7PP PHX METRO SUN CITY DMR 110.9 Dick Hale 440.45000 445.45000 W7JSW PHX METRO SCOTTSDALE O,PL 100.0 W7JSW 440.45000 445.45000 K7QDX C AZ PRESCOTT VALLEY O,PL 103.5 Mike Steiner 440.47500 445.47500 KG7IQW PHX METRO PEORIA O,PL,L, All Star 100.0 Travis Labrador 440.47500 445.47500 K7DAD PHX METRO TEMPE O,PL 88.5 Steven L. Petrie

SERVICE Spare parts Ersatzteile Pièces détachées Reserve onderdelen Repuestos Reservdelar IPL, 445, 450, 445 e, 450 e, 2009-02 445, 450 445e, 450e

sion analysis on discrete-time stochastic processes. We now turn our focus to the study of continuous-time stochastic pro-cesses. In most cases, it is di cult to exactly describe the probability dis-tribution for continuous-time stochastic processes. This was also di cult for discrete time stochastic processes, but for them, we described the .

(e.g. bu er stocks, schedule slack). This approach has been criticized for its use of a deterministic approximation of a stochastic problem, which is the major motivation for stochastic programming. This dissertation recasts this debate by identifying both deterministic and stochastic approaches as policies for solving a stochastic base model,

Stochastic Programming Stochastic Dynamic Programming Conclusion : which approach should I use ? Objective and constraints Evaluating a solution Presentation Outline 1 Dealing with Uncertainty Objective and constraints Evaluating a solution 2 Stochastic Programming Stochastic Programming Approach Information Framework Toward multistage program

Anatomi Tulang dan Fisiologi Panggul 2.1.1 Tulang Tulang pelvis merupakan komposisi dari tiga buah tulang yakni dua tulang kokse . tulang pria lebih kekar dan kuat, sedangkan kerangka perempuan lebih ditujukan kepada pemenuhan fungsi reproduksi. Pada wanita bentuk thorak bagian bawah lebih besar, panggul berbentuk ginekoid dengan ala iliaka lebih lebar dan cekung, promontorium kurang .