Convergence of Random Variables

MASSACHUSETTS INSTITUTE OF TECHNOLOGY 6.436J/15.085J Lecture 16 Fall 2018 CONVERGENCE OF RANDOM VARIABLES Contents 1. Definitions 2. Convergence in distribution 3. The hierarchy of convergence concepts 1 DEFINITIONS 1.1 Almost sure convergence Definition 1. We say that Xn converges to X almost surely (a.s.), and write a.s. Xn → X , if there is a (measurable) set A ⊂ Ω such that: (a) limn!1 Xn (ω) = X(ω), for all ω ∈ A; (b) P(A) = 1. Note that for a.s. convergence to be relevant, all random variables need to be defined on the same probability space (one experiment). Furthermore, the different random variables Xn are generally highly dependent. Two common cases where a.s. convergence arises are the following. (a) The probabilistic experiment runs over time. To each time n, we associate a nonnegative random variable Zn (e.g., income on dayP n). Let Xn = P n 1 k=1 Zk be the income on the first n days. Let X = k=1 Zk be the lifetime income. Note that X is well defined (as an extended real number) a.s. for every ω ∈ Ω, because of our assumption that Zk ≥ 0, and Xn → X. 1 (b) The various random variables are defined as different functions of a single underlying random variable. More precisely, suppose that Y is a random variable, and let gn : R → R be measurable functions. Let Xn = gn (Y ) [which really means, Xn (ω) = gn (Y (ω)), for all ω]. Suppose a.s. that limn!1 gn (y) = g(y) for every y. Then, Xn → X. For example, let gn (y) = y + y 2 /n, which converges to g(y) = y. We then have a.s. Y + Y 2 /n → Y . a.s. When Xn → X, we always have φXn (t) → φX (t), ∀ t, by the dominated convergence theorem. On the other hand, the relation E[Xn ] → E[X] is not always true; sufficient conditions are provided by the monotone and dominated convergence theorems. For an example, where convergence of expectations fails to hold, consider a random variable U which is uniform on [0, 1], and let: ˆ n, if U ≤ 1/n, Xn = (1) 0, if U > 1/n. We have lim E[Xn ] = lim nP(U ≤ 1/n) = 1. n!1 n!1 On the other hand, for any outcome ω for which U (ω) > 0 (which happens with a.s. probability one), Xn (ω) converges to zero. Thus, Xn → 0, but E[Xn ] does not converge to zero. 1.2 Convergence in distribution Definition 2. Let X and Xn , n ∈ N, be random variables with CDFs F and Fn , respectively. We say that the sequence Xn converges to X in distribud tion, and write Xn → X , if lim Fn (x) = F (x), n!1 for every x ∈ R at which F is continuous. 2 (a) Recall that CDFs have discontinuities (“jumps”) only at the points that have positive probability mass. More precisely, F is continuous at x if and only if P(X = x) = 0. (b) Let Xn = 1/n, and X = 0, with probability 1. Note that FXn (0) = P(Xn ≤ 0) = 0, for every n, but FX (0) = 1. Still, because of the excepd tion in the above definition, we have Xn → X. More generally, if Xn = an d and X = a, with probability 1, and an → a, then Xn → X. Thus, convergence in distribution is consistent with the definition of convergence of real numbers. This would not have been the case if the definition required the condition limn!1 Fn (x) = F (x) to hold at every x. (c) Note that this definition just involves the marginal distributions of the random variables involved. These random variables may even be defined on different probability spaces. (d) Let Y be a random variable whose PDF is symmetric around 0. Namely, for every real value t, P(Y ≤ t) = P(Y ≥ −t). Let Xn = (−1)n Y . Then, every Xn has the same distribution, so, trivially, Xn converges to Y in distribution. However, for almost all ω, the sequence Xn (ω) does not converge. (e) If we are dealing with random variables whose distribution is in a parametric class, (e.g., if every Xn is exponential with parameter λn ), and the parameters converge (e.g., if λn → λ > 0 and X is exponential with parameter λ), then we usually have convergence of Xn to X, in distribution. Check this for the case of exponential distributions. (f) It is possible for a sequence of discrete random variables to converge in distribution to a continuous one. For example, if Yn is uniform on {1, . . . , n} and Xn = Yn /n, then Xn converges in distribution to a random variable which is uniform on [0, 1] (exercise). (g) Similarly, it is possible for a sequence of continuous random variables to converge in distribution to a discrete one. For example if Xn is uniform on [0, 1/n], then Xn converges in distribution to a discrete random variable which is identically equal to zero (exercise). (h) If X and all Xn are continuous, convergence in distribution does not imply convergence of the corresponding PDFs. (Exercise. Find an example, by emulating the example in (f).) (i) If X and all Xn are integer-valued, convergence in distribution turns out to be equivalent to convergence of the corresponding PMFs: pXn (k) → pX (k), for all k.(exercise). 3 1.3 Convergence in probability Definition 3. (a) We say that a sequence of random variables Xn (not necessarily defined on the same probability space) converges in probability to a i.p. real number c, and write Xn → c, if lim P(|Xn − c| ≥ ǫ) = 0, n!1 ∀ ǫ > 0. (b) Suppose that X and Xn , n ∈ N are all defined on the same probability space. We say that the sequence Xn converges to X , in probability, and i.p. write Xn → X , if Xn − X converges to zero, in probability, i.e., lim P(|Xn − X| ≥ ǫ) = 0, n!1 ∀ ǫ > 0. (a) When X in part (b) of the definition is deterministic, say equal to some constant c, then the two parts of the above definition are consistent with each other. i.p. d (b) As we will see below convergence Xn → c is equivalent to Xn → c. i.p. (c) The intuitive content of the statement Xn → c is that in the limit as n increases, almost all of the probability mass becomes concentrated in a small interval around c, no matter how small this interval is. On the other hand, for any fixed n, there can be a small probability mass outside this interval, with a slowly decaying tail. Such a tail can have a strong impact on expected values. For this reason, convergence in probability does not have any implications on expected values. See for instance the example in Eq. (1). We i.p. have Xn → X, but E[Xn ] does not converge to E[X]. i.p. i.p. (d) If Xn → X and Yn → Y , and all random variables are defined on the same i.p. probability space, then (Xn + Yn ) → (X + Y ) (exercise). The following is a convenient characterization, showing that convergence in probability is very closely related to almost sure convergence. i.p. Proposition 1. Xn → X iff for every subsequence Xnk there exists a subsuba.s. sequence Xnks → X. 4 2 CONVERGENCE IN DISTRIBUTION The following result provides insights into the meaning of convergence in distribution. Recall that the boundary ∂E of a set E is a set of simultaneous limit points of E and E c : ∂E , [E] ∩ [E c ], where [·] denotes the closure. Also recall that quantile function q of the CDF F is a right-continuous inverse of the CDF: q(s) , inf{x : F (x) > s} Theorem 1. Let Xn and X be random variables, Pn and P their distributions and qn , q their quantile functions. The following are equivalent: d (i) Xn → X (ii) Quantile functions qn (u) → q(u) for every continuity point u of q. (iii) E[f (Xn )] → E[f (X)] for every bounded continuous f . (iv) Pn [E] → P[E] for every Borel E with P[∂E] = 0 (v) lim supn!1 Pn [F ] ≤ P[F ] for every closed F (vi) lim inf n!1 Pn [U ] ≥ P[U ] for every open U . Note: The last four statements remain equivalent for a general metric space, in which case any of them is usually taken as definition of weak convergence of measures. Proof. Equivalence of the first two follows by definition of quantiles. Indeed, in the case when F is continuous and strictly monotonically increasing this is clear. The general case follows from carefully analyzing the inclusions: {(x, y) : y < F (x)} ⊆ {(x, y) : q(y) ≤ x} ⊆ {(x, y) : y ≤ F (x)} valid for any pair of a CDF and its quantile. Next, (ii) implies (iii), (v) and (vi) by the Theorem to follow next (Skorokhod a.s. a.s. representation), since Yn → Y implies f (Yn ) → f (Y ) for continuous functions and lim supn!1 1F (Yn ) ≤ 1F (Y ). The statement of (iii) and (v) then follows by the BCT and Fatou’s lemma respectively. Furthermore, (v) and (vi) are equivalent by taking complements. To show (v) and (vi) imply (iv) let F = [E] and U = intE = [E c ]c . Then ∂E = F \ U . 5 Then since U ⊆ E ⊆ F we have P[U ] ≤ lim inf Pn [U ] ≤ lim inf Pn [E] n!1 (2) n!1 ≤ lim sup Pn [E] ≤ lim sup Pn [F ] ≤ P[F ] n!1 (3) n!1 Thus when P[∂E] = 0 we have P[F ] = P[U ] and thus Pn [E] → P[E]. On the other hand, (iv) implies (i) by taking E = (−∞, x] for any x – point of continuity of F . So overall we have shown: (i) ⇐⇒ (ii) ⇒ (v) ⇐⇒ (vi) ⇒ (iv) ⇒ (i) ⇒ (iii) It only remains to show that (iii) implies any of the other ones. For example, we can show (iii) ⇒ (v). To that end take fǫ (x) = 1 − 1 min(d(x, F ), ǫ) , ǫ where d(x, F ) = inf y2F |x − y| is the minimum distance between x and F . It is easy to see d(x, F ) is a continuous function of x which is equal to zero only on F itself. Furthermore, fǫ ց 1F as ǫ → 0. So we have: inf fǫ (Xn ) = 1F (Xn ) (4) inf E[fǫ (Xn )] = Pn [F ] (5) ǫ>0 and by the BCT ǫ>0 From here consider the following: lim sup Pn [F ] ≤ inf lim sup E[fǫ (Xn )] n!1 ǫ>0 n!1 (6) = inf E[fǫ (X)] (7) = P[F ] (8) ǫ>0 where (6) follows from (5) by taking the limsup and using the usual inequality lim sup inf ≤ inf lim sup, (7) is by the assumption (iii) and (8) by (4)-(5) applied to P instead of Pn . The following result shows a close relation with almost sure convergence. 6 d Theorem 2 (Skorokhod representation). Suppose that Xn → X . Then, there exists a probability space and random variables Y , Yn defined on that space with the following properties: (a) For every n, the random variables Xn and Yn have the same CDF; similarly, X and Y have the same CDF. a.s. (b) Yn → Y . For convergence in distribution, it makes no difference whether the random variables Xn are independent or not; they do not even need to be defined on the same probability space. On the other hand, almost sure convergence implies a strong form of dependence between the random variables involved. The idea in the preceding theorem is to preserve the marginal distributions, but introduce a particular form of dependence between the Xn , which then results in almost sure convergence. This dependence is introduced by generating random variables Yn and Y with the desired distributions, using a common random number generator, e.g., a single random variable U , uniformly distributed on (0, 1). Proof. Recall that if qn is the quantile function of Xn then qn (U ) ∼ Xn , where U is uniform on (0, 1). Take Yn = qn (U ) and apply Theorem 1(ii). 2.1 Convergence to subprobability measures: Helly’s theorem It frequently turns out to be convenient to extend the concept of convergence in distribution to cases when the limiting measure is not a probability measure. For example, we may say that Pn = δn converges in distribution to µ = 0, since the sequence of corresponding CDFs Fn (x) = 1[n,1) (x) converges to F0 (x) = 0 at every point of continuity. Similar to Theorem 1 we have the following equivalent representations: Proposition 2. Let Pn and µ be measures on R with CDFs Fn and F , respectively. The following are equivalent: 1. For every a, b–points of continuity of F : Fn (b) − Fn (a) → F (b) − F (a) 2. For every continuous f possessing limits at infinity f (−∞) = f (+∞) = 0: Z Z f dPn → f dµ 7 3. For every bounded Borel E with P[∂E] = 0: Pn [E] → P[E] In this case we say Pn converges to µ (weakly, or in the vague topology) and write Pn → µ. Note: In the case when µ is a probability measure the above definition coincides with convergence in distribution. Note however, that Pn → µ does not imply Fn (b) → F (b) or even that this limit exists. As an example consider 1 1 1 δn(−1)n + δ0 → δ0 2 2 2 Theorem 3 (Helly). Any (infinite) collection of probability measures on (R, B) contains a sequence converging in distribution to measure µ with µ (R) ≤ 1. Caution: Theorem does not imply that a sequence of probability measures contains a subsequence converging to a probability measure. Necessary and sufficient conditions for the latter will be discussed in the next Section. Proof. Let {rj , j = 1, . . .} be enumeration of rationals on R. Let {µs , s ∈ S} be the collection of probability measures and Fs the respective CDFs. For each rj the values taken by Fs (rj ) belong to [0, 1]. By compactness of [0, 1] it follows that for every j there is a sequence sj,n indexed by n such that Fsj,n (rj ) → F (rj ) . Furthermore, we may arrange the choice so that sj,· is a subsequence of sj−1,· etc. Then define Fn , Fsn,n (Cantor’s diagonal process). Since sn,n is a subsequence of sj,· for every j we have ∀rj ∈ Q . Fn (rj ) → F (rj ) Finally, define F  (x) = inf F (r) . r>x One easily verifies that with F is a right-continuous, non-decreasing function on R 0 ≤ F  (−∞) ≤ F (+∞) ≤ 1 . 8 Thus there is a unique measure µ on (R, B) so that µ ((a, b]) = F  (b) − F  (a) . The proof completes by showing that Fn (x) → F  (x) at every point of continuity of F  . First, notice that for every rational r we have F  (r) ≥ F (r) , lim Fn (r) . n!1 Thus for every r > x we have by monotonicity of Fn : F  (r) ≥ lim Fn (r) ≥ lim sup Fn (x) n!1 n!1 Taking limit as r ց x and using right-continuity of F  we obtain F  (x) ≥ lim sup Fn (x) ∀x ∈ R (9) n!1 Conversely, for every x1 < x and some rational r between them we have F  (x1 ) ≤ lim Fn (r) ≤ lim inf Fn (x) n!1 n!1 by monotonicity of Fn . Thus, taking the limit as x1 ր x we get: F  (x−) ≤ lim inf Fn (x) . n!1 (10) Together (9) and (10) establish convergence at the points of continuity since F  (x−) = F  (x). 2.2 Convergence to probability measures: tightness Definition 4. A collection of probability measures {Ps , s ∈ S} on (R, B) is called tight if for every ǫ there exists a compact set K = [−A, A] such that sup Ps (K c ) ≤ ǫ . s2S In words, a collection is tight if there is no “escaping of mass to infinity”, similar to the case of Pn = δn . Theorem 4 (Prokhorov’s criterion). A collection of probability measures {Ps , s ∈ S} on (R, B) is tight if and only if every sequence contains a subsequence converging to a probability measure. 9 Proof. If collection is tight, then every sequence contains a convergent subsequence by Helly’s theorem: Pn → µ . Assuming without loss of generality that µ ({n} ∪ {−n}) = 0 (otherwise just shift these slightly) and since Pn ([−n, n]c ) ≤ ǫ we have µ ([−n, n]c ) = lim Pk ([−n, n]c ) ≤ ǫ k!1 for each n and thus µ (R) = 1. Conversely, if collection is not tight, then there exist ǫ0 > 0 and measures Pn such that Pn ([−n, n]c ) ≥ ǫ0 > 0 for all n. If there is a subsequence Pnk → µ then µ (R) ≤ 1 − ǫ0 and cannot be a probability measure. 3 THE HIERARCHY OF CONVERGENCE CONCEPTS Theorem 5. We have i.p. a.s. d [Xn → X] ⇒ [Xn → X] ⇒ [Xn → X] ⇐⇒ [φXn (t) → φX (t), ∀ t]. (The first two implications assume that all random variables be defined on the same probability space.) Proof: a.s. i.p. (a) [Xn → X] ⇒ [Xn → X]: We give a short proof, based on the DCT, but more elementary proofs are also possible. Fix some ǫ > 0. Let Yn = I{|Xn −X|ǫ} . a.s. a.s. If Xn → X, then Yn → 0. By the DCT, E[Yn ] → 0. On the other hand, �
E[Yn ] = P Xn − X| ≥ ǫ . �
i.p. This implies that P |Xn − X| ≥ ǫ → 0, and therefore, Xn → X. i.p. d (b) [Xn → X] ⇒ [Xn → X]: Since the magnitude of derivative of the function a 7→ cos(ta) is bounded by t, we have that | cos(ta) − cos(tb)| ≤ t|a − b| . 10 Notice, however, that when t|a − b| > 2 this bound is not good, so overall we get: n | cos(ta) − cos(tb)| ≤ tǫ, |a − b| ≤ 2ǫ/t , 2, |a − b| > 2ǫ/t Using this with a = Xn and b = X and taking the expectation we get E[cos(tXn ) − cos(tX)] ≤ tǫP[|Xn − X| ≤ ǫ/t] + 2P[|Xn − X| > 2ǫ/t] . The second term converges to zero as n → ∞ for any t, ǫ, whereas the first term is bounded by tǫ. Thus, first taking limn!1 and then limǫ!0 we obtain E[cos(tXn )] → E[cos(tX)] for every t ∈ R. Similar proof shows E[sin(tXn )] → E[sin(tX)] . Thus, characteristic functions φXn → φX and from the last part we get the claimed result. d (c) [Xn → X] ⇒ [φXn (t) → φX (t), ∀ t]: d a.s. Suppose that Xn → X. Let Yn and Y be as in Theorem 2, so that Yn → Y . Then, for any t ∈ R, lim φXn (t) = lim φYn (t) = lim E[eitYn ] = E[eitY ] = φY (t) = φX (t), n!1 n!1 n!1 a.s. a.s. where we have made use of the facts Yn → Y , eitYn → eitY , and the DCT. Finally, the converse direction will be established in the next lecture. Exercise 1 (Smoothing method). Show that for every PX on (R, B) there exist a sed quence PXn → PX such that every PXn has continuous, bounded, infinitely-differentiable PDF. Steps: d 1. Show Xǫ = X + ǫZ → X as ǫ → 0. 2. Let X ⊥⊥ Z ∼ N (0, 1) and show that CDF of Xǫ is continuous (Hint: BCT) and differentiable (Hint: Fubini) with derivative     a−X 1 fXǫ (a) = E fZ ǫ ǫ 3. Show that a 7→ fXǫ (a) is continuous. 4. Conclude the proof (Hint: derivatives of fZ are uniformly bounded on R.) At this point, it is natural to ask whether the converses of the implications in Theorem 5 hold. For the first two, the answer is, in general, “no”, although we will also note some exceptions. 11 3.1 Convergence almost surely versus in probability i.p. a.s. [Xn → X] does not imply [Xn → X]: Let Xn be equal to 1, with probability 1/n, and equal to zero otherwise. Suppose i.p. that the Xn are independent. We have Xn → 0. On the other hand, by the BorelCantelli lemma, the event {Xn = 1, i.o} has probability 1 (check this). Thus, for almost all ω, the sequence Xn (ω) does not converge to zero. Nevertheless, a weaker form of the converse implication turns out to be true. i.p. If Xn → X, then there exists an increasing (deterministic) sequence nk of integers, such that limk!1 Xnk = X, a.s. (We omit the proof.) For an illustration of the last statement in action, consider the preceding 6 0) = 1/k 2 , counterexample. If we let nk = k 2 , then we note that P(Xnk = which is summable. By the Borel-Cantelli lemma, the event {Xnk 6= 0} will occur for only finitely many k, with probability 1. Therefore, Xnk converges, a.s., to the zero random variable. 3.2 Convergence in probability versus in distribution The converse turns out to be false in general, but true when the limit is deterministic. i.p. d [Xn → X] does not imply [Xn → X]: Let the random variables X, Xn be i.i.d. and nonconstant random variables, in d which case we have (trivially) Xn → X. Fix some ǫ. Then, P(|Xn − X| ≥ ǫ) is positive and the same for all n, which shows that Xn does not converge to X, in probability. i.p. d [Xn → c] implies [Xn → c]: The proof is very simple: by definition we have P[Xn ≤ c − ǫ] → 0 , P[Xn > c + ǫ] → 0 for any ǫ > 0. Thus P[|Xn − c| > ǫ] → 0 for any ǫ as well. 12