Advanced Stochastic Processes. LECTURE 2 Random variables and measurable functions. Strong Law of Large Numbers (SLLN). Scary stuﬀ continued ... Outline of Lecture • Random variables and measurable functions. • Extension Theorem. Borel-Cantelli Lemma and SLLN 1.1. Random variables and measurable functions Deﬁnition 1.1. Given two pairs (Ω1 , F1 ), (Ω2 , F2 ) of a sample space and a σ-ﬁeld, a function X : Ω1 → Ω2 is deﬁned to be measurable if for every A ∈ F2 we must have X −1 (A) ∈ F1 . When Ω2 is the set of all reals R and F2 is the Borel σ-ﬁeld, the function X is called a random variable. This deﬁnition naturally extends to the case when Ω2 = �d . In this case we call X a random vector. Also since the set of integers is a subset of R, the deﬁnition of a random variable includes the case of integer valued random variables. Exercise 1. Suppose a function X : Ω → R is such that X −1 (−∞, x) ∈ F for every real value x. Prove that X is a measurable function. Note, that we do not have to have a probability measure P on Ω1 or Ω2 in order to deﬁne mea surable functions. But probability measure is needed when we discuss probability distributions below. Examples. (a) It is easy to give an example of a function which is not measurable. Suppose, for example Ω1 = Ω2 and both consist of exactly 3 elements ω1 , ω2 , ω3 . Say F1 is a trivial σ-ﬁeld (which consists of only ∅ and Ω) and F2 is a full σ-ﬁeld consisting of all 8 subsets of Ω. Then the identical transformation X : ω → ω is not measurable: take any non-empty 1 2 set A ⊂ Ω, A = � Ω. We have A is measurable with respect to F2 , but X −1 (A) = A is not measurable with respect to F1 . (b) (Figure.) Say Ω = [0, 1]2 and X : Ω → R is deﬁned by X(ω) = ω1 + ω2 . We claim that X is a random variable when Ω is equipped with Borel σ-ﬁeld. Here is the proof. For every real value x consider the set A = {ω = (ω1 , ω2 ) : ω1 + ω2 > x}. We will prove that A is measurable (belongs to the Borel σ-ﬁeld of [0, 1]2 ). Then we will take a complement of A and this will prove that X is random variable. Consider the countable set of pairs of rationals (r1 , r2 ) such that r1 + r2 > x. For each of them ﬁnd n = n(r1 , r2 ) the smallest integer which is large enough so that the recangle B(r1 , r2 ; 1/n) = {(ω1 , ω2 ) ∈ [0, 1]2 : |ω1 − r1 | ≤ 1 1 , |ω2 − r2 | ≤ } n n lies entirely in A (this is possible by strict inequality r1 + r2 > x). Observe that every pair (ω1 , ω2 ) satisfying ω1 + ω2 > x lies in one of these rectangles. Thus A is the union ∪r1 ,r2 B(r1 , r2 , n(r11,r2 ) ) of the countable collection of such rectangles and therefore belongs to the Borel σ-ﬁeld of [0, 1]2 . � (c) Say Ω = C[0, ∞) equipped with the Borel σ-ﬁeld, and X : Ω → R is the function which maps every continuous function f (t) into max0≤t≤1 |f (t)|. Then X is a random variable on Ω. Indeed, for every x, we have X −1 (x) is the set of all functions f such that max0≤t≤1 |f (t)| ≤ x. But this is exactly the set B(0, x, 1) used in Deﬁnition 1.5 of Lecture 1. The sets of this type generate the Borel σ-ﬁeld, and in particular, belong to it. Thus X is measurable. The concept of random variables naturally leads to the concept of probability distribution Deﬁnition 1.2. (Figure.) Given a probability space (Ω, F, P) and a random variables X : Ω → R, the associated probability distribution is deﬁned to be the function F : R → [0, 1] given by F (x) = P({ω ∈ Ω : X(ω) ≤ x}). When F (x) is a diﬀerentiable function of x, its derivative f (x) = Ḟ (x) is called the density function. In other words F (x) is the probability given to the set of all elementary outcomes ω which are mapped by X into value at most x. It is the probability distributions which are usually discussed in elementary probability classes. There, one usually deﬁnes probability distribution as a function satisfying certain properties (like it should be non-decreasing and should converge to unity as x → ∞). Here these properties can be derived from the given deﬁnition of a probability distribution. Proposition 1. Prove that F (x) is non-decreasing, non-negative and limx→−∞ F (x) = 0, limx→∞ F (x) = 1. � The concept of probability distributions allows one to perform the probability related calculations without alluding to more abstract notions of probability measures. This is not possible, however, when we discuss probability spaces like C[0, ∞). LECTURE 2. PROBABILITY BASICS CONTINUED 3 Having deﬁned random variables and associated probability distributions, we can deﬁne further expected values, moments, moment generating functions, etc., in a more formal way then is done in elementary probability classes. We do this only heuristically, highlighting the main ideas. Deﬁnition 1.3. A random variable X : Ω → R is called simple if it takes only ﬁnitely many values x1 , x2 , . . . , xm . The expected value of a simple random variable X is deﬁned to be the quantity � xi P{ω ∈ Ω : X(ω) = xi }. E[X] = 1≤i≤m What if X is not simple? How do we deﬁne its expected value? The idea is to approximate X by a sequence of simple random variables. For simplicity assume that X takes only values in the interval [0, A] for some A > 0. That is X : Ω → [0, A]. Now consider Xn (ω) = nk if X(ω) ∈ ( k−1 , nk ]. Then Xn is a simple random variable. It can be shown that the sequence of n the corresponding expected values E[X � n ] converges. Its limit is called the expected value E[X] of X. It is also sometimes written as X(ω)dP(ω). This deﬁnition of expected value satisﬁes all the properties of expected values one studies in elementary probability courses, for example the fact E[X 2 ] ≥ (E[X])2 , Markov inequality, Chebyshev inequality, Jensen’s inequality, etc. 1.2. What’s i.i.d. sequence of random variables? Now we can give a formal deﬁnition of a stochastic process – the principle notion for this course. Deﬁnition 1.4. Let T be the set of all non-negative reals R+ or integers Z+ . A stochastic process {Xt }t∈T is a family of random variables Xt : Ω → R parametrized by T . Remark. Note that a sample outcome ω corresponding to a stochastic process is a function X(ω) : T → R, and the sample space of the corresponding stochastic process is the space of functions from T into R. But often we consider restrictions. For example, when T = [0, ∞) we might consider only continuous functions from [0, ∞) into R: Example. Set Ω = C[0, ∞) equipped with Borel σ-ﬁeld. Deﬁne Xt (ω) = ω(t) for every sample ω ∈ C[0, ∞). Then {Xt }t∈[0,∞) is a stochastic process. This is true because each function Xt : C[0, ∞) → R is a random variable. (we will prove this later in the course). Remark. The deﬁnition naturally extends to the case when observations are functions T → Rd into d-dimensional Euclidian space. One of the simplest (to analyze, but not to deﬁne) examples of a stochastic process is an i.i.d. (independent, identically distributed) stochastic process. What is an i.i.d. stochastic process? In probability courses it was common to say X1 , X2 , . . . , is an i.i.d. sequence of Bernoulli random variables with parameter 0 < p < 1, or Z1 , Z2 , . . . is an i.i.d. sequence of Normal (Gaussian) random variables with expected value µ and variance σ 2 . What do we mean by this? How does it ﬁt with (Ω, F, P)? We are almost equipped to answer this question, but need little more technicalities. Probability space deﬁnition includes deﬁning a function P : F → [0, 1]. How can we deﬁne this function on the entire σ-ﬁeld, when we cannot sometimes even describe the σ-ﬁeld explicitly? The help comes from Extension Theorem ET. A rough idea is that if the σ-ﬁeld is generated by 4 some collection of sets A and we can deﬁne P on A only, the there is a unique extension of the function P onto entire σ-ﬁeld, provided some restrictions are satisﬁed. 1.2.1. Extension Theorem Theorem 1.5 ( Extension Theorem). Given a sample space Ω and a collection A of subsets of Ω such that for every A ∈ A its complement Ω \ A is also in Ω and for every ﬁnite sequence A1 , . . . , Am its union ∪1≤j≤m Aj is also in A. Suppose P : A → [0, 1] is such that (a) P(Ω) = 1, �∞ ∞ (b) P(∪∞ j=1 Aj ) ≤ �j=1 P(Aj ), whenever ∪j=1 Aj ∈ A. ∞ ∞ (c) P(∪∞ j=1 Aj ) = j=1 P(Aj ), whenever ∪j=1 Aj ∈ A and Ai , i = 1, 2, . . . are mutually exclusive. Then the function P uniquely extends to a probability measure P : F(A) → [0, 1] deﬁned on the σ-ﬁeld generated by A. Remark. Note, that the requirement from A is to be a collection of sets with properties very similar to that of a σ-ﬁeld. The only diﬀerence is that we do not require every inﬁnite union of sets to be in A as well. 1.2.2. Examples and applications Uniform probability measure. Consider Ω = [0, 1] and let A be the set of ﬁnite unions of open or closed non-intersecting intervals: [a1 , b1 ) ∪ [a2 , b2 ] ∪ · · · ∪ (am , bm ). It is easy to check that A satisﬁes the conditions of the � ET. Consider the function P : A → [0, 1] which maps every such set of intervals to the value 1≤i≤m bi − ai (that is the total length of these intervals). It can be checked that this also satisﬁes the conditions of the ET (we skip the proof). Thus, by ET, there exists a unique extension of function P to a probability measure on entire Borel σ-ﬁeld, since this σ-ﬁeld is generated by intervals. This probability measure is called uniform probability measure on [0, 1]. Other types of continuous distributions. What about other distributions like Normal, Exponential, etc.? The proper deﬁnition of these probability measures is introduced similarly. For example the standard Normal distribution is deﬁned as probability space (R, B, P), where �b t2 B is the Borel σ-ﬁeld on R and P assigns to each interval [a, b] value a √12π e− 2 dt. Then each non-intersecting collection of intervals [ai , bi ], 1 ≤ i ≤ m is assigned value which is the sum of the corresponding integrals. Again the set of ﬁnite collections of non-intersecting intervals satisﬁes the conditions of ET, and applying ET we obtained that the probability measure P is deﬁned on the entire Borel σ-ﬁeld B. 1.2.3. i.i.d. sequences i.i.d coin tosses . Let Ω = {0, 1}∞ . Recall that the product σ-ﬁeld is the ﬁeld generated by cylinder type sets A(ω). Let A be the set of ﬁnite unions of such sets ∪1≤j≤k A(ωj ). Again, it can be checked that that A satisﬁes the conditions of ET. For every ﬁnite sequence ω = ω1 , . . . , ωm and the corresponding set A(ω) we set P(A(ω)) simply to be 21m (the probability of a particular sequence of 0/1 observations in the ﬁrst m coin tosses is 21m ). For example, the probability of ﬁrst four zeros is 214 . Then, for every union of non-intersecting sets ∪1≤j≤k A(ωj ) we set their LECTURE 2. PROBABILITY BASICS CONTINUED 5 corresponding value to 2km . The conditions of ET again can be checked, but we skip the proof. Then, by ET there is a unique extension of P to the entire product σ-ﬁeld of Ω. This is what we call a sequence of i.i.d. unbiased coin tosses also known as a sequence of i.i.d. Bernoulli random variables with parameter 1/2. The phrase i.i.d., in proper probabilistic terms, means (Ω, F, P) – the probability space constructed above. General i.i.d. type distributions. We have deﬁned formally i.i.d. Bernoulli sequence. What about general i.i.d. sequences? They are deﬁned similarly by considering inﬁnite products and cylinder type sets. First we set Ω = R∞ . On it we consider the product σ-ﬁeld F∞ . Deﬁne A to be the set of ﬁnite unions of cylinder type sets. Recall that a cylinder set A is the set of the form A = [a1 , b1 ] × (a2 , b2 ) × · · · × [am , bm ) × R∞ – product of closed or open or half-closed half open intervals. Recall also that cylinder sets generate, by deﬁnition, the product σ-ﬁeld F∞ . Suppose we have a probability space (R, B, P) deﬁned on R and its Borel σ-ﬁeld B (for exam ple P corresponds to standard Normal distribution). Then for every cylinder set A we deﬁne � P(A) = 1≤j≤m P([aj , bj ]). Again we check that A and P satisfy the conditions of ET (we skip the proof). Thus there is a unique extension of P to the entire product σ-ﬁeld F∞ of R∞ , since A generates this σ-ﬁeld. Then we deﬁne Xm (ω) = ωm for every ω ∈ R∞ . We note that Xm is a random variable as it is a measurable function from R∞ into R. The sequence X1 , X2 , . . . is a stochastic process which we call an i.i.d. sequence of random variables. Essentially we have ”embedded” a sequence of random variables {Xm } into a single probability space (R∞ , F∞ , P). Is this deﬁnition consistent with elementary deﬁnition of�i.i.d. Recall that elementary deﬁnition of i.i.d. sequence is when P(X1 ≤ x1 , . . . , Xm ≤ xm ) = 1≤j≤m P(Xj ≤ xj ). Is this true in our case? Note P(X1 ≤ x1 , . . . , Xn ≤ xm ) = P{ω ∈ R∞ : ω1 ∈ (−∞, x1 ], . . . , ωm ∈ (−∞, xm ]} = P{ω ∈ (−∞, x1 ] × · · · × (−∞, xm ] × R∞ } � = P((−∞, xj ]), 1≤j≤m where the last equality � follows from how we deﬁned P on cylinder sets. But the product of these probabilities is exactly 1≤j≤n P(Xj ≤ xj ). Thus the identity checks. 1.3. Borel-Cantelli Lemma and Strong Law of Large Numbers (SLLN) The Strong Law of Large Numbers (SLLN) (like the Central Limit Theorem) is one of the most fundamental theorems in probability theory. Yet properly stating it, let alone proving it is not as straightforward as is, for example the Weak Law of Large Numbers (WLLN). We now use the (Ω, F, P) framework to properly state and prove SLLN. We begin with a very useful tool, the Borel-Cantelli Lemma. Given a sample space Ω, a σ-ﬁeld F and an inﬁnite sequence A1 , A2 , . . . , Am , . . . ∈ F deﬁne Ai.o. (i.o. stands for inﬁnitely often) to be the set of all ω ∈ Ω which belong to inﬁnitely many Am -s. One can write Ai.o. as (check 6 the validity of this identity) Ai.o. = ∩m≥1 ∪j≥m Aj . Lemma 1.6 (Borel-Cantelli Lemma). � Given a probability space (Ω, F, P) and an inﬁnite sequence of events Am , m ≥ 1 suppose m P(Am ) < ∞. Then P(Ai.o. ) = 0. In words we say: the probability that Am happen inﬁnitely often is equal to zero. Proof. Deﬁne Bm = ∪j≥m Aj . Then Ai.o. = ∩m Bm . Then B1 ⊃ B2 ⊃ B3 ⊃ · · · . Using P(Ai.o. ) = limm P(Bm ). But since Proposition 4 part (b) (applied to complement sets) we obtain � � P(A ) < ∞ then the tail parts of the sum satisfy lim m m m j≥m P(Aj ) = 0. But P(Bm ) = � P(∪j≥m Aj ) ≤ j≥m P(Aj ). Therefore, moreover limm Bm = 0. We conclude P(Ai.o. ) = 0. � Theorem 1.7 (SLLN). Consider an i.i.d sequence of random variables Xn , n = 1, 2, . . . corre sponding to some probability measure (R, B, P). Suppose E[X1 ] < ∞. Then almost surely � 1≤i≤n Xi lim = E[X1 ]. n→∞ n Formally, deﬁne � 1≤i≤n Xi (ω) ∞ A = {ω ∈ R : lim = E[X1 ]}. n→∞ n Then P(A) = 1. Proof. The proof of this fundamental result in probability theory is complicated (see for example [2]). Here, for simplicity, we consider a special case when the random variable X1 has a ﬁnite fourth moment. Namely, � 4 E[|X1 | ] = |X1 (ω)|4 dP(ω) < ∞. Let us center the random variables Xi in the following way: Yi = Xi − E[Xi ]. Then Yi have zero expected value. Since � � Y i 1≤i≤n 1≤i≤n Xi = − E[Xi ], n n P it suﬃces to prove that P An (�) as | 1≤i≤n Yi | n 1≤i≤n Yi n converges almost surely to zero. Fix � > 0 and deﬁne the event > �. Formally � ∞ An (�) = {ω ∈ R Applying Markov inequality P(| � 1≤i≤n n Yi :| 1≤i≤n Yi (ω) n � | > �) = P(( ≤ E[( 1≤i≤n � n 1≤i≤n n4 �4 Yi | > �}. )4 > �4 ) Yi )4 ] � When we expand E[( 1≤i≤n Yi )4 ] we note that only the terms of the form E[Yi4 ] and E[Yi2 Yj2 ] are non-zero, since the expected value of Yi is zero and the sequence is i.i.d. Also by independence LECTURE 2. PROBABILITY BASICS CONTINUED 7 E[Yi2 Yj2 ] = (E[Y12 ])2 . We obtain a bound nE[Y14 ] + n(n − 1)(E[Y12 ])2 n2 [E[Y14 ] + (E[Y12 ])2 ] E[Y14 ] + (E[Y12 ])2 ≤ = n4 �4 n4 �4 n2 �4 This expression is ﬁnite by our assumption of ﬁniteness of fourth moment. Since the sum � E[Y14 ]+(E[Y12 ])2 < ∞, then applying the Borel-Cantelli Lemma we conclude that probabil n≥1 n2 �4 ∞ ity that An (�) happens for inﬁnitely many n is zero. In other words, P for almost every ω ∈ R Yi (ω) there exists n0 = n0 (�, ω) such that for all n > n0 we must have | 1≤i≤nn | ≤ �. This means that for almost every ω, we have � 1≤i≤n Yi (ω) lim = 0. n→∞ n This concludes the proof. � � 1.4. Reading assignments • Notes ”Modeling experiments”, pages 1.4,1.5,2.2. • Grimmett and Stirzaker [2], Chapters 1 and 2. Chapter 7, Sections 7.3-7.5 . • Durrett [1] Chapter 1, Sections 1-7.