Lecture 1: Metric Spaces

MASSACHUSETTS INSTITUTE OF TECHNOLOGY 6.265/15.070J Lecture 1 Fall 2013 9/4/2013 Metric spaces and topology Content. Metric spaces and topology. Polish Space. Arzelá-Ascoli Theo­ rem. Convergence of mappings. Skorohod metric and Skorohod space. 1 Metric spaces. Open, closed and compact sets When we discuss probability theory of random processes, the underlying sample spaces and σ-field structures become quite complex. It helps to have a unifying framework for discussing both random variables and stochastic processes, as well as their convergence, and such a framework is provided by metric spaces. Definition 1. A metric space is a pair (S, ρ) of a set S and a function ρ : S × S → R+ such that for all x, y, z ∈ S the following holds: 1. ρ(x, y) = 0 if and only if x = y. 2. ρ(x, y) = ρ(y, x) (symmetry). 3. ρ(x, z) ≤ ρ(x, y) + ρ(y, z) (triangle inequality). Examples of metric spaces include S = Rd with ρ(x, y) = 1≤j≤d (xj − yj )2 , or = 1≤j≤d |xj − yj | or = max1≤j≤d |xj − yj |. These metrics are also called L2 , L1 and L∞ norms and we write Ix − yI1 , Ix − yI2 , Ix − yI∞ , or simply Ix−yI. More generally one can define Ix−yIp = 1. p = ∞ essentially corresponds to Ix − yI∞ . p 1≤j≤d (xj −yj ) 1 p ,p ≥ Problem 1. Show that Lp is not a metric when 0 < p < 1. Another important example is S = C[0, T ] – the space of continuous func­ tions x : [0, T ] → Rd and ρ(x, y) = ρT = sup0≤t≤T Ix(t) − y(t)I, where I · I can be taken as any of Lp or L∞ . We will usually concentrate on the case d = 1, in which case ρ(x, y) = ρT = sup0≤t≤T |x(t) − y(t)|. The space C[0, ∞) is 1 P also a metric space under ρ(x, y) = n∈N 21n min(ρn (x, y), 1), where ρn is the metric defined on C[0, n]. (Why did we have to use the min operator in the def­ inition above?). We call ρT and ρ uniform metric. We will also write Ix − yIT or Ix − yI instead of ρT . Problem 2. Establish that ρT and ρ defined above on C[0, ∞) are metrics. Prove also that if xn → x in ρ metric for xn , x ∈ C[0, ∞), then the restrictions x'n , x' of xn , x onto [0, T ] satisfy x'n → x' w.r.t. ρT . Finally, let us give an example of a metric space from a graph theory. Let G = (V, E) be an undirected graph on nodes V and edges E. Namely, each element (edge) of E is a pair of nodes (u, v), u, v ∈ V . For every two nodes u and v, which are not necessarily connected by an edge, let ρ(u, v) be the length of a shortest path connecting u with v. Then it is easy to see that ρ is a metric on the finite set V . Definition 2. A sequence xn ∈ S is said to converge to a limit x ∈ S (we write xn → x) if limn ρ(xn , x) = 0. A sequence xn ∈ S is Cauchy if for every E > 0 there exists n0 such that for all n, n' > n0 , ρ(xn , xn' ) < E. A metric space is defined to be complete if every Cauchy sequence converges to some limit x. The space Rd is a complete space under all three metrics L1 , L2 , L∞ . The space Q of rational points in R is not complete (why?). A subset A ⊂ S is called dense if for every x ∈ S there exists a sequence of points xn ∈ A such that xn → x. The set of rational values in R is dense and is countable. The set of irrational points in R is dense but not countable. The set of points (q1 , . . . , qd ) ∈ Rd such that qi is rational for all 1 ≤ i ≤ d is a countable dense subset of Rd . Definition 3. A metric space is defined to be separable if it contains a dense countable subset A. A metric space S is defined to be a Polish space if it is complete and separable. We just realized that Rd is Polish. Is there a countable dense subset of C[0, T ] of C[0, ∞), namely are these spaces Polish as well? The answer is yes, but we will get to this later. Problem 3. Given a set S, consider the metric ρ defined by ρ(x, x) = 0, ρ(x, y) = 6 y. Show that (S, ρ) is a metric space. Suppose S is uncountable. Show 1 for x = that S is not separable. Given x ∈ S and r > 0 define a ball with radius r to be B(x, r) = {y ∈ S : ρ(x, y) ≤ r}. A set A ⊂ S is defined to be open if for every x ∈ A there exists 2 E such that B(x, E) ⊂ A. A set A is defined to be closed if Ac = S \ A is open. The empty set is assumed to be open and closed by definition. It is easy to check that union of open sets is open and intersection of closed sets is closed. Also it is easy to check that a finite intersection of open sets is open and finite union of closed sets is closed. Every interval (a, b) is and every countable union of intervals ∪i≥1 (ai , bi ) is an open set. Show that a union of close intervals [ai , bi ], i ≥ 1 is not necessarily close. For every set A define its interior Ao as the union of all open sets U ⊂ A. This set is open (check). For every set A define its closure A¯ as the intersection of all closed sets V ⊃ A. This set is closed. For every set A define its boundary ∂A as A¯ \ Ao . Examples of open sets are open balls Bo (x, r) = {y ∈ S : ρ(x, y) < r} ⊂ B(x, r) (check this). A set K ⊂ S is defined to be compact if every sequence xn ∈ K contains a converging subsequence xnk → x and x ∈ K. It can be shown that K ⊂ Rd is compact if and only if K is closed and bounded (namely supx∈K IxI < ∞ (this applies to any Lp metric). Prove that every compact set is closed. Proposition 1. Given a metric space (S, ρ) a set K is compact iff every cover of K by open sets contains a finite subcover. Namely, if Ur , r ∈ R is a (possibly uncountable) family of sets such that K ⊂ ∪r Ur , then there exists a finite subset r1 , . . . , rm ∈ R such that K ⊂ ∪1≤i≤m Uri . We skip the proof of this fact, but it can be found in any book on topology. Problem 4. Give an example of a closed bounded set K ⊂ C[0, T ] which is not compact. Definition 4. Given two metric spaces (S1 , ρ1 ), (S2 , ρ2 ) a mapping f : S1 → S2 is defined to be continuous in x ∈ S1 if for every E > 0 there exists δ > 0 such that f (B(x, δ)) ⊂ B(f (x), E). Equivalently for every y such that ρ1 (x, y) < δ we must have ρ2 (f (x), f (y)) < E. And again, equivalently, if for every sequence xn ∈ S1 converging to x ∈ S it is also true that f (xn ) converges to f (x). A mapping f is defined to be continuous if it is continuous in every x ∈ S1 . A mapping is uniformly continuous if for every E > 0 there exists δ > 0 such that ρ1 (x, y) < δ implies ρ2 (f (x), f (y)) < E. Problem 5. Show that f is a continuous mapping if and only if for every open set U ⊂ S2 , f −1 (U ) is an open set in S1 . Proposition 2. Suppose K ⊂ S1 is compact. If f : K → Rd is continuous then it is also uniformly continuous. Also there exists x0 ∈ K satisfying If (x0 )I = supx∈K If (x)I, for any norm I · I = I · Ip . 3 Proof. This is where alternative property of compactness provided in Propo­ sition 1 is useful. Fix E > 0. For every x ∈ K find δ = δ(x) such that f (B(x, δ(x))) ⊂ B(f (x), E). This is possible by continuity of f . Then K ⊂ ∪x∈K Bo (x, δ(x)/2) (recall that B0 is an ”open” version of B). Namely, we have an open cover of K. By Proposition 1, there exists a finite subcover K ⊂ ∪1≤i≤k Bo (xi , δ(xi )/2). Let δ = min1≤i≤k δ(xi ). This value is positive since k is finite. Consider any two points y, z ∈ K such that ρ1 (y, z) < δ/2. We just showed that there exists i, 1 ≤ i ≤ k such that ρ1 (xi , y) ≤ δ(xi )/2. By triangle inequality ρ1 (xi , z) < δ(xi )/2 + δ/2 ≤ δ(xi ). Namely both y and z belong to Bo (xi , δ(xi )). Then f (y), f (z) ∈ Bo (f (xi ), E). By triangle inequality we have If (y) − f (z)I ≤ If (y) − f (xi )I + If (z) − f (xi )I < 2E. We conclude that for every two points y, z such that ρ1 (y, z) < δ/2 we have If (y) − f (z)I < 2E. The uniform continuity is established. Notice, that in this proof the only property of the target space Rd we used is that it is a metric space. In fact, this part of the proposition is true if Rd is replaced by any metric space S2 , ρ2 . Now let us show the existence of x0 ∈ K satisfying If (x0 )I = supx∈K If (x)I. First let us show that supx∈K If (x)I < ∞. If this is not true, identify a se­ quence xn ∈ K such that If (xn )I → ∞. Since K is compact, there ex­ ists a subsequence xnk which converges to some point y ∈ K. Since f is continuous then f (xnk ) → f (y), but this contradicts If (xn )I → ∞. Thus supx∈K If (x)I < ∞. Find a sequence xn satisfying limn If (xn )I = supx∈K If (x)I. Since K is compact there exists a converging subsequence xnk → x0 . Again us­ ing continuity of f we have f (xnk ) → f (x0 ). But If (xnk )I → supx∈K If (x)I. We conclude f (x0 ) = supx∈K If (x)I. We mentioned that the sets in Rd which are compact are exactly bounded closed sets. What about C[0, T ]? We will need a characterization of compact sets in this space later when we analyze tightness properties and construction of a Brownian motion. Given x ∈ C[0, T ] and δ > 0, define wx (δ) = sups,t:|s−t|<δ |x(t) − x(s)|. The quantity wx (δ) is called modulus of continuity. Since [0, T ] is compact, then by Proposition 2 every x ∈ C[0, T ] is uniformly continuous on [0, T ]. This may be restated as for E > 0, there exists δ > 0 such that wx (δ) < E. Theorem 1 (Arzel´a-Ascoli Theorem). A set A ⊂ C[0, T ] is compact if and 4 only if it is closed and sup |x(0)| < ∞, (1) x∈A and lim sup wx (δ) = 0. δ→0 x∈A (2) Proof. We only show that if A is compact then (1) and (2) hold. The converse is established using a similar type of mathematical analysis/topology arguments. We already know that if A is compact it needs to be closed. The assertion (1) follows from Proposition 2. We now show (2). For any s, t ∈ [0, T ] we have |y(t) − y(s)| ≤ |y(t) − x(t)| + |x(t) − x(s)| + |x(s) − y(s)| ≤ |x(t) − x(s)| + 2Ix − yI. Similarly we show that |x(t) − x(s)| ≤ |y(t) − y(s)| + 2Ix − yI. Therefore for every δ > 0. |wx (δ) − wy (δ)| < 2Ix − yI. (3) We now show (2). Check that (2) is equivalent to 1 lim sup wx ( ) = 0. n x∈A n (4) Suppose A is compact but (4) does not hold. Then we can find a subsequence xni ∈ A, i ≥ 1 such that wxni (1/ni ) ≥ c for some c > 0. Since A is compact then there is further subsequence of xni which converges to some x ∈ A. To ease the notation we denote this subsequence again by xni . Thus Ixni −xI → 0. From (3) we obtain |wx (1/ni ) − wxni (1/ni )| < 2Ix − xni I < c/2 for all i larger than some i0 . This implies that wx (1/ni ) ≥ c/2, (5) for all sufficiently large i. But x is continuous on [0, T ], which implies it is uniformly continuous, as [0, T ] is compact. This contradicts (5). 5 2 Convergence of mappings Given two metric spaces (S1 , ρ1 ), (S2 , ρ2 ) a sequence of mappings fn : S1 → S2 is defined to be point-wise converging to f : S1 → S2 if for every x ∈ S1 we have ρ2 (fn (x), f (x)) → 0. A sequence fn is defined to converge to f uniformly if lim sup ρ2 (fn (x), f (x)) = 0. n x∈S1 Also given K ⊂ S1 , sequence fn is said to converge to f uniformly on K if the restriction of fn , f onto K gives a uniform convergence. A sequence fn is said to converge to f uniformly on compact sets u.o.c if fn converges uniformly to f on every compact set K ⊂ S1 . Problem 6. Let S1 = [0, ∞) and let S2 be arbitrary. Show that fn converges to f uniformly on compact sets if and only if for every T > 0 lim sup ρ2 (fn (t), f (t)) = 0. n 0≤t≤T Point-wise convergence does not imply uniform convergence even on com­ pact sets. Consider xn = nx for x ∈ [0, 1/n], = n(2/n − x) for x ∈ [1/n, 2/n] and = 0 for x ∈ [2/n, 1]. Then xn converges to zero function point-wise but not uniformly. Moreover, if fn is continuous and fn converges to f point-wise, this does not imply in general that f is continuous. Indeed, let fn = 1/(nx + 1), x ∈ [0, 1]. Then fn converges to 0 point-wise everywhere except x = 0 where it converges to 1. The limiting function is discontinuous. However, the uniform continuity implies continuity of the limit, as we are about to show. Proposition 3. Suppose fn : S1 → S2 is a sequence of continuous mappings which converges uniformly to f . Then f is continuous as well. Proof. Fix x ∈ S1 and E > 0. There exists n0 such that for all n > n0 , supz ρ2 (fn (z), f (z)) < E/3. Fix any such n > n0 . Since, by assumption fn is continuous, then there exists δ > 0 such that ρ2 (fn (x), fn (y)) < E/3 for all y ∈ Bo (x, δ). Then for any such y we have ρ2 (f (x), f (y)) ≤ ρ2 (f (x), fn (x)) + ρ2 (fn (x), fn (y)) + ρ2 (fn (y), f (x)) < 3E/3 = E. This proves continuity of f . Theorem 2. The spaces C[0, T ], C[0, ∞) are Polish. 6 Problem 7. Use Proposition 3 (or anything else useful) to prove that C[0, T ] is complete. That C[0, T ] has a dense countable subset can be shown via approximations by polynomials with rational coefficients (we skip the details). 3 Skorohod space and Skorohod metric The space C[0, ∞) equipped with uniform metric will be convenient when we discuss Brownian motion and its application later on in the course, since Brown­ ian motion has continuous samples. Many important processes in practice, how­ ever, including queueing processes, storage, manufacturing, supply chain, etc. are not continuous, due to discrete quantities involved. As a result we need to deal with probability concept on spaces of not necessarily continuous functions. Denote by D[0, ∞) the space of all functions x on [0, ∞) taking values in R or in general any metric space (S, ρ), such that x is right-continuous and has left limits. Namely, for every t0 , limt↑t0 f (t), limt↓t0 f (t) exist, and limt↓t0 f (t) = f (t0 ). As an example, think about a process describing the number of customers in a branch of a bank. This process is described as a piece-wise constant func­ tion. We adopt a convention that at a moment when a customer arrives/departs, the number of customers is identified with the number of customers right af­ ter arrival/departure. This makes the process right-continuous. It also has leftlimits, since it is piece-wise constant. Similarly, define D[0, T ] to be the space of right-continuous functions on [0, T ] with left limits. We will right shortly RCLL. On D[0, T ] and D[0, ∞) we would like to define a metric which measures some proximity between the func­ tions (processes). We can try to use the uniform metric again. Let us consider the following two processes x, y ∈ D[0, T ]. Fix τ, ∈ [0, T ) and δ > 0 such that τ + δ < T and define x(z) = 1{z ≥ τ }, y(z) = 1{z ≥ τ + δ}. We see that x and y coincide everywhere except for a small interval [τ, τ + δ). It makes sense to assume that these processes are ”close” to each other. Yet Ix − yIT = 1. Thus uniform metric is inadequate. For this reason Skorohod introduce the so called Skorohod metric. Before we define Skorohod metric let us discuss the idea behind it. The problem with uniform metric was that the two processes x, y described above where close to each other in a sense that one is a perturbed ver­ sion of the other, where the amount of perturbation is δ. In particular, consider the following piece-wise linear function λ : [0, T ] → [0, T ] given by λ(t) = τ τ +δ t, τ+ 1−τ 1−τ −δ (t t ∈ [0, τ + δ]; − τ − δ), t ∈ [τ + δ, T ]. 7 We see that x(λ(t)) = y(t). In other words, we rescaled the axis [0, T ] by a small amount and made y close to (in fact identical to) x. This motivates the following definition. From here on we use the following notations: x ∧ y stands for min(x, y) and x ∨ y stands for max(x, y) Definition 5. Let Λ be the space of strictly increasing continuous functions λ from [0, T ] onto [0, T ]. A Skorohod metric on D[0, T ] is defined by   ρs (x, y) = inf Iλ − II ∨ Ix − yλ)I , λ∈Λ for all x, y ∈ D[0, T ], where I ∈ Λ is the identity transformation, and I · I is the uniform metric on D[0, T ]. Thus, per this definition, the distance between x and y is less than E if there exists λ ∈ Λ such that sup0≤t≤T |λ(t)−t| < E and sup0≤t≤T |x(t)−y(λ(t))| < E. Problem 8. Establish that ρs is a metric on D[0, T ]. Proposition 4. The Skorohod metric and uniform metric are equivalent on C[0, T ], in a sense that for xn , x ∈ C[0, T ], the convergence xn → x holds under Sko­ rohod metric if and only if it holds under the uniform metric. Proof. Clearly Ix − yI ≥ ρs (x, y). So convergence under uniform metric im­ plies convergence under Skorohod metric. Suppose now ρs (xn , x) → 0. We need to show Ixn − xI → 0. Consider any sequence λn ∈ Λ such that Iλn −II → 0 and Ix(λn )−xn I → 0. Such a sequence exists since ρs (xn , x) → 0 (check). We have Ix − xn I ≤ Ix − xλn I + Ixλn − xn I. The second summand in the right-hand side converges to zero by the choice of λn . Also since λn converges to I uniformly, and x is continuous on [0, T ] and therefore uniformly continuous on [0, T ], then Ix − xλn I → 0. 4 Additional reading materials • Billingsley [1], Appendix M1-M10. References [1] P. Billingsley, Convergence of probability measures, Wiley-Interscience publication, 1999. 8