Random Variables and Measurable Functions; Strong Law of Large Numbers

Advanced Stochastic Processes. LECTURE 2 Random variables and measurable functions. Strong Law of Large Numbers (SLLN). Scary stuff continued ... Outline of Lecture • Random variables and measurable functions. • Extension Theorem. Borel-Cantelli Lemma and SLLN 1.1. Random variables and measurable functions Definition 1.1. Given two pairs (Ω1 , F1 ), (Ω2 , F2 ) of a sample space and a σ-field, a function X : Ω1 → Ω2 is defined 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 σ-field, the function X is called a random variable. This definition 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 definition 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 define 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 σ-field (which consists of only ∅ and Ω) and F2 is a full σ-field 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 defined by X(ω) = ω1 + ω2 . We claim that X is a random variable when Ω is equipped with Borel σ-field. 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 σ-field 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 find 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 σ-field of [0, 1]2 . � (c) Say Ω = C[0, ∞) equipped with the Borel σ-field, 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 Definition 1.5 of Lecture 1. The sets of this type generate the Borel σ-field, and in particular, belong to it. Thus X is measurable. The concept of random variables naturally leads to the concept of probability distribution Definition 1.2. (Figure.) Given a probability space (Ω, F, P) and a random variables X : Ω → R, the associated probability distribution is defined to be the function F : R → [0, 1] given by F (x) = P({ω ∈ Ω : X(ω) ≤ x}). When F (x) is a differentiable function of x, its derivative f (x) = Ḟ (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 defines 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 definition 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 defined random variables and associated probability distributions, we can define 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. Definition 1.3. A random variable X : Ω → R is called simple if it takes only finitely many values x1 , x2 , . . . , xm . The expected value of a simple random variable X is defined to be the quantity � xi P{ω ∈ Ω : X(ω) = xi }. E[X] = 1≤i≤m What if X is not simple? How do we define 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 definition of expected value satisfies 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 definition of a stochastic process – the principle notion for this course. Definition 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 σ-field. Define 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 definition 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 define) 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 fit with (Ω, F, P)? We are almost equipped to answer this question, but need little more technicalities. Probability space definition includes defining a function P : F → [0, 1]. How can we define this function on the entire σ-field, when we cannot sometimes even describe the σ-field explicitly? The help comes from Extension Theorem ET. A rough idea is that if the σ-field is generated by 4 some collection of sets A and we can define P on A only, the there is a unique extension of the function P onto entire σ-field, provided some restrictions are satisfied. 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 finite 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] defined on the σ-field 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 σ-field. The only difference is that we do not require every infinite 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 finite unions of open or closed non-intersecting intervals: [a1 , b1 ) ∪ [a2 , b2 ] ∪ · · · ∪ (am , bm ). It is easy to check that A satisfies 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 satisfies 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 σ-field, since this σ-field 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 definition of these probability measures is introduced similarly. For example the standard Normal distribution is defined as probability space (R, B, P), where �b t2 B is the Borel σ-field 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 finite collections of non-intersecting intervals satisfies the conditions of ET, and applying ET we obtained that the probability measure P is defined on the entire Borel σ-field B. 1.2.3. i.i.d. sequences i.i.d coin tosses . Let Ω = {0, 1}∞ . Recall that the product σ-field is the field generated by cylinder type sets A(ω). Let A be the set of finite unions of such sets ∪1≤j≤k A(ωj ). Again, it can be checked that that A satisfies the conditions of ET. For every finite 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 first m coin tosses is 21m ). For example, the probability of first 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 σ-field 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 defined formally i.i.d. Bernoulli sequence. What about general i.i.d. sequences? They are defined similarly by considering infinite products and cylinder type sets. First we set Ω = R∞ . On it we consider the product σ-field F∞ . Define A to be the set of finite 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 definition, the product σ-field F∞ . Suppose we have a probability space (R, B, P) defined on R and its Borel σ-field B (for exam­ ple P corresponds to standard Normal distribution). Then for every cylinder set A we define � 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 σ-field F∞ of R∞ , since A generates this σ-field. Then we define 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 definition consistent with elementary definition of�i.i.d. Recall that elementary definition 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 defined 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 σ-field F and an infinite sequence A1 , A2 , . . . , Am , . . . ∈ F define Ai.o. (i.o. stands for infinitely often) to be the set of all ω ∈ Ω which belong to infinitely 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 infinite sequence of events Am , m ≥ 1 suppose m P(Am ) < ∞. Then P(Ai.o. ) = 0. In words we say: the probability that Am happen infinitely often is equal to zero. Proof. Define 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, define � 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 finite 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 suffices to prove that P An (�) as | 1≤i≤n Yi | n 1≤i≤n Yi n converges almost surely to zero. Fix � > 0 and define 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 finite by our assumption of finiteness 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 infinitely 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.