Lecture 24 Notes: Martingales - Stopping and Converging

6.262: Discrete Stochastic Processes L24: Martingales: stopping and converging Outline: • Review of martingales • Stopped martingales • The Kolmogorov submartingale inequality • SLLN for IID rv’s with a variance • The martingale convergence theorem A sequence {Zn; n ≥ 1} of rv’s is a martingale if � � E Zn | Zn−1, Zn−2, . . . , Z1 = Zn−1; for all n ≥ 1. � E [|Zn|] < ∞ (1) � Recall that E Zn | Zn−1, . . . , Z1 is a rv that maps each sample point ω to the conditional expectation of Zn con­ ditional on Z1(ω), . . . , Zn−1(ω). For a martingale, this ex­ pectation must be the rv Zn−1. Lemma: For a martingale, {Zn; n ≥ 1}, and for n > i ≥ 1, � � E Zn | Zi, Zi−1 . . . , Z1 = Zi : E [Zn] = E [Zi] Can you figure out why E [Zn | Zm, . . . Z1] = Zn for m ≥ n? Note that E [Zn | Z1] = Z1 and E [Zn] = E [Z1] for all n > 1. Simple Examples of martingales � 1) Zero-mean RW: If Zn = n i=1 Xi where {Xi; i ≥ 1} are IID and zero mean, then {Zn; n ≥ 1} is a martingale. � � � 2) If Zn = n i=1 Xi where E Xi | Xi−1, . . . , X1 = 0 for each i ≥ 1, then {Zn; n ≥ 1} is a martingale. 3) Let Xi = UiYi where {Ui; i ≥ 1} are IID, equiprobable ±1. The Yi are independent of the Ui. Then {Zn; n ≥ 1}, where Zn = X1 + · · · Xn, is a martingale. 4) Product form martingales: Let {Xi; i ≥ 1} be a se­ quence of IID unit-mean rv’s. Then {Zn; n ≥ 1}, where Zn = X1X2 · · · Xn, is a martingale. If pX (0) = pX (2) = 1/2, then pZn (2n) = 2−n and pZn (0) = 1 − 2−n. Thus, limn→∞ Zn = 0 WP1 and limn→∞ E [Zn] = 1. Sub- and supermartingales are sequences {Zn; n ≥ 1} with E [|Zn|] < ∞ for which inequalities replace the equalities of martingales. For all n ≥ 1, � � E Zn | Zn−1, . . . , Z1 ≥ Zn−1 � � E Zn | Zn−1, . . . , Z1 ≤ Zn−1 submartingale supermartingale If {Zn; n ≥ 1} is a submartingale, then {−Zn; n ≥ 1} is a supermartingale and vice-versa, so we consider only submartingales. For submartingales, E [Zn | Zi, . . . , Z1] ≥ Zi E [Zn] ≥ E [Zi] for all n > i > 0 for all n > i > 0 Convex functions A function h(x), R → R, is convex if each tangent to the curve lies on or below the curve. The condition h��(x) ≥ 0 is sufficient but not necessary. ✭ ✭✭ ✟ ✟ ✭✭✭✭ ✟✟ ✭✭✭✭ ✭ ✟ ✭ ✭ ✟ ✭✭✭✭ E [h(Z )] ✟✟✟ ✭✭✭✭ ✭❤ ❤ ❤❤❤❤ ✟ ❤❤❤❤ ✟ ❤ ❤✟ 1 h(x) h(x ) + c(x − x1) c = h�(x1) x1 = E [Z] h(x) = |x| � ❅ ❅ � ❅ � ❅ � ❅ � ❅� x Lemma (Jensen’s inequality): If h is convex and Z is a rv with finite expectation, then h(E [Z]) ≤ E [h(Z)] Jensen’s inequality leads to the following theorem. See proof in text. Thm 7.8.1: If {Zn; n ≥ 1} is a martingale or submartin­ gale, if h is convex, and if E [|h(Zn)|] < ∞ for all n, then {h(Zn); n ≥ 1} is a submartingale. For example, if {Zn; n ≥ 1} is a martingale, then {|Zn|; n ≥ 1}, {Zn2; n ≥ 1} and {erZn ; n ≥ 1 are submartingales if the marginal expected values exist. Stopped martingales The definition of a stopping trial J for a stochastic pro­ cess {Zn; n ≥ 1} applies to any process. That is, J must be a rv and {J = n} must be specified by {Z1, . . . , Zn}. A possibly defective rv J is a mapping from Ω to the extended reals R+ where {J = ∞} and {J = −∞} might have positive probability. The other provisos of rv’s still hold. A possibly defective stopping trial is thus a stopping rule in which stopping may never happen (such as RW’s with a single threshold). A stopped process {Zn∗ ; n ≥ 1} for a possibly defective stopping time J on a process {Zn; n ≥ 1} satisfies Zn∗ = Zn if n ≤ J and Zn∗ = ZJ if n > J. For example, a given gambling strategy, where Zn is the net worth at time n, could be modified to stop when Zn reaches some given value. Then Zn∗ would remain at that value forever after, while Zn follows the original strategy. Theorem: If J is a possibly defective stopping rule for a martingale (submartingale), {Zn; n ≥ 1} , then the stopped process {Zn∗ ; n ≥ 1} is a martingale (submartin­ gale). Pf: Obvious??? The intuition here is that before stop­ ping occurs, Zn∗ = Zn, so Zn∗ satisfies the martingale (subm.) condition. Afterwards, Zn∗ is constant, so it again satisfies the martingale (subm) condition. Proof that {Zn∗ ; n ≥ 1} is a martingale: Note that Zn∗ = � n−1 � m=1 ZmI{J=m} + ZnI{J ≥n} Thus |Zn∗ | ≤ m 0 or β < 0. Then E [Zn∗ ] = 1 for all n ≥ 1. Also, limn→∞ Zn∗ = ZJ WP1 and E [ZJ ] = E [exp[rSJ − Jγ(r)] = 1 This is Wald’s identity in a more general form. The connection of limn Zn∗ to ZJ needs more care (see Section 7.8), but this shows the power of martingales. Kolmgorov’s submartingale inequality Thm: Let {Zn; n ≥ 1} be a non-negative submartingale. Then for any positive integer m and any a > 0, Pr � � max Zi ≥ a ≤ 1≤i≤m E [Zm] . a (2) If we replace the max with Zm, this is the lowly but useful Markov inequality. Proof: Let J be the stopping time defined as the smallest n ≤ m such that Zn ≥ a. If Zn ≥ a for some n ≤ m, then J is the smallest n for which Zn ≥ a. If Zn < a for all n ≤ m, then J = m. Thus the process must stop by time m, and ZJ ≥ a iff Zn ≥ a for some n ≤ m. Thus Pr � � max Zn ≥ a = Pr{ZJ ≥ a} ≤ 1≤n≤m E [ZJ ] . a Since the process must be stopped by time m, we have ∗. ZJ = Zm ∗ ] ≤ E [Z ], so the right hand side above is less than E [Zm m or equal to E [Zm] /a, completing the proof. The Kolmogorove submartingale inequality is a strength­ ening of the Markov inequality. The Chebyshev inequality is strengthened in the same way. � � Let {Zn; n ≥ 1} be a martingale with E Zn2 < ∞ for all n ≥ 1. Then Pr � � max |Zn| ≥ b ≤ 1≤n≤m � 2 E Zm b2 � ; for all integer m ≥ 2, all b > 0. Let {Sn; n ≥ 1} be a RW with Sn = X1 +· · ·+Xn where each Xi has mean X and variance σ 2. Then for any positive integer m and any � > 0, � � σ2 . Pr max |Sn − nX | ≥ m� ≤ 1≤n≤m m�2 SLLN for IID rv’s with a variance Thm: Let {Xi; i ≥ 1} be a sequence of IID random vari­ ables with mean X and standard deviation σ < ∞. Let Sn = X1 + · · · + Xn. Then for any � > 0, � Sn Pr lim =X n→∞ n Idea of proof: Pr =1 �   ∞ �  �  m=k � max m |Sn − nX| ≥ 2m� ≤  1≤n≤2 Then lower bound the left term to Pr  ∞ �  �  m=k max 2m−1≤n≤2m ∞ � σ2 2σ 2 = k 2 2m�2 2 � m=k �  |Sn − nX | ≥ 2n�  The martingale convergence theorem Thm: Let {Zn; n ≥ 1} be a martingale and assume that there is some finite M such that E [|Zn|] ≤ M for all n. Then there is a random variable Z such that, limn→∞ Zn = Z WP1. The text proves � � the theorem with the additional � con­ � 2 straint that E Zn is bounded. Either bounded E Zn2 or bounded E [|Zn|] is a very strong constraint, but the the­ orem is still very powerful. For a branching process {Xn; n ≥ 1} where the number Y of offspring of an element has Y > 1, we saw that n {Xn/Y ; n ≥ 1} is a martingale satisfying the constraint, n so X n/Y → Z WP1.