Probability on Metric Spaces

Advanced Stochastic Processes. LECTURE 18 Probability on metric spaces Lecture outline • Metric spaces. • Convergence of mappings. • Skorohod metric 18.1. Metric spaces and topology 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 18.1. A metric space is a pair (S, ρ) of a set and a function ρ : S × S → R+ such that for all x, y, z ∈ S the following holds: (a) ρ(x, y) > 0 if and only if x = � y. (b) ρ(x, y) = ρ(y, x). (symmetry) (c) ρ(x, z) ≤ ρ(x, y) + ρ(y, z) (triangle inequality). �� � 2 Examples of metric spaces include S = Rd with ρ(x, y) = 1≤j≤d (xj − yj ) , or = 1≤j≤d |xj − yj | or = max1≤j≤d |xj − yj |. These metrics are also called L2 , L1 and L∞ norms. Another important example is S = C[0, T ] – the space of continuous functions x : [0, T ] → Rd and ρ(x, y) = ρT = sup0≤t≤T �x(t) − y(t)�, where � · � can be taken as either of L1 , L2 , L∞ . The space � C[0, ∞) is also a metric space under ρ(x, y) = n∈N 21n ρn (x, y), where ρn is the metric defined on C[0, n]. We call ρT and ρ uniform metric. We will also write �x − y�T or �x − y� instead of ρT . Definition 18.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 � > 0 there exists n0 such that for 1 2 all n, n� > n0 , ρ(xn , xn� ) < �. A metric space is defined to be complete if every Cauchy sequence converges to some limit x. Problem 1. 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 . The space Rd is a complete space under all three metrics L. The space Q of rational points in R is not complete. 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. A metric space is defined to be separable if it contains a dense countable subset A. Rd is an example of a separable set. Problem 2. Given a set S, consider the metric ρ defined by ρ(x, x) = 0, ρ(x, y) = 1 for x �= y. Show that (S, ρ) is a metric space. Suppose S is uncountable. Show that S is not separable. Definition 18.3. A metric space S is defined to be a Polish space if it is complete and separable. Proposition 1. The space C[0, T ] is Polish. Problem 3. 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). 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 � such that B(x, �) ⊂ A. A set A is defined to be closed if Ac = S \ A is open. It is easy to check that union of open sets is open and intersection of closed sets is closed. 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 ¯ o . Examples closed sets V ⊃ A. This set is closed. For every set A define its boundary ∂A as A\A of open sets are open intervals in R and open balls Bo (x, r) = {y : �x − y� < r} ⊂ C[0, T ] (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 �x� < ∞ (this applies to any L metric). Check that every compact set is closed. Problem 4. Give an example of a closed bounded set K ⊂ C[0, T ] which is not compact. Definition 18.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 � > 0 there exists δ > 0 such that f (B(x, δ)) ⊂ B(f (x), �). A mapping f is continuous if it is continuous in every x ∈ S1 . A mapping is uniformly continuous if for every � > 0 there exists δ > 0 such that ρ1 (x, y) < δ implies ρ2 (f (x), f (y)) < �. 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 : S1 → Rd is continuous then it is also uniformly continuous. Also there exists x0 ∈ K satisfying f (x0 ) = supx∈K �f (x)�. Proof. We will skip the proof of uniform continuity and concentrate on the second part. First let us show that supx∈K f (x) < ∞. If this is not true, identify a sequence xn ∈ K such that �f (xn )� → ∞. Since K is compact, there exists a subsequence xnk which converges to some LECTURE 18. PROBABILITY ON METRIC SPACES 3 point y ∈ K. Since f is continuous then f (xnk ) → f (y), but this contradicts �f (xn )� → ∞. Thus supx∈K �f (x)� < ∞. Find a sequence xn satisfying lim �f (xn )� = supx∈K �f (x)�. Since K is compact there exists a converging subsequence xnk → x0 . Again using continuity of f we � conclude f (x0 ) = supx∈K �f (x)�. 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)|. Theorem 18.5 (Arzelá­Ascoli Theorem). A set A ⊂ C[0, T ] is compact if and only if it is closed and (18.6) sup |x(0)| < ∞, x∈A and (18.7) lim sup wx (δ) = 0. δ →0 x∈A Proof. We only show that if A is compact then (18.6) and (18.7) hold. The converse is estab­ lished using a similar type of mathematical analysis/topology arguments. The assertion (18.6) follows from Proposition 2. We now show (18.7). 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)| + 2�x − y�. Similarly we show that |x(t) − x(s)| ≤ |y(t) − y(s)| + 2�x − y�. Therefore for every δ > 0. (18.8) |wx (δ) − wy (δ)| < 2�x − y�. We now show (18.7) which is equivalent to 1 lim sup wx ( ) = 0. n x∈A n Suppose this is not the case. Then we can find a sequence xn ∈ A such that wxn (1/n) ≥ c for some c > 0. Since A is compact then �xn − x� → 0 for some x ∈ A. From (18.8) we obtain |wx (1/n) − wxn (1/n)| < 2�x − xn � < c/2 for all sufficiently large n. This implies that (18.9) wx (1/n) ≥ c/2, for all sufficiently large n. But x is continuous on [0, T ], which implies it is uniformly continuous, as [0, T ] is compact. This contradicts (18.9). � 4 18.2. Convergence of mappings 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 . Point­wise convergence does not imply uniform convergence even on compact 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 point­wise but not uniformly. 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 Proposition 3. Suppose fn is a sequence of continuous mappings which converges uniformly to f . Then f is continuous as well. Proof. Fix x ∈ S1 and � > 0. There exists n0 such that for all n > n0 , supz ρ2 (fn (z), f (z)) < �/3. Fix any such n > n0 . Since, by assumption fn is continuous, then there exists δ > 0 such that ρ2 (fn (x), fn (y)) < �/3 for all y ∈ B(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)) < 3�/3 = �. This proves continuity of f . � The similar assertion, however does not hold for point­wise convergence. 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. 18.3. Skorohod metric The space C[0, ∞) equipped with uniform metric was convenient when we discussed Brownian motion, since Brownian motion has continuous samples. Many important processes in practice, including queueing, storage, manufacturing, supply chain, etc. are not continuous, due to discrete quantities involved. As a result we need to expand the sample space. 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 ). Think about a process describing the number of customers in a branch of a bank. This process is described as a piece­wise constant function. 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 after arrival/departure. This makes the process right­continuous. It also has left­limits, 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 functions (processes). We can try to use the uniform metric LECTURE 18. PROBABILITY ON METRIC SPACES 5 again. Let us consider the following two processes x, y ∈ D[0, T ]. We are given t, t + δ ∈ [0, T ] and define x(z) = 1{z ≥ t}, y(z) = 1{z ≥ t + δ}. We see that x and y coincide everywhere except for a small interval [t, t + δ). It makes sense to assume that these processes are ”close” to each other. Yet �x − y�T = 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 version of the other, where the amount of perturbation is δ. That is, consider the following linear function λ : [0, ∞) → [0, ∞) given by λ(t) = t/(t + δ). We see that y(λ(z)) = x(z). In other words, we rescaled the axis [0, ∞) by a small amount and made y close to (in fact identical to) x. Definition 18.10. Let Λ be the space of strictly increasing continuous functions λ : [0, T ] → [0, T ]. A Skorohod metric on D[0, T ] is defined by � � ρs (x, y) = inf �λ − I� ∨ �x − yλ)� , λ∈Λ for all x, y ∈ D[0, T ], where I ∈ Λ is the identity transformation, and � · � is the uniform metric on D[0, T ]. Thus, per this definition, the distance between x and y is less than � if there exists λ ∈ Λ such that sup0≤t≤T |λ(t) − t| < � and sup0≤t≤T |x(t) − y(λ(t))| < �. It is immediate that ρs (x, x) = 0. Symmetry ρs (x, y) = ρs (y, x) follows from the fact that each λ ∈ Λ has an inverse λ−1 ∈ Λ. Thus �x − yλ� = �xλ−1 − y�. Since also �λ − I� = �λ−1 − I�, symmetry follows. We skip the proof of triangle inequality. Proposition 4. The Skorohod metric and uniform metric are equivalent on C[0, T ], in a sense that convergence xn → x holds under Skorohod metric if and only if it holds under the uniform metric. Proof. Clearly �x − y� ≥ ρs (x, y). So convergence under uniform metric implies convergence under Skorohod metric. Suppose now ρs (xn , x) → 0. We need to show �xn − x� → 0. Consider any sequence λn ∈ Λ such that �λn − I� → 0 and �x(λn ) − xn � → 0. Such a sequence exists since ρs (xn , x) → 0 (check). We have �x − xn � ≤ �x − xλn � + �xλn ) − xn �. 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 �x − xλn � → 0. 18.4. Additional reading materials • Sections 1.1­1.3 and 4.2,4.3 from notes distributed in the class. • Billingsley [1], Chapter 2, Section7 and Chapter 4, Section 12.