MASSACHUSETTS INSTITUTE OF TECHNOLOGY 6.265/15.070J Lecture 11-Additional material Martingale Convergence Theorem Content. 1. Martingale Convergence Theorem 2. Doob’s Inequality Revisited 3. Martingale Convergence in Lp 4. Backward Martingales. SLLN Using Backward Martingale 5. Hewitt-Savage 0 − 1 Law 6. De-Finetti’s Theorem 1 Martingale Convergence Theorem Theorem 1. (Doob) Suppose Xn is a super-martingale which satisﬁes sup E[|Xn |] < ∞ n Then, almost surely X∞ = limn Xn exists and is ﬁnite in expectation. That is, deﬁne X∞ = lim sup Xn . Then Xn → X∞ a.s. and E[|X∞ |] < ∞. Proof. The proof relies “Doob’s Upcrossing Lemma”. For that consider Λ £ {ω : Xn (ω) does not converge to a limit in R} = {ω : lim inf Xn (ω) < lim sup Xn (ω)} n n = ∪a a, then C1 = 0 and it remains zero until the ﬁrst time Xn becomes smaller than a, at which point Cn switches to 1 and then continues as above. Consider Yn = (C · X)n = Ck (Xk − Xk−1 ) 1≤k≤n We claim that YN (ω) ≥ (b − a)UN [a, b] − (XN (ω) − a)− . Let UN [a, b] = k. Then there is 0 ≤ s1 < t1 < · · · < sk < tk ≤ N such that Xsi (ω) < a < b < Xti (ω), i = 1, · · · , k. By deﬁnition, Csi +1 = 1 for all i ≥ 1. Further, Ct (ω) = 1 for si + 1 ≤ t ≤ li ≤ ti where li ≤ ti is the smallest time t ≥ si such that Xt (ω) > b. Without the loss of generality, assume that s1 = min{n : Xn < a}. Let, sk+1 = min{n > tk : Xn (ω) < a}. Then, Cj (ω)(Xj (ω) − Xj−1 (ω)) YN (ω) = j≤N = Ct+1 (ω)(Xt+1 (ω) − Xt (ω))] [ 1≤i≤k si ≤t≤li Ct+1 (ω)(Xt+1 (ω) − Xt (ω)) (Because otherwise Ct (ω) = 0.) + t≥sk+1 (Xli (ω) − Xsi (ω)) + XN (ω) − Xsk+1 (ω), = 1≤i≤k where the term XN (ω) − Xsk+1 (ω) is deﬁned to be zero if sk+1 > N . Now, Xli (ω) − Xsi (ω) ≥ b − a. Now if XN (ω) ≥ Xsk+1 then XN (ω) − Xsk+1 ≥ 0. Otherwise |XN (ω) − Xsk+1 (ω) | ≤ |XN (ω) − a|. 3 Therefore we have YN (ω) ≥ UN [a, b](b − a) − (XN (ω) − a)− as claimed. Now, as we have established earlier, Yn = (C · X)n is super-MG since Cn ≥ 0 is predictable. That is, E[YN ] ≤ E[Y0 ] = 0 By claim, (b − a)E[UN [a, b]] ≤ E[(XN − a)− ] This completes the proof of Doob’s Lemma. Next, we wish to use this to prove P(Λa,b ) = 0. Lemma 2. For any a < b, P(Λa,b ) = 0. Proof. By deﬁnition Λa,b = {ω : U∞ [a, b] = ∞}. Now by Doob’s Lemma (b − a)E[UN [a, b]] ≤ E[(XN − a)− ] ≤ sup E[|Xn |] + |a| n <∞ Now, UN [a, b] / U∞ [a, b]. Hence by the Monotone Convergence Theorem, E[UN [a, b]] / E[U∞ [a, b]]. That is, E[U∞ [a, b]] < ∞. Hence, P(U∞ [a, b] = ∞) = 0. 2 Doob’s Inequality + . Given λ > 0, Theorem 2. Let Xn be a sub-MG and let Xn∗ = max0≤m≤n Xm let A = {Xn∗ ≥ λ}. Then, λP(A) ≤ E[Xn 1(A)] ≤ E[Xn+ ] Proof. Deﬁne stopping time ∗ N = min{m : Xm ≥ λ or m = n} Thus, P(N ≤ n) = 1. Now, by the Optional Stopping Theorem we have that XN ∧n is a sub-MG. But XN ∧n = XN . Thus E[XN ] ≤ E[Xn ] 4 (3) We have E[XN ] = E[XN 1(A)] + E[XN 1(Ac )] = E[XN 1(A)] + E[Xn 1(Ac )] (4) E[Xn ] = E[Xn 1(A)] + E[Xn 1(Ac )] (5) Similarly, From (3)∼ (5), we have E[XN 1(A)] ≤ E[Xn 1(A)] (6) λP(A) ≤ E[XN 1(A)] (7) But From (6) and (7), λP(A) ≤ E[Xn 1(A)] ≤ E[Xn+ 1(A)] ≤ E[Xn+ ]. (8) Suppose, Xn is non-negative sub-MG. Then, P( max Xk ≥ λ) ≤ 0≤k≤n 1 E[Xn ] λ If it were MG, then we also obtain 1 1 E[Xn ] = E[X0 ] λ λ P( max Xk ≥ λ) ≤ 0≤k≤n 3 Lp maximal inequality and Lp convergence Theorem 3. Let, Xn be a sub-MG. Suppose E[(Xn+ )p ] < ∞ for some p > 1. Then, 1 1 E[( max Xk+ )p ] p ≤ qE[(Xn+ )p ] p 0≤k≤n where 1q + p1 = 1. In particular, if Xn is a MG then |Xn | is a sub-MG and hence 1 1 E[( max |Xk |)p ] p ≤ qE[|Xn |p ] p 0≤k≤n 5 Before we state the proof, an important application is Theorem 4. If Xn is a martingale with supn E[|Xn |p ] < ∞ where p > 1, then Xn → X a.s. and in Lp , where X = lim supn Xn . We will ﬁrst prove Theorem 4 and then Theorem 3. Proof. (Theorem 4) Since supn E[|Xn |p ] < ∞, p > 1, by MG-convergence theorem, we have that Xn → X, a.s., where X = lim sup Xn . n For Lp convergence, we will use Lp -inequality of Theorem 3. That is, E[( sup |Xm |)p ] ≤ q p E[|Xn |p ] 0≤m≤n Now, sup0≤m≤n |Xm | / sup0≤m |Xm |. Therefore, by the Monotone Conver gence Theorem we obtain that E[sup |Xm |p ] ≤ q p sup E[|Xn |p ] < ∞ n 0≤m Thus, sup0≤m |Xm | ∈ Lp . Now, |Xn − X| ≤ 2 sup |Xm | 0≤m Therefore, by the Dominated Convergence Theorem E[|Xn − X|p ] → 0. Proof. (Theorem 3) We will use truncation of Xn∗ to prove the result. Let M be the truncation parameter: Xn∗,M = min(Xn∗ , M ). Now, consider the following: ∞ E[(Xn∗,M )p ] = 0 ≤ 0 ∞ pλp−1 P(Xn∗,M ≥ λ)dλ 1 pλp−1 [ E[Xn+ 1(Xn∗,M ≥ λ)]]dλ λ The above inequality follows from ( P(Xn∗,M ≥ λ) = 0, if M < λ ∗ P(Xn ≥ λ), if M ≥ λ 6 and Theorem 2. By an application of Fubini for non-negative integrands, we have pE[Xn+ Xn∗,M Z λp−2 dλ] 0 p E[Xn+ (Xn∗,M )p−1 ] p−1 1 1 p ≤ E[(Xn+ )p ] p E[(Xn∗,M )(p−1)q ] q , by Holder’s inequality. p−1 = Here, 1 q =1− 1 p (9) ⇒ q(p − 1) = p. Thus, we can simplify (9) 1 1 = qE[(Xn+ )p ] p E[(Xn∗,M )p ] q Thus, p ||Xn∗,M ||pp ≤ q||Xn+ ||p ||Xn∗,M ||pq That is, p(1− 1q ) ||Xn∗,M ||p ≤ q||Xn+ ||p Hence, ||Xn∗,M ||p ≤ q||Xn+ ||p . 4 Backward Martingale Let Fn be increasing sequence of σ-algebra, n ≤ 0, such that · · · ⊂ F−3 ⊂ F−2 ⊂ F−1 ⊂ F0 . Let Xn be Fn adapted, n ≤ 0, and E[Xn+1 |Fn ] = Xn , n < 0 Then Xn is called backward MG. Theorem 5. Let Xn be backward MG. Then lim Xn = X−∞ exists a.s. and in L1 . n→−∞ Compare with standard MG convergence results: (a): We need sup E[|Xn |] < ∞, or non-negative MG in Doob’s convergence theorem, which gives a.s. convergence not L1 . (b): For L1 , we need UI. And, it is necessary because if Xn → Xinf ty a.s. and L1 then there exists X ∈ F∞ s.t. Xn = E[X|Fn ]; and hence Xn is UI. 7 Proof of Theorem 5. Recall Doob’s convergence theorem’s proof. Let Λ : = {ω : Xn (ω) does not converge to a limit in [−∞, ∞]} = {ω : lim inf Xn (ω) < lim sup Xn (ω)} n n = ∪a,b:a,b∈Q {ω : lim inf Xn (ω) < a < b < lim sup Xn (ω)} n n = ∪a,b:a,b∈Q Λa,b Now, recall Un [a, b] is the number of upcrossing of [a, b] in Xn , Xn+1 , ..., X0 as n → −∞. By upcrossing inequality, it follows that (b − a)E[Un [a, b]] ≤ E[|X0 |] + |a| Since Un [a, b] / U∞ [a, b] and By monotone convergence theorem, we have E[U∞ [a, b]] < ∞ ⇒ P(Λa,b ) = 0 This implies Xn converges a.s. Now, Xn = E[X0 |Fn ]. Therefore, Xn is UI. This implies Xn → X−∞ in L1 . Theorem 6. If X−∞ = limn→−∞ Xn and F−∞ = ∩n Fn . Then X−∞ = E[X0 |F−∞ ]. Proof. Let Xn = E[X0 |Fn ]. If A ∈ F−∞ ⊂ Fn , then E[Xn ; A] = E[X0 ; A]. Now, |E[Xn ; A] − E[X−∞ ; A]| = |E[Xn − X−∞ ; A]| ≤ E[|Xn − X−∞ |; A] ≤ E[|Xn − X−∞ |] → 0 as n → −∞ (by Theorem 5) Hence, E[X−∞ ; A] = E[X0 ; A]. Thus, X−∞ = E[X0 |F−∞ ]. Theorem 7. Let Fn � F−∞ , and Y ∈ L1 . Then, E[Y |Fn ] → E[Y |F−∞ ] a.s. in L1 . Proof. Xn = E[Y |Fn ] is backward MG by deﬁnition. Therefore, Xn → X−∞ a.s. and in L1 . By Theorem 6, X−∞ = E[X0 |F−∞ ] = E[Y |F−∞ ]. Thus, E[Y |Fn ] → E[Y |F−∞ ]. 8 5 Strong Law of Large Number Theorem 8 (SLLN). Let ξ be i.i.d. with E[|ξi |] < ∞. Let Sn = ξ1 + ... + ξn . Let X−n = Snn . And, F−n = σ (Sn , ξn+1 , ...). Then, Sn |F−n−1 ] n n 1X = E[ξi |Sn+1 ] n E[X−n |F−n−1 ] = E[ i=1 = E[ξ1 |Sn+1 ] 1 = Sn+1 n+1 = X−n+1 Then X−n is backward MG. Proof. By Theorem 5∼ 7, we have X−n → X−∞ a.s. and in L1 , with X−∞ = E[ξ1 |F−∞ ]. Now F−∞ is in ξ (the exchangeable σ-algebra). By Hewitt-Savage (proved next) 0-1 law, ξ is trivial. That is, E[ξ1 |F−∞ ] is a constant. Therefore, E[X−∞ ] = E[ξ1 ] is also a constant. Thus, Sn = E[ξ1 ] n→∞ n X−∞ = lim 6 Hewitt-Savage 0-1 Law Theorem 9. Let X1 , ..., Xn be i.i.d. and ξ be the exchangeable σ − algebra: ξn = {A : πn A = A; ∀πn ∈ Sn }; ξ = ∪n ξn If A ∈ ξ, then P(A) ∈ {0, 1}. Proof. The key to the proof is the following Lemma: Lemma 3. Let X1 , ..., Xk be i.i.d. and define X 1 An (φ) = An (φ(Xi1 , ..., Xik )) npk (i1 ,...,ik )∈{1,...,n} If φ is bounded then An (φ) → E[φ(X1 , ..., Xk )] a.s. 9 Proof. An (φ) ∈ ξn by deﬁnition. So An (φ) = E[An (φ)|ξn ] 1 X E[φ(Xi1 , ..., Xik )|ξn ] = npk i1 ,...,ik 1 X E[φ(X1 , ..., Xk )|ξn ] = n pk i1 ,...,ik = E[φ(X1 , ..., Xk )|ξn ] (10) Let F−n = ξn . Then F−n � F−∞ = ξ. Then, for Y = φ(X1 , ..., Xk ). E[Y |F−n ] is backward MG. Therefore, E[Y |F−n ] → E[Y |F−∞ ] = E[φ(X1 , ..., Xk )|ξ] Thus, An (φ) → E[φ(X1 , ..., Xk )|ξ] (11) We want to show that indeed E[φ(X1 , ..., Xn )|ξ] is E[φ(X1 , ..., Xn )]. First, we show that E[φ(X1 , ..., Xn )|ξ] ∈ σ(Xk+1 , ...) since φ is bounded. Then, we ﬁnd that if E[X|G] ∈ F where X is independent of F then E[X|G] is constant, equal to E[X]. This will complete the proof of Lemma. First step: consider An (φ). It has npk terms in which there are k(n − 1)pk−1 terms containing X1 . Therefore, the effect of terms containing X1 is: Tn (1) ≡ 1 np k X φ(Xi1 , ..., Xik ) ≤ (i1 ,...,ik ) � 1 � k (n − 1)pk−1 ||φ||∞ np k (n − k)! (n − 1)! k ||φ||∞ n! (n − k)! k = ||φ||∞ → 0 as n → ∞ n = (12) −1 Let A−1 n (φ) = An (φ) − Tn (1). Then, we have An (φ) → E[φ(X1 , ..., Xn )|ξ] from (11) and (12). Thus, E[φ(φ(X1 , ..., Xn ))|ξ] is independent on X1 . Simi larly, repeating argument for X2 , ..., Xk we obtain that E[φ(X1 , ..., Xn )|ξ] ∈ σ(Xn+1 , ...) Second step: if E[X 2 ] ≤ ∞, E[X|G] ∈ F, X is independent of F then E[X|G] = E[X]. 10 Proof. Let Y = E[X|G]. Now Y ∈ F and X is independent on F1 we have that E[XY ] = E[X]E[Y ] = E[Y ]2 , since E[Y ] = E[X]. Now by deﬁnition of conditional expectation for any Z ∈ G, E[XZ] = E[Y Z]. Hence, for Z = Y , we have E[XY ] = E[Y 2 ]. Thus, E[Y 2 ] = E[Y ]2 ⇒ V ar(Y ) = 0 ⇒ Y = E[Y ] a.s. (13) This completes the proof of the Lemma. Now completing proof of H-S law. We have proved that An (φ) → E[φ(X1 , ..., Xn )] a.s. for all bounded φ dependent on ﬁnitely many components. By the ﬁrst step, ξ is independent on Gk = σ(X1 , ..., Xk ). This is true for all k. ∪k Gk is a π-system which contains Ω. Therefore, ξ is independent of σ(∪k Gk ) and ξ ⊂ σ(∪k Gk ). Thus, for all A ∈ ξ, A is independent of itself. Hence, P(A ∩ A) = P(A)P(A) ⇒ P (A) ∈ {0, 1}. 7 De Finetti’s Theorem Theorem 10. Given X1 , X2 , ... sequence of exchangeable, that is, for any n and πn ∈ Sn , (X1 , ..., Xn ) £ (Xπn (1) , ..., Xπn (n) ), then conditional on ξ, X1 , ..., Xn , ... are i.i.d. Proof. As in H-S’s proof and Lemma, deﬁne An (φ) = Then, due to exchangeability, 1 npk (i1 ,...,ik ) φ(Xi1 , ..., Xik ). An (φ) = E[An (φ)|ξn ] = E[φ(X1 , ..., Xn )|ξn ] → E[φ(X1 , ..., Xn )|ξ] by backward MG convergence theorem. (14) Since X1 , ... may not be i.i.d., ξ can be nontrivial. Therefore, the limit need not be constant. Consider a f : Rk−1 → R and g : R → R. Let In,k be set of all 11 distinct 1 ≤ i1 , ..., ik ≤ n, then npk−1 An (f )nAn (g) X = X g(Xm ) i∈In,k−1 f (Xi1 ,...,Xik−1 ) m≤n ⎡ = X f (Xi , ..., Xik−1 )g(Xik ) + i∈In,k X ⎣f (Xi1 , ..., Xik−1 ) k−1 X ⎤ g(Xij )⎦ j=1 i∈In,k−1 (15) Let φj (X1 , ..., Xk−1 ) = f (X1 , ..., Xk−1 )g(Xj ), 1 ≤ j ≤ k−1 and φ(X1 , ..., Xk ) = f (X1 , ..., Xk−1 )g(Xk ). Then, npk−1 An (f )nAn (g) = npk An (φ) + npk−1 k−1 X An (φj ) j=1 Dividing by npk , we have k X n 1 An (f )An (g) = An (φ) + An (φj ) n−k+1 n−k+1 j=1 by 15, and fact that ||f ||∞ , ||g||∞ < ∞, we have E[f (X1 , ..., Xk−1 |ξ)]E[g(X1 )|ξ] = E[f (X1 , ..., Xk−1 )g(Xk )|ξ] (16) Thus, we have using (16) that for any collection of bounded functions f1 , ..., fk , k k k k E[ fi (Xi )|ξ] = E[fi (Xi )|ξ] i=1 i=1 Message: given the “symmetry” assumption and given “exchangeable” statis tics, the underlying r.v. conditionally become i.i.d.! A nice example. Let Xi be exchangeable r.v.s. taking values in {0, 1}. Then there exists distributions on [0, 1] with distribution function F s.t. Z 1 P(X1 + ... + Xn = k) = θk (1 − θ)n−k dF (θ) 0 for all n. That is, mixture of i.i.d. r.v. 12

Additional Materials: Martingales Convergence Theorem

Related Documents

Recommended Documents

Description

Related Documents

Almost There!

Free up your schedule!

Take 5 seconds to unlock