Probability Basics - Probability Space, σ-algebras, Probability Measur

Advanced Stochastic Processes. LECTURE 1 Probability basics: probability space, σ-algebras, probability measure, and other scary stuff ... Outline of Lecture • • • • General remarks on probability theory and stochastic processes Sample space Ω. Discrete sample space and discrete probability space. Continuous sample space. σ-algebra and probability measure. 1.1. General Remarks Probability theory is devoted to studying random observations which typically take some values in �, or vectors in �d , or integers Z, but typically these observations are values. Examples: the number of college graduates next year; average temperature on September 8; stock price of IBM tomorrow at 11am. These observation take values (have a sample space) N, � and �+ = [0, ∞), respectively. The theory of stochastic processes is devoted to studying random (stochastic) observations which are processes described mathematically as functions. Examples: the number of college graduates as a function of the year between 2005 and 2010; temperature on September 8 as a function of the time of the day; IBM stock price as a function of the day of the year. These random observations are functions: f : [2005, 2010] → N, f : [0, 24] → �, f : [0, 365] → �+ , respectively. The focus of this class is random (stochastic) processes. The random processes naturally lead as well to random observations when focusing on some features of the process. These random observations (random variables) are described mathematically as functionals of random processes. 1 2 Examples: • the maximum number of college graduates between 2005 and 2010: max2005≤n≤2010 f (n); • first time when temperature exceeded 70: �inf{t ∈ [0, 24] : f (t) ≥ 70}; 1 f (x)dx. • average IBM stock price over the year: 365 0≤x≤365 In order to discuss random values and random processes we need to build an abstract formulation of a probability space which would allow us to speak both about random values and processes. 1.2. Sample Space Remark. The materials of this and the following lecture overlap significantly with the course Fundamentals of Probability 6.975. The probability space is defined as a triplet (Ω, F, P) consisting of the sample space Ω, σ-algebra F and probability measure P. We discuss these concepts in detail in the following sections. Sample space Ω is the set of elementary events describing ”what can happen”. Its elements are denoted by ω ∈ Ω and are defined to be elementary outcomes. The sample space can be finite Ω = {ω1 , . . . , ωN }, countable Ω = {ω1 , ω2 , . . . , ωN , . . .} or uncountable (for example �). An important sample space for this class (when we study Brownian motion) is C([a, b]) – the set of all continuous functions f : [a, b] → �. Examples. (a) The sample space for rolling a dice once: Ω = {1, 2, . . . , 6}, n times: Ω = {1, 2, . . . , 6}n , infinitely many times: Ω = {1, 2, . . . , 6}∞ . First two are finite, last is uncountable. Corresponding examples of elementary outcomes: ω = 3, ω = (1, 3, 3 . . . , 5), ω = (1, 1, 3, 1, 5, . . . , 2, . . .). � �� � n (b) The sample space for observing a stock value at a particular time: Ω = �+ . (c) The sample space for observing temperature as a function of the time of the day is Ω = C([0, 24]). The sample space for observing stock as a function of the year is Ω = C([0, 365]). Remark. The sample space for processes needs not be continuous. For example, suppose for simplicity stock are traded every business day for 7 hours between 9am and 4pm. Then the stock price on Monday and Tuesday can be described as a set of functions f : [0, 14] → �+ which are continuous everywhere except at t = 7 (end of trading on Monday). Note: there is no discussion of probabilities yet. Ω simply describes the space of possible events. 1.3. Discrete Probability Space Probability space (Ω, F, P) is easiest to define when Ω is finite or countable. LECTURE 1. PROBABILITY BASICS 3 Definition 1.1. A discrete probability space is a triplet (Ω, F, P) such that (a) The sample space Ω is finite or countable Ω = {ω1 , ω2 , . . .}; (b) F is the set of all subsets of Ω. � (c) P is a function P : Ω → [0, 1] such that ω∈Ω P[ω] = 1. � For every subset A ∈ F we define P[A] = ω∈A P[ω]. There is no need to describe F since it is the set of all subsets. Thus, we may simply write (Ω, P). Examples. (a) n unbiased coin tosses. Ω = {0, 1}n . P[ω] = 1/2n . Suppose A = {ω = (ω1 , . . . , ωn ) : ω1 = 1, ωn = 0}. Then P[A] = � ω:ω1 =1,ωn =0 P[ω] = 2n−2 1 1 = . 2n 4 (b) Geometric random variable. A parameter 0 < ρ < 1 is fixed. Ω = Z+ . For every ω ∈ Ω, P[ω] = (1 − ρ)ρω . (c) Poisson random variable. A parameter λ > 0 is fixed. Ω = Z+ . For every ω ∈ Ω, P[ω] = λω −λ e . ω! 1.4. σ-algebras When Ω is not countable it is not clear how to assign probabilities to elementary events. For example, we want to capture the intuition that a randomly chosen point from [0, 1] has a probability 1/4 of falling into � [1/2, 3/4]. If we assign P[ω] to be a positive value c > 0 then we have a problem: the total sum ω P[w] = ∞. If we assign P[ω] = 0, how do we get P[1/2, 3/4] = 1/4? The solution is to assign probabilities to sets A ⊂ [0, 1] of elementary outcomes, instead of individual outcomes ω ∈ [0, 1]. For every A ⊂ Ω Ac denotes the complement set: {ω ∈ Ω : ω ∈ / A}. A collection of sets A1 , A2 , . . . ⊂ Ω is called mutually exclusive if Ai ∩ Aj = ∅ whenever i �= j. Definition 1.2. A σ-field F is a collection of subsets of Ω satisfying the following conditions: (a) Ω ∈ F (b) If A ∈ F then Ac ∈ F . (c) If a sequence A1 , A2 , . . . ∈ F then ∪i Ai ∈ F . Any set A ∈ F is called measurable or F-measurable. σ-field replaces the set of all subsets A ⊂ Ω when Ω is no longer countable. Exercise 1. Given a σ-field F. Prove that if A, B ∈ F then A ∩ B ∈ F. In general, given an infinite sequence A1 , A2 , . . . , ∈ F prove that ∩i Ai ∈ F . 4 Check that the following are indeed σ- fields. Example : (a) Trivial σ-field F = {∅, Ω}. (b) Set A ⊂ F is fixed. F = {∅, A, Ac , Ω}. (c) The set of all subsets of the sample space: F = {A ⊂ Ω} = 2Ω . (d) Ω = {1, 2, . . . , 6}n – rolling a dice n times. Let A = {ω = (ω1 , . . . ωn ) : ω1 ≤ 2}, B = {ω = (ω1 , . . . , ωn ) : 3 ≤ ω1 ≤ 4}, C = {ω = (ω1 , . . . , ωn ) : ω1 ≥ 4}. Then F = {∅, A, B, C, A ∪ B, A ∪ C, B ∪ C, Ω} is a σ-field. Proposition 1. Let Fs , s ∈ S be some set of σ-fields defined on the same sample space Ω. (Note that the index set S needs not be finite or countable). Define F = ∩s Fs . That is a subset A ∈ F if and only if A ∈ Fs for every σ-field Fs . Then F is also a σ-field. Proof. Note that F is nonempty since Ω ∈ ∩s Fs . If A ∈ F then A ∈ Fs for every s. Since Fs is a σ-field, then Ac ∈ Fs for every s. Therefore Ac ∈ F . Similarly we show that if Ai ∈ F , i = 1, 2, . . . � then ∩i≥1 Ai ∈ F. Thus F is a σ-field. What is an appropriate σ-field corresponding to the set of all intervals [a, b] ⊂ [0, 1]? What about earlier examples of random processes: temperature during the day f : [0, 24] → � or stock during the year f : [0, 365] → �+ ? Describing these σ-fields explicitly is not easy, so we resort to the tool of generated σ-field. Given a collection B of subsets of Ω (which is not necessarily a σ-field) there is always at least one σ-field which contains it: simply take the set of all subsets of Ω. It is certainly a σ-field. Denote, by F(B) the smallest σ-field containing B. It is obtained by taking intersection ∩s Fs of all σ-fields Fs which contain B : Fs ⊃ B . We say that F(B) is generated by B. 1.5. Three important σ-fields 1.5.1. Borel σ-field on [0, 1] Definition 1.3. Borel σ-field on Ω = [0, 1] is defined to be the σ-field generated by the set of all closed intervals [a, b] ⊂ [0, 1]. It is denoted by B. Properties of the Borel field B • Every interval [a, b] ∈ B by definition. • Every interval [0, a) is the complement set of [a, 1] and therefore belongs to B. Similarly, (a, 1] ∈ B . • Every interval (a, b) = [0, b) ∩ (a, 1] ∈ B (use Exercise 1). • Every point {a} = [0, a] ∩ [a, 1] ∈ B (again use Exercise 1). • Every union of open or closed intervals (a1 , b1 ) ∪ [a2 , b2 ) ∪ · · · ∪ [an , bn ) ∈ B . Exercise 2. Let Q[0, 1] be the set of all rational values r ∈ [0, 1]. Prove that Q[0, 1] ∈ B. Is the Borel σ-field the same as the set of all subsets of [0, 1]? The answer is ”no”. There exists H ∗ ⊂ [0, 1] which does not belong to B, but constructing this set is a very non-trivial task. A convenient rule of thumb is: any easily describable subset of [0, 1] is measurable! LECTURE 1. PROBABILITY BASICS 5 Borel σ-field can be similarly defined on the whole real line � instead of [0, 1] as the σ-field generated by the set of all intervals [a, b] ⊂ (−∞, ∞); or in Euclidian space �d , as σ-field generated by rectangles [a1 , b1 ] × · · · × [ad , bd ]. 1.5.2. σ-field on {0, 1}∞ Set Ω = {0, 1}∞ . Given a sequence ω1 , . . . , ωm ∈ {0, 1} denote by Am (ω) the set of all infinite sequences ω ∈ Ω which agree with ω1 , . . . , ωm on first m coordinates. For example say m = 4 and ω1 = ω2 = ω3 = ω4 = 0. Then A4 (ω) is the set of all sequences starting with four zeros. Definition 1.4. The σ-field F∞ generated by all sets A(ω) when m and ω1 , . . . , ωm vary arbi­ trarily is defined to be the product σ-field on Ω = {0, 1}∞ . The sets A(ω) are called cylinder sets. Similar product type σ-fields can be defined on �∞ or in general on any infinite product Ω of a given sample space Ω equipped with some σ-field F. The product σ-field F∞ is the σ-field generated by cylinder sets which are all sets of the form A1 × A2 × · · · × Am × Ω∞ , where A1 , A2 , . . . , Am are arbitrary sets from F. Namely, cylinder sets are sets of infinite sequences (ω1 , ω2 , . . . , ωm , . . .) where the first element must belong to A1 , the second element to A2 , and so on, the m-th element to Am , but the remaining elements are unrestricted. For example when Ω = R∞ we can take as cylinder sets the sets of the form [a1 , b1 ] × [a2 , b2 ] × · · · × [am , bm ] × R∞ . ∞ The product σ-field allows us to speak about discrete time processes where index m corresponds to event occurring at time m. Describing explicitly product σ-field (that is without alluding to ”generating”) is not possible, but we can describe some useful special cases. In general, just as in the case of Ω = [0, 1], the rule of thumb is: most of the imaginable subsets of Ω∞ belong to F∞ . Proposition 2. Let Ω = {0, 1}∞ and F∞ be the corresponding product σ-field. The following sets belong to F∞ . (a) Fix any element ω = (ω1 , ω2 , . . .) ∈ Ω. Then {ω} ∈ F∞ . (b) Fix any m. Then {ω ∈ Ω : ωk = 0, for all k ≥ m} ∈ F∞ .P ωi (c) Fix any value 0 ≤ c ≤ 1. Then A(c) = {ω ∈ Ω : limn→∞ 1≤i≤n = c} ∈ F∞ . n (a) Given a fixed ω = (ω1 , ω2 , . . .), consider the sequence of sets Am = {ω � : ω1� = � ω1 , . . . , ωm = ω} ⊂ Ω. By definition Am ∈ F∞ as it is a cylinder set. Applying the result of Exercise 1, ∩m Am ∈ F∞ . But ∩m Am consists of exactly one point which is {ω}. (b) Fix any infinite sequence ω = (ω1 , ω2 , . . .) such that all of the entries ωk = 0 for k ≥ m. By the result of part (a), {ω} ∈ F∞ . But the set of interest, {ω ∈ Ω : ωk = 0, for all k ≥ m} is obtained as a union of exactly 2m such sequences. By rule (c) of Definition 1.2, this set belongs to F∞ . (c) This is a more difficult, but very important part of the proposition. For every pair r, m ∈ N define 1 � 1 Ar,m = {ω ∈ {0, 1}∞ : | ωi − c| ≤ }. m 1≤i≤m r Proof. Exercise 3. Prove that Ar,m ∈ F∞ . 6 Then for every m, Br,m � ∩m� ≥m Ar,m� ∈ F∞ . Therefore Cr � ∪m≥1 Br,m ∈ F∞ . We claim that A(c) = ∩r≥1 Cr . Exercise 4. Prove this identity. Therefore A(c) is F∞ -measurable. � 1.5.3. σ-field C[0, ∞) The sample space Ω = C[0, ∞) of real valued continuous functions will be an important space when we discuss Brownian motion. In order to introduce the σ-field of interest on C[0, ∞) we first introduce a notation. For every T > 0, ρ > 0 and for every element x ∈ C[0, ∞) define B(x, ρ, T ) = {y ∈ C[0, ∞) : sup |x(t) − y(t)| ≤ ρ}. 0≤t≤T Definition 1.5. The Borel σ-field on the sample space C[0, ∞) (denoted B) is the σ-field gen­ erated by all the sets B(x, ρ, T ), where x ∈ C[0, ∞), ρ, T ∈ R+ vary arbitrarily. We now give some examples of the sets in the Borel σ-field. Proposition 3. The following sets belong to B: (a) The set of all non-negative functions {x : x(t) ≥ 0, for all t ≥ 0} (b) {x : limt→∞ x(t) = ∞}. (c) {x : x(t) ≤ t, for all t}. As before, most of the imaginable susbsets of C[0, ∞) belong to the Borel σ-field, but not all of them. (we do not construct a counterexample). Proof. (a) For every positive integer n let gn (t) = n for all t. Fix any positive integer m and consider the union B(m) � ∪n B(gn , n, m). This is the set of all functions f which take value between 0 and 2n for all 0 ≤ t ≤ m for some n (see Figure). We have B(m) ∈ B. By one of the fundamental theorems of mathematical analysis, every continuous function defined on [0, m] achieves a maximum at some point t ∈ [0, m], and, in particular, is bounded. Thus B(m) is simply the set of all continuous functions which are non-negative on [0, m]. Now we take ∩m≥1 B(m) and note that it belongs to B and is the set of all non-negative functions. (b) Exercise 5. Prove the last two parts. � 1.6. Probability measure We finally get to the point of discussing probabilities and random observations. We already described how to define a probability space when Ω is countable. There we assigned probability values to individual elements ω ∈ Ω. As we discussed before, this does not work when Ω is uncountable. The solution is to assign probabilities to events A ⊂ Ω, specifically elements A of some σ-field F, and require that it satisfies certain ”natural” properties we expect to hold for probabilities. LECTURE 1. PROBABILITY BASICS 7 Definition 1.6. A probability space is a triplet (Ω, F, P) consisting of a sample space Ω, a σ-field F defined on Ω and a probability function (usually called probability measure) P : F → [0, 1] satisfying the following properties: (a) P(Ω) = 1. � (b) For every infinite sequence A1 , A2 , . . . ∈ F, there holds P(∪i Ai ) ≤ i P(Ai ). (c) � For every mutually exclusive infinite sequence A1 , A2 , . . . ∈ F there holds P(∪i Ai ) = i P(Ai ). The elements A ∈ F are called the events, and P(A) is called the probability of the event A. The definition intuitively means the following. The probability of ”anything that is possible to happen” is P(ω ∈ Ω) = P(Ω) is unity. If we have several events A1 , A2 , . . . then probability that ”any of them happen” is at most the sum of probabilities of individual events. The inequality is used instead of equality because of the possibility of overlap. For example the probability that the temperature today is at most 70o or temperature at 1pm is 60o is at most the sum of probabilities of these individual events, since both can happen. But if the events are mutually exclusive, then the equality holds. Say A is ”maximum temperature is at most 70o ” and B is ”smallest temperature is at least 75o ”. Both events cannot happen: A ∩ B = ∅. Thus P(A ∪ B) = P(A) + P(B). An event A ∈ F is said to happen almost surely if P(A) = 1. Here are several important implications. Proposition 4. (a) For every two events A, B ∈ F, there holds P(A ∩ B) = P(A) + P(B) − P(A ∪ B). (b) Suppose A1 ⊂ A2 ⊂ A3 ⊂ · · · . Then P(∪Ai ) = limi→∞ P(Ai ). Proof. (a) The sets A \ B, B \ A, A ∩ B are mutually exclusive and their union is A ∪ B. Therefore P(A ∪ B) = P(A \ B) + P(B \ A) + P(A ∩ B) = P(A \ B) + P(A ∩ B) + P(B \ A) + P(A ∩ B) − P(A ∩ B) But P(A \ B) + P(A ∩ B) = P(A) and P(B \ A) + P(A ∩ B) = P(B). Therefore P(A ∪ B) = P(A) + P(B) − P(A ∩ B). (b) Set, for convenience A0 = ∅. The events � A1 \ A0 , A2 \ A1 , A3 \ A2 , . . . , are mutually exclusive. Therefore P(∪i (Ai \ Ai−1 )) = i P(Ai \ Ai−1 ). But note that ∪i (Ai \ Ai−1 ) = ∪i Ai . Also � � P(Ai \ Ai−1 ) = lim P(Ai \ Ai−1 ). i n→∞ i≤n � But since again Ai \ Ai−1 are mutually exclusive, then i≤n P(Ai \ Ai−1 ) = P(∪i≤n (Ai \ Ai−1 )). Finally, we observe that ∪i≤n (Ai \ Ai−1 ) = An . Therefore limn P(An ) = P(∪i Ai ). This concludes the proof. � This completes the description of a probability space (Ω, F, P). Every discussion of probability models has some underlying probability space. The tool of probability distribution, which is primarily considered in elementary probability courses, allows one to by-pass these more abstract 8 concepts. However when we discuss stochastic processes in spaces like {0, 1}∞ or C[0, ∞) these concepts are indispensable. 1.7. Reading assignments • Notes distributed in the class. • Durrett [1] • Grimmett and Stirzaker [2], Chapter 1.