### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Stochastic Processes STAT 150

GPA 3.64

### View Full Document

## 50

## 0

## Popular in Course

## Popular in Statistics

This 58 page Class Notes was uploaded by Floy Kub on Thursday October 22, 2015. The Class Notes belongs to STAT 150 at University of California - Berkeley taught by S. Evans in Fall. Since its upload, it has received 50 views. For similar materials see /class/226723/stat-150-university-of-california-berkeley in Statistics at University of California - Berkeley.

## Reviews for Stochastic Processes

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/22/15

Statistics 150 Spring 2007 April 24 2007 01 1 Introduction Definition 11 A sequence Y Ynz n 2 O is a martingale with respect to the sequence X an n 2 0 if for all n 2 O 1 Elm lt oo 2 EYn1lX0X1Xn Y Example 12 Simple random walk Let X7 be iid random variables such that X7 1 with probability p and X7 1 with probability q 1 p Then S X1 X2 Xn satisfies ElSnl g n and ESn1lX17X27 39 39 39 7X71 Sn l q and Yn Sn np q defines a martingale with respect to X Example 13 De Moivre s martingale A simple random walk on the set 012 N stops when it first hits either of the absorbing barriers at 0 and at N what is the probability that it stops at the barrier 0 Write X1X2 for the steps of the walk and Sn for the position after n steps where SO k3 Define Yn qpSn where PZMXz39 1pq1 and Oltplt 1 We claim that EYn1lX1X2Xn Yn for all 72 If Sn equals 0 or N then the process has stopped by time n and Sn Sn and therefore YnH Yn If 0 lt Sn lt N then EYn1lX1X2 Xn E qp5ntXn1lX1X2 Xn qpSquotlpqp QQP1l Yn By taking expectations we see that EYn1 EEOn for all n and hence EYn EY0 qpk for all n Let T be the number of steps before the absorption of the particle at either 0 or N then EYT qpk Expanding EYT we have that EYT amom QPN1 Pk where pk Pabsorbed at 0 30 Therefore p pN Pk W WherePZQP Example 14 Markov chains Let X be a discretetime Markov chain taking values in the countable state space S with transition matrix P Suppose that o S gt R is bounded and harmonic which is to say that szj j for all 239 E S jES It is easily seen that Y Xn n 2 0 is a martingale with respect to X E Xn1lX1X2Xn E Xn1an prnj ltjgt xn jes Definition 15 Given a random variable Z we use the shorthand ElZlJquotnl for ElZlX0X1 We call 7 730731 a filtration A sequence of random variables Y Ynz n 2 0 is said to be adapted to the filtration 7 if Yn is Jibmeasurable for all n that is if Yn is a function of X0X1 Xn Definition 16 Let 7 be a filtration of the probability space SJUP and let Y be a sequence of random variables which is adapted to 7 We can rewrite our previous definition of a martingale by saying that the pair K men n 2 0 a martingale if for all n gt 0 1 Elm lt oo 2 EYn1lfn Yn Definition 17 Let 7 be a filtration of the probability space SJUP and let Y be a sequence of random variables which is adapted to 7quot We call the pair K a submartingae if for all n 2 0 1 mm lt oo 2 EYn1l7n Z Yn or a supermartingae if for all n 2 O 3 Ell7 lt oo 4 EYn1l7n S Yn We call the pair 3 predictable if Sn is fn1measurabe for all n 2 1 We call a predictable process 5 increasing if SO 0 and 1PSn g Sn11for all n Proposition 18 Doob decomposition A submartingae Y7quot with finite means may be expressed in the form where M 7 is a martingale and S 7 is an increasing predictable process This decomposition is unique The process 3 is called the compensator of the submartingale Y7quot Note that compensators have finite mean since 0 3 Sn 3 Hi Mn implying that ElSnl 3 mini Eanl 10 Proof We define M and S explicitly as follows M0 Y0 SO 0 Mn1Mn n1EYn1ifn7 Sn1Sn n I 11 2 Exercises 1 Let X1X2 be random variables such that the partial sums Sn X1 X2 Xn determine a martingale Show that EX7Xj 0 if 239 7E j 2 Let XOX1X2 be a sequence of random variables with finite means and satisfying Ean1lXOX1 Xn aXn bXn1 for n 2 1 where 0 lt ab lt 1 and a l b 1 Find a value of oz for which Sn ozXn Xn1 n 2 1 defines a martingale with respect to the sequence X 12 3 If X is a martingale show that ECn EY0 for all n ii If Y7quot is a submartingale respectively supermatingale with finite means show that EYn Z EY0 respectively EYn g EY0 4 Let K be a martingale Show that EYnml7n Yn for all mm 2 0 13 5 Let Sn n 2 0 be a simple symmetric random walk on the integers with S0 k3 Show that Si n is a martingale Arguing as we did for the probability of ruin find the expected duration of the game for the gambler s ruin problem 6 Let X be a discretetime Markov chain with countable state space S and transition matrix P Suppose that w S gt R is bounded and satisfies Ejespijw j 3 MHz for some gt 0 and all 239 E S Show that A WMXn constitutes a supermartingale 14 Proposition 29 Hoeffding s inequality Let K be a martingale and suppose that there exists a sequence K 1 K 2 of real numbers such that P Yn Yn1 g Kn 1 for a n Then 1 2 51 7L1 7L 15 Proof Observe that for w gt 0 the function gd 6 is convex and 1 6 S 1 de 51de if idi g 1 DIi t Applying this to a random variable D having mean 0 and satisfying PiDi g 1 1 we obtain 2 E D lt 6 1 l 6 lt 6 1 2 by a comparison of the coefficients of 2 for n 2 0 Using Markov39s inequality we have MY Y0 Z x g 6 6xE 6YquotYO for 6 gt 0 16 Writing Dn Yn Yn1 and conditioning on fn1 we obtain E 6Yn Y0 fn1 66Yn1 Y0E 6Dn fn1 1 lt 6Yn1 Y0 62K2 e 6Xp2 n We take expectations and iterate to find 1 1 6Yn Y 6Yn Y 2 2 2 2 Ee 0 Ee 1 0exp26 Knltexplt26 and therefore 1 TL MY Y0 Z x g exp 616 562 for all 6 gt 0 21 17 Suppose that x gt 0 and set 6 this is the value which T K3 minimizes the exponent we obtain 1x2 2 W Y0 Z x 3 exp ml The same argument is valid with Yn Y0 replaced by Y0 Yn and the claim of the theorem follows by adding the two identical bounds together El 18 Example 210 Large deviations Let X1X2 be independent random variables Xi having the Bernoulli distribution with parameter p We set Sanl 1 i Xn and YnSn npto obtain a martingale Y It is a consequence of Hoedeing39s inequality that 1 P Sn npl Z g 2eXp x2u2 for x gt 0 where u maxp 1 p 19 3 Crossing and convergence Proposition 31 Martingale convergence theorem Let K be a submartingale and suppose that EYn g M for some M and all n There exists a random variable YOO such that Yn amp YOO as n gt oo 20 a real ab by the subsequence y0y1 yn and let Uab y limngt00 Unaby be Suppose that y ynz n 2 0 is a real sequence and ab interval Let Unab y be the number of upcrossings of the total number of such upcrossings by y Lemma 32 fUa b y lt 00 for a rationals a and b satisfying a lt b then limnsoo yn exists but may be infinite 21 Suppose now that K is a submartingale and let Unab Y be the number of upcrossing of a b by Y up to time n 22 Proposition 33 Upcrossing inequality lfa lt b then E Yn b a Proof Set Zn Yn a so that Una I Y Un0 b a Z Let T2k1T2k k 2 1 be the upcrossing by Z of 019 a and define the indicator function I 1 ifz39 E T2k1T2k for some k 0 otherwise Note that L is f 1measurabe Now I CLUnO b CL g 7L1 23 H oweve r E Zz39 Zi l i EKZvL Zi l z39 fi lD MWsz 73 1 Zi lD Wzv fi 1 Zi l E E E EZ 1 II and so b a Un07 b a S S 24 Proof ofproposition 31 Suppose Y7quot is a submartingale and EYn g M for all n From the upcrossing inequality we have that if a lt b EYn lal b a so that Ua I Y limngt00 Una I Y satisfies EUnm 9 Y 3 M lal b a for all a lt 9 Therefore Uab Y lt 00 as for all a lt I Since there are only countany many rationals it follows that with probability 1 Ua I Y lt 00 for all rational a and I And the sequence Yn converges almost surely to some limit YOO which could be infinite EUab Y 11m EUnab Y 3 25 We omit the proof that YOO is actually finite with probability one 26 Corollary 34 If Y 7quot is either a nonnegative supermartingae or a nonpositive submartingae then YOO limngt00 Yn exists almost surely 27 Example 35 Random walk Consider De Moivre39s martingale namely Y qpSquot where Sn is the position after n steps of the usual simple random walk The sequence Yn is a nonnegative martingale and hence converges almost surely to some finite limit Y as n gt 00 This is not of much interest ifp q since Yn 1 for all n in this case Suppose that 19 7E q The random variable Yn takes values in the set pk k 0i1 where p qp Certainly Yn cannot converge to any given possibly random member of this set since this would necessarily entail that Sn converges to a finite limit which is obviously false Therefore Yn converges to a limit point of the set not lying within the set The only such limit point which is finite is 0 and therefore Yn gt 0 as Hence Sn gt 00 as ifp lt q and Sn gt 00 as ifp gt q Note that Yn does not converge in mean since EYn EY0 7E 0 for all n 28 Lemma 36 Let K be a martingale Then Yn converges in mean if and only if there exists a random variable Z with finite mean such that Yn EZ i f lfYn L YOO then Yn lam00 i f Remark That is YOO is a possible choice of Z and the unique one that is foomeasurable 29 4 Stopping times Definition 41 A random variable T taking values in 0 1 2 U 00 is called a stopping time with respect to the filtration 7quot if the indicator of the event T n is Jibmeasurable for all n 2 0 Note that the indicator of the event TgtnT nc is fnmeasurable for all n We write ElZlJquotTl for ElZlX0X1XT 30 Example 42 First passage times For each sufficiently nice subset B of R define the first passage time of X to B by T3 minn Xn E B with TB 00 if Xn g B for all n It is easily seen that TB is a stopping time 31 Proposition 43 Let K be a submartingae and let T be a stopping time with respect to 7 Then Z 7 defined by Zn YTM is a submartingae Proof We may write n l Zn 2 2 mm YanZn t0 whence Zn is fnmeasurable and Wt EEOJ lt oo 0 Also Zn Zn YnH Yn1Tgtn whence EZn1 Zn EYn1 Yn fn1Tgtn Z Let X7quot and K be two martingales with respect to the filtration 7quot Let T be a stopping time with respect to 7quot T is the switching time from X to Y Proposition 44 Optional switching Suppose that XT YT on the event T lt oo Then Xn ifnltT Yn ifnZT Zn defines a martingale with respect to 7quot 33 Proof Note that Zn Xn1nltT YnanT is Jibmeasurable Also EiZni g Eani EiYni lt 00 By the martingale property of X and Y Zn EXn1 i fn1nltT EYn1 i fn1n2T IEXn11nltT Yn11n2T i 771 Now Xn11nltT Yn11nZT Zn1 Xn11n1T Yn11n1T Zn1 XT YT1n1T By the assumption that XT YT on the event T lt 00 we have that Zn EZn1 i 73 so that Z is a martingale El 34 Proposition 45 Optional sampling theorem Let K be a submartingae 1 If T is a stopping time and there exists a deterministic N lt 00 such that MT 3 N 1 then MY lt 00 and EYT f0 2 Y0 2 If T1 g T2 g is a sequence of stopping times such that PTj g Nj 1 for some deterministic rea sequence Nj then ZH defined by ZQH0 Y00 ZjHj YTj7Tj is a submartingae Proof Part b follows from part 3 Suppose MT 3 N 1 Let Zn YTML so that Z is a submartingale Therefore lt 00 and EZN i 70 Z Z0 Y0 and the proof is finished by observing that ZN YTAN YT as El 35 Proposition 46 Let K be a martingale For x gt 0 E0 F max Ym Z x g O m n IE E YnD and P max YM 216 3 Oltmltn 36 Proof Let x gt 0 and T minm Ym Z x be the first passage time of Y above the level 16 Then T n is a bounded stopping time and EY0 EYTAn Now EltYTAn EYT1TSn i Yn1Tgtn However EltYT1TSn Z E1T n g n since YT Z x and therefore EYn EYTML Z xIPT S n EYn1Tgtn whence xIPT g n g lax711 g EYn Note also that Y7quot is a martingale so that E Y P max Ym Z x g M from x gt 0 O m n IE 37 5 Optional stopping Proposition 51 Let K be a martingale and let T be a stopping time Then EYT EY0 if 1 IPT lt 00 1 2 EHTi lt 00 and 3 EYn1Tgtn gt 0 as n gt oo 38 Proof Note that YT YTML YT Yn1Tgtn Taking expectations and using the fact that EYTML EY0 we find that i EYT1TgtTL Now 00 tanT15 Z EYT1Tk kn1 is the tail of the convergent series EYT 2k EYT1Tk therefore EYT1Tgtn H 0 as n H 00 El 39 Example 52 Markov chains Let X be an irreducible persistent Markov chain with countable state space S and transition matrix P and let d S gt R be a bounded function satisfying Zpiszj for all 239 E S jES Then zMXn constitutes a martingale Let T7 be the first passage time of X to the state 239 that is Ti minn Xn The sequence Xn is bounded and we obtain E XTZ E X0 whence E X0 for all states 239 Therefore w is a constant function 4o Proposition 53 Let K be a martingale and let T be a stopping time Then EYT EY0 if the following hold 1 PTltoo 1 ETltoo and 2 there exists a constant C such that E lln1 Ynl fn g C for all n lt T 41 Example 54 Wald s equation Let X1X2 be independent identically distributed random variables with finite mean u and let Sn 271 Xi Then Yn Sn ml is a martingale with respect to the filtration 7 where fn 0Y1 Y2 Yn Now ElYn1 Ynl l R Ean1 Ml IE4lX1 Ml lt 00 Thus EYT EY0 0 for any stopping time T with finite mean implying that EST HElTl 42 Example 55 Wald s identity Let X1X2 be independent identically distributed random variables with common moment generating function Mt EetX suppose that there exists at least one value of 757 0 such that 1 g Mt lt oo and fix t accordingly Let Sn 231 Xi Define Y01 Yn n for 7221 It is clear the K is a martingale Let T be a stopping time with finite mean and note that etX E Yn Yn n YnE 1 l 1 ll W i Yn M t 21 l IE etX Mt 43 Suppose that T is such that iSni 30 for nltT 51 where C is a constant Now Mt Z 1 and etSn emo Yn lt lt W7 f ltT MW MW e or In summary ifT is a stopping time with finite mean such that 51 holds then EetSMtT 1 whenever Mt Z 1 44 Example 56 Simple random walk Suppose that Sn is a simple random walk whose steps take the values 1 and 1 with respective probabilities p and q 1 19 For positive integers a and b we have from Wald39s identity that e atE MtT15Ta 6th Mt T1STb 1 if Mt 2 1 52 where T is the first exit time of a b as before and Mt pet l qe Setting Mt 8 1 we get 6t 18 or 6t 28 where 1 1 x1 4pq82 A 8 1 x1 4pq82 7 2 A1 8 2198 2198 45 Substituting these into equation 52 we obtain two linear equations in the quantities 1313 2 E8T1STQ 1323 2 E3T15Tb 53 with solutions AWN AS AW P181f a 28 1b A2b 1b A2b which we add to obtain the probability generating function of T EST 2 1313 P28 0 lt s g 1 46 Suppose we let a gt oo so that T becomes the time until the first passage to the point I From 53 P18 gt 0 as a gt oo if 0 lt 8 lt1 and P28 gt Fbs where b Fb8lt114pq82gt 2q8 Notice that Fb1 min1pqb 47 6 Exercises 1 If T1 and T2 are stopping times with respect to a filtration 7quot show that T1 T2 maXT1T2 and minT1T2 are stopping times also 2 Let X1X2 be a sequence of nonnegative independent random variables and let Nt maxn X1 X2 Xn g t Show that Nt 1 is a stopping time with respect to a suitable filtration to be specified 48 3 Let K be a submartingale and let S and T be stopping times satisfying 0 g S g T g N for some deterministic N Show that Em ms Em IanN 4 Let Sn be a simple random walk with SO 0 such that 0 lt p M51 1 lt Use de Moivre s martingale to show that IEsupm Sm 49 5 Let Sn n 2 0 be a simple symmetric random walk with SD 0 Show that cosSn ab a cos A n constitutes a martingale if cos 7E 0 6 Let Sn a 2771 XT be a simple symmetric random walk The walk stops at the earliest time T when it reaches either of the two positions 0 or K where 0 lt a lt K Show that Mn 2770 ST S L is a martingale and deduce that EZO ST K2 a2a a 50 7 The maximal inequality Let39s denote Y maXY7 0 g 239 g Proposition 71 Maximal inequality 1 fY7quot is a submartingae then HEYJr 39I L for xgt0 2 If Y 7 is a supermartingae and E Yoi lt oo then Py 2x E W 39I L for x gt 0 51 Proof Let T minn Yn Z x where x gt 0 Suppose first that K is a submartingale Then Y f is a nonnegative submartingale with finite means and T minn YTL Z Applying the optional sampling theorem with stopping times T1 T n T2 n we obtain EY1LAn g EYn However EYTLn WYFlTsn EYn1TSn Z g n i EltYn1T n whence xPT n EYn1 1Tgtn 52 Suppose next that K is a supermartingale By optional sampling EY0 Z EYTn Now EYTML EYT1Tgn Yn1Tgtn 2 xIPT g n EY 39I L whence xPT g n g EY0 EYn 53 Example 72 DoobKolmogorov inequality Let K be a martingale such that lt 00 for all n Then Hajlb is a submartingale whence EY2 39I L PltmaxYk2xPmaXYk2Zx2 2 031677 03kgn IE form gt 0 54 Example 73 Gambling systems For a given game write Y0 Y1 for the sequence of capitals obtained by wagering one unit on each play that is Y0 is the initial capital and Yn is the capital obtained after n gambles each involving a unit stake A general betting strategy would allow the gambles to vary her stake If she bets Sn on the nth play her profit is SnYn Yn1 since Yn Yn1 is the profit resulting from a stake of one unit Hence the gambler39s capital Zn after n plays satisfies Zn n1 Snon YH Y0 ZSZYi YH z 1 Notice that 3 must be a predictable process The sequence Z is called the transform of Y by S If Y is a martingale we call Z a martingale transform 55 Proposition 74 Let 3 be a predictable process and let Z be the transform of Y by S Then 1 if K is a martingale then Z 7 is a martingale as long as Elan lt 00 for all n 2 if Y 7 is a submartingale and in addition Sn 2 0 for all n then Z 7 is a submartingale as long as IEer lt 00 for all n Proof EZn1 fn Zn ESn1Yn1 Yn fn n1EYn1 fn Y b 56 A number of special cases are of value 1 Optional skipping At each play the gambler either wagers a unit stake or skips the round S equals either 0 or 1 2 Optional stopping The gambler wagers a unit stake on each play until the random time T when she gambles for the last time That is 1 if n g T 0 if n gt T Sn and Zn YTML Now T n Sn 1Sn1 0 E 73 so that T is a stopping time It is a consequence of Proposition 74 that YTAn7quotn is a martingale whenever Y is a martingale as established earlier 3 Optional starting The gambler does not play until the T 1th play where T a stopping time In this case Sn 0 for n g T 57

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "I made $350 in just two days after posting my first study guide."

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.