Lecture 21: Tightness of Measures

MASSACHUSETTS INSTITUTE OF TECHNOLOGY 6.265/15.070J Lecture 21 Fall 2013 11/27/2013 Functional Law of Large Numbers. Construction of the Wiener Measure Content. 1. Additional technical results on weak convergence 2. Functional Strong Law of Large Numbers 3. Existence of Wiener measure (Brownian motion) 1 Additional technical results on weak convergence Given two metric spaces S1 , S2 and a measurable function f : S1 → S2 , sup­ pose S1 is equipped with some probability measure P. This induces a proba­ bility measure on S2 which is denoted by Pf −1 and is defined by Pf −1 (A) = P(f −1 (A)) for every measurable set A ⊂ S2 . Then for any random variable X : S2 → R, its expectation EPf −1 [X] is equal to EP [X(f )]. (Convince your­ self that this is the case by looking at the special case when f is a simple func­ tion). Theorem 1 (Mapping Theorem). Suppose Pn ⇒ P for a sequence of probability measures P, Pn on S1 and suppose f : S1 → S2 is continuous. Then Pn f −1 ⇒ Pf −1 on S2 . Proof. We use Portmentau theorem, in particular weak convergence character­ ization using bounded continuous functions. Thus let g : S2 → R be any bounded continuous function. Since it is continuous, it is also measurable, thus it is also a random variable defined on (S2 , B2 ), where B2 is the Borel σ-field on S2 . We have, EPn f −1 [g] = EPn [g(f )]. Since g is a bounded continuous, then the composition is also bounded continu­ ous. Therefore, by Portmanteau theorem EPn [g(f )] → EP [g(f )] = EPf −1 [g] 1 Definition 1. A sequence of probability measures Pn on metric space S is de­ fined to be tight if for every E > 0 there exists n0 and a compact set K ⊂ S, such that Pn (K) > 1 − E for all n > n0 . Theorem 2 (Prohorov’s Theorem). Suppose sequence Pn is tight. Then it con­ tains a weakly convergent subsequence Pn(k) ⇒ P. The converse of this theorem is also true, but we will not need this. We do not prove Prohorov’s Theorem. The proof can be found in [1]. Recall that Arzela-Ascoli Theorem provides a characterization of compact sets in C[0, T ]. We can use it now for characterization of tightness. Proposition 1. Suppose a sequence of measures Pn on C[0, T ] satisfies the fol­ lowing conditions: (i) There exists a ≥ 0 such that limn Pn (|x(0)| ≥ a) = 0. (ii) For each E > 0, limδ→0 lim supn Pn ({x : wx (δ) > E}) = 0. Then the sequence Pn is tight. Proof. Fix E > 0. From (i) we can find â and n0 large enough so that Pn (|x(0)| > â) < E for all n > n0 . For every m ≤ n0 we can also find am large enough so that Pm (|x(0)| > am ) < E. Take a = max(â, am ). Then Pn (|x(0)| > a) < E for all n. Let B = {x : |x(0)| ≤ a}. We just showed Pn (B) ≥ 1 − E. Similarly, for every k > 0 we can find δ̂k and nk such that Pn (wx (δ̂k ) > E/2k ) < E/2k for all n > nk . For every fixed n ≤ nk we can find a small enough δn > 0 such that Pn (wx (δn ) > E/2k ) < E/2k since by uniform continuity of x we have ∩δ>0 {wx (δ) > E/2k } = Ø a.s. Let δk = min(δ̂k , minn≤nk δn ). Let Bk = {x : wx (δk ) ≤ E}. Since Pn (Bkc ) < E/2k then Pn (∪k Bkc ) < E and Pn (∩k Bk ) ≥ 1 − E, for all n. Therefore Pn (B ∩ ∩k Bk ) ≥ 1 − 2E for all n. Then set K = B ∩ ∩k Bk is closed (check) and satisfies the conditions of Arzela-Ascoli Theorem. Therefore it is compact. 2 Functional Strong Law of Large Numbers (FSLLN) We are about to establish two very important limit results in the theory of stochas­ tic processes. In probability theory two cornerstone theorems are (Weak or Strong) Law of Large Numbers and Central Limit Theorem. These theorems have direct analogue in the theory of stochastic processes as Functional Strong Law of Large Numbers (FSLLN) and Functional Central Limit Theorem (FCLT) also known as Donsker Theorem. The second theorem contains in it the fact that Wiener Measure exists. 2 We first describe the setup. Consider a sequence of i.i.d. random variables X1 , X2 , . . . , Xn , . . .. We assume that E[X1 ] = 0, E[X12 ] = σ 2 . We can view each realization of an infinite sequence (Xn (ω)) as a sample in a product space R∞ equipped with product type σ-field F and probability measure Pi.i.d. , in­ duced by the probability distribution of X1 . Define Sn = 1≤k≤n Xk . Fix an interval [0, T ] and for each n ≥ 1 and t ∈ [0, T ] consider the following function Nn (t) = S nt (ω) n + (nt − nt ) X nt +1 (ω) n . (1) This is a piece-wise linear continuous function in C[0, T ]. Theorem 3 (Functional Strong Law of Large Numbers (FSLLN)). Given an i.i.d. sequence (Xn ), n ≥ 1 with E[X1 ] = 0, E[|X1 |] < ∞, for every T > 0, the sequence of functions Nn : [0, T ] → R converges to zero almost surely. Namely P(INn (ω)IT → 0) = P( sup |Nn (t, ω)| → 0) = 1 0≤t≤T As we see, just as SLLN, the FSLLN holds without any assumptions on the variance of X1 , that is even if σ = ∞. Here is another way to state FSLLN. We may consider functions Nn defined on entire [0, ∞) using the same defining identity (1). Recall that sets [0, T ] are compact in R. An equivalent way of saying FSLLN is Nn converges to zero almost surely uniformly on compact sets. Proof. Fix E > 0 and T > 0. By SLLN we have that for almost all realizations ω of an sequence X1 (ω), X2 (ω), . . ., there exists n0 (ω) such that for all n > n0 (ω), Sn (ω) E < n T We let M (ω) = max1≤m≤n0 (ω) Sm (ω). We claim that for n > M (ω)/E, there holds sup |Nn (t)| < E. 0≤t≤T We consider two cases. Suppose t ∈ [0, T ] is such that nt > n0 (ω). Then Nn (t) ≤ max �S nt n 3 (ω) S , nt +1 (ω) n � . We have Sbntc (ω) Sbntc (ω ) bntc  = ≤ t ≤ . n bntc n T Using a similar bound on Sbntc+1 (ω), we obtain Nn (t) ≤ . n Suppose now t is such that nt ≤ n0 (ω). Then |Nn (t)| ≤ M (ω) < , n since, by our choice n > M (ω)/. We conclude sup0≤t≤T |Nn (t)| <  for all n > M (ω)/. This concludes the proof. 3 Weiner measure FSSLN was a simpler functional limit theorem. Here we consider instead a ”Gaussian” scaling of a random walk Sn and establish existence of the Weiner measure (Brownian motion) as well as FCLT. Thus suppose we have a sequence of i.i.d. random variables X1 , . . . , Xn with mean zero but finite variance σ 2 < ∞. Instead of function (1) consider the following function Nn (t, ω) = Sbntc (ω) Xbntc+1 (ω) √ √ + (nt − bntc) , σ n σ n n ≥ 1, t ∈ [0, T ]. (2) This is again a piece-wise linear continuous function. Then for each n we obtain a mapping ψn : R∞ → C[0, T ]. Of course, for each n, the mapping ψn depends only on the first nT + 1 coordinates of samples in R∞ . Lemma 1. Each mapping ψn is measurable. Proof. Here is where it helps to know that Kolmogorov field is identical to Borel field on C[0, T ], that is Theorem 1.4 from the previous lecture. Indeed, now it suffices to show that that ψn−1 (A) is measurable for each set A of the form 4 A = πt−1 (−∞, y], as these sets generate Kolmogorov/Borel σ-field. Each set ψn−1 (πt−1 (−∞, y]) is the set of all realizations Nn (ω) such that P 1≤k≤m Xk (ω) √ + (nt − m)Xm+1 (ω) ≤ y . Nn (t, ω) = σ n where m = bntc. This defines a measurable subset of Rm+1 ⊂ R∞ . One to observe that the function f : Rm+1 → R defined by way to see this is P xk √ f (x1 , . . . , xm ) = 1≤k≤m + (nt − m)xm+1 is continuous and therefore is σ n measurable. We conclude that ψn is measurable for each n. Thus each ψn induces a probability measure on C[0, T ], which we denote by Pn . This probability measure is defined by Pn (A) = Pi.i.d. (ψn−1 (A)) = Pi.i.d. (Nn (ω) ∈ A). We now establish the principal result of this lecture – existence of Weiner measure, namely, the existence of a Brownian motion. Theorem 4 (Existence of Wiener measure). A sequence of measures Pn has a weak limit P∗ which satisfies the property of Wiener measure on C[0, T ]. The proof of this fact is quite involved and we give only its scheme, skipping some technical results. First let us outline the main steps in the proof. In the previous lecture we considered projection mappings Pt : C[0, T ] → R. Similarly, for any collection 0 ≤ t1 < · · · < tk we can consider πt1 ,...,tk (x) = (x(t1 ), . . . , x(tk )) ∈ Rk . 1. We first show that the sequence of measures Pn on C[0, T ] is tight. We use this to argue that there exists a subsequence Pn(k) which converges to some measure π ∗ . 2. We show that π ∗ satisfies the properties of Wiener measures. For this purposes we look at the projected measures πt1 ,...,tk (π ∗ ) on Rk and show that these give a joint Gaussian distribution, the kind arising in a Brownian motion (that is the joint distribution of (B(t1 ), B(t2 ), . . . , B(tk ))). At this point the existence of Wiener measure is established. 3. We then show that in fact the weak convergence πn∗ ⇒ π holds. Proof sketch. We begin with the following technical and quite delicate result about random walks. 5 Lemma 2. The following identity holds for random walks Sn = X1 + · · · + Xn : √ lim lim sup λ2 P(max |Sk | ≥ λσ n) = 0. (3) λ→∞ n→∞ k≤n Note, that this is indeed a very subtle result. We could try to use submartingale inequality, since Sk is sub-martingale. It will give √ 1 E[S 2 ] P(max |Sk | ≥ λσ n) ≤ 2 2n = 2 . k≤n λ σ n λ So by taking a product with λ2 we do not obtain convergence to zero. On the other hand note that if the random variables have a finite fourth moment E[Xn4 ] < ∞, then the result follows from the sub-martingale inequality by considering Sn4 in place of Sn2 (exercise). The proof of this lemma is based on the following fact: Proposition 2 (Etemadi’s Inequality,[1]). For every α > 0 P(max |Sk | ≥ 3α) ≤ 3 max P(|Sk | ≥ α) k≤n k≤n Proof. Let Bk be the event |Sk | ≥ 3α, |Sj | < 3α, j < k. Then P(max |Sk | ≥ 3α) ≤ P(|Sn | ≥ α) + k≤n P(Bk ∩ |Sn | < α) k≤n ≤ P(|Sn | ≥ α) + P(Bk ∩ |Sn − Sk | > 2α) k≤n = P(|Sn | ≥ α) + P(Bk )P(|Sn − Sk | > 2α) k≤n ≤ P(|Sn | ≥ α) + max P(|Sn − Sk | ≥ 2α) k≤n ≤ P(|Sn | ≥ α) + max(P(|Sn | ≥ α) + P(|Sk | ≥ α)) k≤n ≤ 3 max P(|Sk | ≥ α). k≤n Now we can prove Lemma 2. Proof of Lemma 2. Applying Etemadi’s Inequality √ √ P(max |Sk | ≥ λσ n) ≤ 3 max P(|Sk | ≥ (1/3)λσ n) k≤n k≤n 6 Fix E > 0. Let Φ denote the cumulative standard normal distribution. Find λ0 large enough so that 2λ2 (1 − Φ(λ/3)) < E/3 for all λ ≥ λ0 . Fix any such λ. By the CLT we can find n0 = n0 (λ) large enough so that √ P(|Sn | ≥ (1/3)λσ n) ≤ 2(1 − Φ(λ/3)) + E/(3λ2 ) √ for all n ≥ n0 , implying λ2 P(|Sn | ≥ (1/3)λσ n) ≤ 2E/3. Now fix any n ≥ 27n0 /E and any k ≤ n. If k ≥ n0 , then from the derived bound we have √ √ λ2 P(|Sk | ≥ (1/3)λσ n) ≤ λ2 P(|Sk | ≥ (1/3)λσ k) ≤ 2E/3. On the other hand, if k ≤ n0 then √ λ2 E[Sk2 ] σ2k λ2 P(|Sk | ≥ (1/3)λσ n) ≤ 2 = ≤ E/3. (1/9)σ 2 n (λ /9)σ 2 n We conclude that for all n ≥ 27n0 /E, √ λ2 max P(|Sk | ≥ (1/3)λσ n) ≤ E/3, 1≤k≤n from which we obtain √ λ2 lim sup P(max |Sk | ≥ λσ n) ≤ E k≤n n Since E > 0 was arbitrary, we obtain the result. The next result which we also do not prove says that the property (3) implies tightness of the sequence of measures Pn on C[0, T ]. Lemma 3. The following convergence holds for every E > 0. lim lim sup P(wNn (δ) ≥ E) = 0. (4) δ→0 n→∞ As a result the sequence of measures Pn is tight. Proof. Observe that wNn (δ) ≤ max i≤j≤nT :j−i≤δn | i≤k≤j √ σ n Xk | . Exercise 1. Use this to finish the proof of the lemma. Hint: partition interval [0, T ] into length δ intervals and use Lemma 2. 7 Let us now see how Lemma 2 implies tightness. We use characterization given by Proposition 1. First for any positive a, Pn (|x(0)| ≥ a) = P(|Nn (0)| > 0) = 0 since Nn (0) = 0. Now Pn (wx (δ) > ) = P(wNn (δ) > ). From the first part of the lemma we know that the double convergence (4) holds. This means that condition (ii) of Proposition 1 holds as well. We now return to the construction of Wiener measure. Lemma 3 implies that the sequence of probability measures Pn on C[0, T ] is tight. Therefore, by Prohorov’s Theorem, it contains a weakly convergent subsequence Pn(k) ⇒ P∗ . Proposition 3. P∗ satisfies the property of the Wiener measure. Proof. Since P∗ is defined on the space of continuous functions, then continuity of every sample is immediate. We need to establish independence of increments and the fact that increments are stationary Gaussian. Thus we fix 0 ≤ t1 < · · · < tk and y1 , . . . , yk ∈ Rk . To preserve the continuity, we still denote elements of C[0, T ] by x, x(t) or x(ω, t) whereas before we used notations ω, B(ω), B(t, ω). Consider the random vector πt1 (Nn ) = Nn (t1 ). This is simply the random variable Sbnt1 c (ω) Xbnt1 c+1 (ω) √ √ + (nt1 − bnt1 c) σ n σ n The second term in the sum converges to zero in probability. The first term we rewrite as √ Sbnt1 c (ω) b nt1 c √ √ . n σ b nt1 c and by CLT it converges to a normal N (0, t1 ) distribution. Similarly, consider P Xbnt2 c+1 (ω) nt1 < m≤nt2 Xm (ω ) √ √ Nn (t2 ) − Nn (t1 ) = + (nt2 − bnt2 c) σ n σ n Xbnt1 c+1 (ω) √ − (nt1 − bnt1 c) σ n Again by CLT we see that it converges to normal N (0, t2 − t1 ) distribution. Moreover, the joint distribution of (Nn (t1 ), Nn (t2 ) − Nn (t1 )) converges to a joint distribution of two independent normals with zero mean and variances t1 , t2 − t1 . Namely, the (Nn (t1 ), Nn (t2 )) converges in distribution to 8 (Z1 , Z1 + Z2 ), where Z1 , Z2 are independent normal random variables with zero mean and variances t1 , t2 − t1 . By a similar token, we see that the distribution of the random vector πt1 ,...,tk (Nn ) = (Nn (t1 ), Nn (t2 ), . . . , Nn (tk )) converges in distribution to (Z1 , Z1 + Z2 , . . . , Z1 + · · · + Zk ) where Zj , 1 ≤ j ≤ k are independent zero mean normal random variables with variances t1 , t2 − t1 , . . . , tk − tk−1 . On the other hand the distribution of πt1 ,...,tk (Nn ) is Pn πt−1 = Pi.i.d. ψn−1 πt−1 . 1 ,...,tk 1 ,...,tk Since Pn(k) ⇒ P∗ and π is continuous, then, applying mapping theorem (The­ ⇒ P∗ πt−1 . Combining, these two orem 1) we conclude that Pn(k) πt−1 1 ,...,tk 1 ,...,tk −1 ∗ facts, we conclude that the probability measure P πt1 ,...,tk is the probability measure of (Z1 , Z1 + Z2 , . . . , Z1 + · · · + Zk ) (where again Zj are indepen­ dent normal, etc ...). What does this mean? This means that when we select x ∈ C[0, T ] according to the probability measure P∗ and look at its projection πt1 ,...,tk (x) = (x(t1 ), . . . , x(tk )), the probability distribution of this random vector is the distribution of (Z1 , Z1 + Z2 , . . . , Z1 + · · · + Zk ). This means that x has independent increments with zero mean Gaussian distribution and variances t1 , t2 − t1 , . . . , tk − tk−1 . This is precisely the property we needed to establish for P∗ in order to argue that it is indeed Wiener measure. This concludes the proof of Proposition 3 – the fact that P∗ is the Weiner measure. We also need to show that the convergence Pn ⇒ P holds. For this purpose we will show that P∗ is unique. In this case the convergence holds. Indeed, suppose otherwise, there exists a subsequence n(k) such that Pn(k) ⇒ P∗ . Then we can find a bounded continuous r.v. X, such that EPn(k) X ⇒ EP∗ X. Then we can find E0 and a subsequence n(ki ) of n(k) such that |EPn(ki ) X − EP∗ X| ≥ E0 for all i. By tightness we can find a further subsequence n(kij ) of n(ki ) which converges weakly to some limiting probability measure P̃. But we have seen that every such weak limit has to be a Wiener measure which is unique. Namely P̃ = P∗ . This is a contradiction since |EPn(ki ) X − EP∗ X| ≥ E0 . j It remains to show the uniqueness of Wiener measure. This follows again from the fact that the Kolmogorov σ-field coincides with the Borel σ-field on C[0, T ]. But the properties of Wiener measure (independent increments with variances given by the length of the time increments) uniquely define probabil­ ity on generating sets obtained via projections πt1 ,...,tk : C[0, T ] → Rk . This concludes the proof of uniqueness. 9 4 Applications Theorem 4 has applications beyond the existence of Wiener measure. Here is one of them. Theorem 5. The following convergence holds max1≤k≤n Sk √ ⇒ sup B(t) σ n 0≤t≤T (5) where B is the standard Brownian motion. As a result, for every y lim P( n max1≤k≤n Sk √ ≥ y) = 2(1 − Φ(y)), σ n (6) where Φ is standard normal distribution. Proof. The function g(x) = sup0≤t≤T x(t) is a continuous function on C[0, T ] (check this). Since by Theorem 4, Pn ⇒ P∗ then, by Mapping Theorem, g(Nn ) ⇒ g(B), where B is a standard Brownian motion – random sample max1≤k≤n Sk √ from the Wiener measure P∗ . But g(Nn ) = sup0≤t≤T Nn (t) = . σ n We conclude that (5) holds. To prove the second part we note that the set A = {x ∈ C[0, T ] : sup0≤t≤T x(t) = y} has P∗ (A) = 0 – recall that the maximum sup0≤t≤T B(t) of a Brownian motion has density. Also note that A is the boundary of the set {x : sup0≤t≤T x(t) ≤ y}. Therefore by Portmentau theorem, (6) holds. 5 Additional reading materials • Billingsley [1] Chapter 2, Section 8. References [1] P. Billingsley, Convergence of probability measures, Wiley-Interscience publication, 1999. 10