Two Fundamental Probabalistic Models

MASSACHUSETTS INSTITUTE OF TECHNOLOGY 6.436J/15.085J Lecture 2 TWO FUNDAMENTAL PROBABILISTIC MODELS Contents 1. Extending measures from algebras to σ-algebras (Carathéodory) 2. Coin tosses: a “uniform” measure on {0, 1}∞ 3. Lebesgue measure on [0, 1] and R 4. Completion of a probability space 5. Further remarks 6. Appendix: strange sets The following are two fundamental probabilistic models that can serve as building blocks for more complex models: (a) A model of an infinite sequence of fair coin tosses that assigns equal probability, 1/2n , to every possible sequence of length n. (b) The uniform distribution on [0, 1], which assigns probability b − a to every interval [a, b] ⊂ [0, 1]. These two models are often encountered in elementary probability and used without further discussion. Strictly speaking, however, we need to make sure that these two models are well-posed, that is, consistent with the axioms of probability. To this effect, we need to define appropriate σ-algebras and probability measures on the corresponding sample spaces. In what follows, we describe the required construction, while omitting the proofs of the more technical steps. 1 EXTENDING MEASURES FROM ALGEBRAS TO σ-ALGEBRAS The general outline of the construction we will use is as follows. We are interested in defining a probability measure with certain properties on a given 1 measurable space (Ω, F). We consider a smaller collection, F0 ⊂ F, of subsets of Ω , which is an algebra, and on which the desired probabilities are easy to define.1 Furthermore, we make sure that F0 is rich enough, so that the σalgebra it generates is the same as the desired σ-algebra F. We then extend the definition of the probability measure from F0 to the entire σ-algebra F. This is possible, under a few conditions, by virtue of the following fundamental result from measure theory due to Carethéodory. We begin by asking the following question: Is probability measure on a σ-algebra F = σ(C) completely determined by its values on the generating collection C? The answer is no as the next exercise demonstrates. Exercise 1. Let Ω = {H, T }2 (two coin tosses). Consider two probability measures: under P1 two fair coins are tossed independently,  while under P2 the second coin toss is just taken to be equal to the first. Let C = {HH, HT }, {HH, T H}} . Show that σ(C) = 2 Ω and that P1 = P2 on C. However, it turns out that probability measures coinciding on an algebra of sets must necessarily coincide on the σ-algebra generated by it. Proposition 1. Let A be an algebra of subsets of Ω and λ, µ probability measures on F = σ(A). If λ and µ agree on A then they agree on all of F. Proof. Define L = {A ∈ F : µ(A) = λ(A)}. Take a sequence of sets An ∈ L with An ր A. By Theorem 1 from Lecture 1 (continuity of σ-additive measures) we have µ(A) = λ(A) and hence A ∈ L. Same argument applies to decreasing sequences An ց A. Therefore L is a monotone class, containing the algebra A. By the monotone class theorem (Theorem 2 from Lecture 1) L = σ(A). Remark. One frequently constructs σ-algebras from p-systems. A collection of subsets C is called a p-system if it is closed under finite intersections. In the next lecture we will show that measures coinciding on a p-system also coincide on the algebra generated by it. By virtue of Proposition 1 they will then also coincide on the σ-algebra generated by the p-system. In short: it is sufficient to verify agreement of measures on any generating p-system. Remark. Proposition remains true if we replace probability measures with finite or even σ-finite measures (A measure µ is called σ-finite if the set Ω can be partitioned into a countable union of sets, each of which has finite measure.). 1 An algebra (or a field) is a collection of subsets of the sample space that includes the empty set closed under taking complements and under finite unions. 2 “Wilder” measures, however, Sn may violate the proposition: E.g. consider an algebra of finite unions i=1 (ai , bi ] on (0, 1]. The σ-algebra generated by this algebra is the Borel one on (0, 1]. Let λ(A) and µ(A) be equal to cardinality and twice the cardinality of A, respectively. The on the algebra of finite unions they coincide (giving infinite measure to any non-empty set), while being clearly different. Theorem 1. (Carath´eodory’s extension theorem) Let F0 be an algebra of subsets of a sample space Ω , and let F = σ(F0 ) be the σ -algebra that it generates. Suppose that P0 is a mapping from F0 to [0, 1] that satisfies P0 (Ω) = 1, as well as countable additivity on F0 . Then, P0 can be extended uniquely to a probability measure on (Ω, F). That is, there exists a unique probability measure P on (Ω, F) such that P(A) = P0 (A) for all A ∈ F0 . Remarks: (a) The proof of the extension theorem is not too long; see, e.g., Appendix A of [Williams]. The key steps are: • Define a σ-subadditive set-function λ∗ : 2 → [0, 1] (called an outer measure)   ∞ X [  P(Aj ) : Aj ∈ F, E ⊂ λ∗ (E) , inf Aj .   j=1 j • Define a collection of sets F̄ , {E : λ∗ (F ) = λ∗ (F ∩ E) + λ∗ (F ∩ E c ) ∀F ⊂ Ω }. • Show that F¯ is a σ-algebra containing F0 and that λ∗ is a probability measure on it, which coincides with P on F0 . Then restrict from F̄ to F. (b) Although the extension theorem is a powerful result, the key step in constructing probability measures is verification of the countable additivity property of P0 on F0 . By Theorem 1 from Lecture 1, it suffices to verify that if {Ai } is a decreasing sequence of sets in F0 and if ∩∞ i=1 Ai is empty, then limn→∞ P0 (Ai ) = 0. We will soon see how such a verification is done. In the next two sections, we consider the two models of interest. We define appropriate algebras, define probabilities for the events in those algebras, and then use the extension theorem to obtain a probability measure. 3 2 COIN TOSSES: A “UNIFORM” MEASURE ON {0, 1}∞ Consider an infinite sequence of fair coin tosses. We wish to construct a probabilistic model of this experiment under which every possible sequence of results of the first n tosses has the same probability, 1/2n . The sample space for this experiment is the set {0, 1}∞ of all infinite sequences ω = (ω1 , ω2 , . . .) of zeroes and ones (we use zeroes and ones instead of heads and tails). First, we want to argue that it is not possible to define a good “uniform” measure on the collection of all subsets 2 . This will justify the whole idea of introducing the concept of a σ-algebra. Let us try to understand what exactly we mean by “uniform”. Fix an infinite string b ∈ {0, 1}∞ . Let us introduce the modulo-2 addition (XOR) as: ω ⊕ b = (ω1 + b1 , . . . , ωn + bn , . . .)mod2 , and similarly for sets A ⊕ b = {ω ⊕ b : ω ∈ A} . Informally, a realization of coin tosses is in the set A ⊕ b iff it is in A after we invert every coordinate j for which bj = 1. It is natural to require that our measure be such that P[A ⊕ b] = P[A] . (1) (In mathematical terms, we want P to be translation invariant.) Let us show that it is not possible to define a σ-additive P on all of 2 so that (1) holds. Indeed, suppose such a P existed. Then define an equivalence relation on Ω : ω ∼ ω ′ if these binary sequences disagree in at most finitely many places. Let A be a set of representatives, one for each equivalence class; and let B be the equivalence class of the 0-sequence. It is clear that [ Ω = ω ⊕ A. ω∈B On the other hand since B is countable and the sets in the union are disjoint: X X 1 = P[ ] = P[ω ⊕ A] = P[A], ω∈B ω∈B which is impossible for any choice of P[A]. In conclusion, we showed that “uniform” (in the sense of (1)) probability measure on Ω must necessarily be defined on a σ-algebra that may not include Ω A and hence be strictly smaller than 2 . We construct such a σ-algebra next. 4 2.1 An algebra and a σ-algebra of subsets of {0, 1}n Let Fn be the collection of events whose occurrence can be decided by looking 6 at the results of the first n tosses. For example, the event {ω | ω1 = 1 and ω2 = ω4 } belongs to F4 (as well as to Fk for every k ≥ 4). Let B be an arbitrary (possibly empty) subset of {0, 1}n . Consider the set A = {ω ∈ {0, 1}∞ | (ω1 , ω2 , . . . , ωn ) ∈ B}. We can express A ⊂ {0, 1}∞ in the form A = B × {0, 1}∞ . This is simply saying that any sequence in A can be viewed as a pair consisting of a n-long sequence that belongs to B, followed by an arbitrary infinite sequence. The event A belongs to Fn , and all elements of Fn are of this form, for some A. It is easily verified that Fn is a σ-algebra. Exercise 2. Provide a formal proof that Fn is a σ -algebra. The σ-algebra Fn , for any fixed n, is too small; it can only serve to model the first n coin tosses. We are interested instead in sets that belong to Fn , for arbitrary n, and this leads us to our main definition: F0 = ∞ [ Fn = {A : ω ∈ A ⇐⇒ (ω1 , . . . , ωn ) ∈ B, n ≥ 0, B ∈ {0, 1}n } , n=1 ? i.e. F0 is the collection of all those sets A for which membership ω ∈ A can be determined on the basis of inspecting only finitely many coordinates (ω1 , . . . , ωn ) for some n ≥ 0. 2 Example. Let An = {ω | ωn = 1}, the event that the nth toss results in a “1”. Note that An ∈ Fn . Let A = ∪1 i=1 An , which is the event that there is at least one “1” in the infinite toss sequence. The event A does not belong to Fn , for any n. (Intuitively, having observed a sequence of n zeroes does not allow us to decide whether there will be a subsequent “1” or not.) Consider also the complement of A, which is the event that the outcome of the experiment is an infinite string of zeroes. Once more, we see that Ac does not belong to F0 . The preceding example shows that F0 is not a σ-algebra. On the other hand, it can be verified that F0 is an algebra. Exercise 3. Prove that F0 is an algebra. 2 Warning: the union [1 i=1 Fi = F0 is not the same as the collection of sets of the form A , for A 2 F . For an illustration, if F1 = {{a}, {b, c}} and F2 = {{d}}, then F1 [ [1 i i i i=1 F2 = {{a}, {b, c}, {d}}. Note that {b, c} [ {d} = {b, c, d} is not in F1 [ F2 . 5 We would like to have a probability model that assigns probabilities to all of the events in Fn , for every n. This means that we need a σ-algebra that includes F0 . On the other hand, we would like our σ-algebra to be as small as possible, i.e., contain as few subsets of {0, 1}n as possible, to minimize the possibility that it includes pathological sets to which probabilities cannot be assigned. This leads us to define F as the sigma-algebra σ(F0 ) generated by F0 . 2.2 � A probability measure on {0, 1}∞ , F) We start by defining a finitely additive function P0 on the algebra F0 that also satisfies P0 ({0, 1}∞ ) = 1. This is accomplished as follows. Every set A in F0 is of the form B × {0, 1}∞ , for some n and some B ⊂ {0, 1}n . We then let P0 (A) = |B|/2n .3 Note that the event {ω1 , ω2 , . . . , ωn } × {0, 1}n , which is the event that the first n tosses resulted in a particular sequence {ω1 , ω2 , . . . , ωn }, is assigned probability 1/2n . In particular, all possible sequences of length are assigned equal probability, as desired. Before proceeding further, we need to verify that the above definition is consistent. Note that same set A can belong to Fn for several values of n. We therefore need to check that when we apply the definition of P0 (A) for different choices of n, we obtain the same value. Indeed, suppose that A ∈ Fm , which implies that A ∈ Fn , for n > m. In this case, A = B ×{0, 1}∞ = C ×{0, 1}∞ , where B ⊂ {0, 1}n and C ⊂ {0, 1}m . Thus, B = C × {0, 1}n−m , and |B| = |C| · 2n−m . One application of the definition yields P0 (A) = |B|/2n , and another yields P0 (A) = |C|/2m . Since |B| = |C| · 2n−m , they both yield the same value. It is easily verified that P0 (Ω) = 1, and that P0 is finitely additive: if A1 , A2 ⊂ Fn are disjoint, then P(A1 ∪ A2 ) = P(A1 ) + P(A2 ). It turns out that P0 is also countably additive on F0 . Lemma 1. P0 is σ-additive on F0 Proof. According to Theorem 1 of Lecture 1 it is sufficient to show that An ց Ø ⇒ P(An ) → 0. In fact, we will show that An ց Ø 3 ⇒ ∃N ≥ 1 ∀n ≥ N : An = Ø . For any set A, |A| denotes its cardinality, the number of elements it contains. 6 (2) Let us call a b ∈ {0, 1}m a “great prefix” if there exists infinitely many n ≥ 1 with the property that An contains some ω with ωi = bi for all i = 1, . . . , m. Note that AN = Ø for some N ≥ 1 is equivalent to stating that b = Ø (zerolength prefix) is not great. So assume, to arrive at a contradiction, that b = Ø is great. Notice that if b is a great prefix than either b0 or b1 (juxtaposition) must be great too. Indeed, we can split the infinitely many An ’s which contain ω with b as prefix in two groups depending on whether ωm+1 equals zero or one. One of these groups must be infinite. In other words, any great prefix can be extended by one more digit. In this way by induction we can construct an infinite sequence b = (b1 , . . . , bn , . . .) with the property that any initial segment if it is a great prefix. Now we show that b ∈ Am for any m. Indeed, by definition of F0 there must exist n such that Am ∈ Fn . Consider prefix (b1 , . . . , bn ). It is great by construction and thus there must exist ω ∈ Aℓ such that ωi = bi for all i ≥ ℓ. In fact there are infinitely many such ℓ’s and so in particular there is an ℓ ≥ m. Hence, from Aℓ ⊂ Am we conclude ω ∈ Am . But now recall that Am ∈ Fn and since ω and b share the initial n values, we must also have b ∈ Am . In all, we have shown b ∈ Am for all m and thus ∩Am 6= Ø contradicting the assumption. (Here is a “fancy” proof for analysts: The space {0, 1}∞ is compact in the product topology (Tikhonov’s theorem) and thus An is a decreasing sequence of compacts.) We can now invoke the Extension Theorem and conclude that there exists a unique probability measure on F, the σ-algebra generated by F0 , that agrees with P0 on F0 . This probability measure assigns equal probability, 1/2n , to every possible sequence of length n, as desired. This confirms that the intuitive process of an infinite sequence of coin flips can be captured rigorously within the framework of probability theory. Exercise 4. Consider the probability space ({0, 1}1 , F , P). Let A be the set of all infinite sequences ω for which ωn = 0 for every odd n. (a) Establish that A ∈ / F0 , but A ∈ F . (b) Compute P(A). Exercise 5. Show that P is translation invariant (1) for all ω and A ∈ F . (Hint: the monotone class theorem may be helpful.) 3 LEBESGUE MEASURE ON [0, 1] AND ON R In this section, we construct the uniform probability measure on [0, 1], also known as Lebesgue measure. Under the Lebesgue measure, the measure as7 signed to any subset of [0, 1] is meant to be equal to its length. While the definition of length is immediate for simple sets (e.g., the set [a, b] has length b − a), more general sets present more of a challenge. We start by considering the sample space Ω = (0, 1], which is slightly more convenient than the sample space [0, 1], though in the end it will result in essentially the same probability space. Similarly to the case of coin-tosses, a translation-invariant probability measure defined on all subsets of does not exists, see Section 6. Thus, our first goal is to define a proper σ-algebra. 3.1 A σ-algebra and an algebra of subsets of (0, 1] Consider the collection C of all intervals [a, b] contained in (0, 1], and let F be the σ-algebra generated by C. As mentioned in the Lecture 1 notes, this is called the Borel σ-algebra, and is denoted by B. Sets in this σ-algebra are called Borel sets or Borel measurable sets. Any set that can be formed by starting with intervals [a, b] and using a countable number of set-theoretic operations (taking complements, or forming countable unions and intersections of previously formed sets) is a Borel set. For example, it can be verified that single-element sets, {a}, are Borel sets. Furthermore, intervals (a, b] are also Borel sets since they are of the form [a, b] \ {a}. Every countable set is also a Borel set, since it is the union of countably many singleelement sets. In particular, the set of rational numbers in (0, 1], as well as its complement, the set of irrational numbers in (0, 1], is a Borel set. While Borel sets can be fairly complicated, not every set is a Borel set; see Sections 5-6. As usual, directly defining a probability measure for all Borel sets is difficult, so we start by considering a smaller collection, F0 , of subsets of (0, 1]. We let F0 consist of the empty set and all sets that are finite unions of intervals of the form (a, b]. In more detail, if a set A ∈ F0 is nonempty, it is of the form A = (a1 , b1 ] ∪ · · · ∪ (an , bn ], where 0 ≤ a1 < b1 ≤ a2 < b2 ≤ · · · ≤ an < bn ≤ 1 and n ∈ N. Lemma 1. We have σ(F0 ) = σ(C) = B . Proof. We have already argued that every interval of the form (a, b] is a Borel set. Hence, a typical element of F0 (a finite union of such intervals) is also a Borel set. Therefore, F0 ⊂ B, which implies that σ(F0 ) ⊂ σ(B) = B. (The last equality holds because B is already a σ-algebra and is therefore equal to the smallest σ-algebra that contains B.) 8 Consider 0 < a < b ≤ 1 and take a sequence of rationals an ր a and bn ց b. Then [a, b] = ∩∞ n=1 (an , bn ] Since (an , bn ] ∈ F0 it follows that [a, b] ∈ σ(F0 ). Thus, C ⊂ σ(F0 ), which implies that �
B = σ(C) ⊂ σ σ(F0 ) = σ(F0 ) ⊂ B. (The second equality holds because the smallest σ-algebra containing σ(F0 ) is σ(F0 ) itself.) The first equality in the statement of the proposition follows. Finally, the equality σ(C) = B is just the definition of B. Lemma 2. (a) The collection F0 is an algebra. (b) The collection F0 is not a σ -algebra. Proof. (a) By definition, Ø ∈ F0 . Note that Øc = (0, 1] ∈ F0 . More generally, if A is of the form A = (a1 , b1 ]∪· · ·∪(an , bn ], its complement is (0, a1 ]∪(b1 , a2 ]∪ · · · ∪ (bn , 1], which is also in F0 . Furthermore, the union of two sets that are unions of finitely many intervals of the form (a, b] is also a union of finitely many such intervals. For example, if A = (1/8, 2/8] ∪ (4/8, 7/8] and B = (3/8, 5/8], then A ∪ B = (1/8, 2/8] ∪ (3/8, 7/8]. (b) To see that F0 is not a σ-algebra, note that (0, 1 − 2−n ] ∈ F0 , for every n ∈ N, but the union of these sets, which is (0, 1), does not belong to F0 . 3.2 The uniform measure on (0, 1] For every A ∈ F0 of the form A = (a1 , b1 ] ∪ · · · ∪ (an , bn ], we define P0 (A) = (b1 − a1 ) + · · · + (bn − an ), �
which is its total length. Note that P0 ( ) = P (0, 1] = 1. Also P0 is finitely additive. Indeed if A1 , . . . , An are disjoint finite unions of intervals of the form (a, b], then A = ∪1≤i≤n Ai is also a finite union of such intervals and its total length is the sum of the lengths of the sets Ai . 9 Lemma 2. P0 is σ-additive on F0 Proof. (Optional) First notice the following: For A ∈ F0 and any ǫ > 0 there exists a closed subset C ⊂ A such that A=C ∪E, where E ∈ F0 and P0 (E) ≤ ǫ. For the basic interval (a, b] this follows by writing (a, b] = [a − ǫ, b] ∪ (a, a − ǫ] and for other sets in F0 similarly. Next consider An ց Ø with An ∈ F0 . Fix arbitrary ǫ0 > 0 and let ǫn = −n ǫ0 2 . Select decompositions as above An = Cn ∪ En , P0 (En ) ≤ ǫn . T Sets Cn are not necessarily nested, so define Fn = nk=1 Ck and notice that An \ Fn ⊆ n [ Ek , (3) k=1 which is shown by induction. Suppose that all Fn are non-empty and select in each Fn an arbitrary element xn . Note that xn ∈ Fm for all m ≤ n. By compactness of F1 the sequence xn must contain a subsequence xni converging to some point x∗ . By the preceding observation for every fixed m and all sufficiently large i we have xni ∈ Fm , and thus x∗ ∈ Fm for all m. This contradicts the fact that ∩Fm = Ø. We conclude that there must exist some N such that FN = Ø. Consequently, from (3) we get that AN ⊆ N [ Ek k=1 implying by the union bound that P0 (AN ) ≤ N X P0 (Ek ) = ǫ0 k=1 N X k=1 Thus, for any ǫ0 > 0 we have lim P0 (An ) ≤ ǫ0 n→∞ 10 2−k ≤ ǫ0 implying the limit is actually zero. We can now apply the Extension Theorem and conclude that there exists a probability measure P, called the Lebesgue or uniform measure, defined � on
the entire Borel σ-algebra B, that agrees with P0 on F0 . In particular, P (a, b] = b − a, for every interval (a, b] ⊂ (0, 1]. By augmenting the sample space to include 0, and assigning zero probability to it, we obtain a new probability model with sample space = [0, 1]. (Exercise: define formally the sigma-algebra on [0, 1], starting from the σalgebra on (0, 1].) Exercise 6. Let A be the set of irrational numbers in [0, 1]. Show that P(A) = 1. Example. Let A be the set of points in [0, 1] whose decimal representation contains only odd digits. (We disallow decimal representations that end with an infinite string of nines. Under this condition, every number has a unique decimal representation.) What is the Lebesgue measure of this set? Observe that A = ∩1 n=1 An , where An is the set of points whose first n digits are odd. It can be checked that An is a disjoint union of 5n intervals, each with length 1/10n. Thus, P(An ) = 5n /10n = 1/2n. Since A ⊂ An , we obtain P(A) ≤ P(An ) = 1/2n . Since this is true for every n, we conclude that P(A) = 0. Exercise 7. Let A be the set of points in [0, 1] whose decimal representation contains at least one digit equal to 9. Find the Lebesgue measure of that set. Note that there is nothing special about the interval (0, 1]. For example, �
if we let Ω = (c, d], where c < d, and if (a, b] ⊂ (c, d], we can define P0 (a, b] = (b − a)/(d − c) and proceed as above to obtain a uniform probability measure on the set (c, d], as well as on the set [c, d]. On the other hand, a “uniform” probability measure on the entire real line, R, that assigns equal probability to intervals of equal length, is incompatible with the requirement P(Ω) = 1. What we obtain instead, in the next section, is a notion of length which becomes infinite for certain sets. 3.3 The Lebesgue measure on R Let = R. We first define a σ-algebra of subsets of R. This can be done in several ways. It can be verified that the three alternatives below are equivalent. (a) Let C be the collection of all intervals of the form [a, b], and let B = σ(C) be the σ-algebra that it generates. (b) Let D be the collection of all intervals of the form (−∞, b], and let B = σ(D) be the σ-algebra that it generates. 11 (c) For any n, we define the Borel σ-algebra of (n, n + 1] as the σ-algebra generated by sets of the form [a, b] ⊂ (n, n + 1]. We then say that A is a Borel subset of R if A ∩ (n, n + 1] is a Borel subset of (n, n + 1], for every n. Exercise 8. Show that the above three definitions of B are equivalent. Let Pn be the uniform measure on (n, n + 1] (defined on the Borel sets in (n, n + 1]). Given a set A ⊂ R, we decompose it into countably many pieces, each piece contained in some interval (n, n + 1], and define its “length” µ(A) using countable additivity: µ(A) = ∞ X n=−∞   Pn A ∩ (n, n + 1] . It turns out that µ is a measure on (R, B), called again Lebesgue measure. However, it is not a probability measure because µ(R) = ∞. Exercise 9. Show that µ is a measure on (R, B). Hint: Use the countable additivity of the measures Pn to establish the countable of µ.PYou can also the fact that if P additivity P1 1 P1 the numbers aij are nonnegative, then 1 i=1 j=1 aij = j=1 i=1 aij . Similar to the case of {0, 1}∞ , there exist subsets of [0, 1] that are not Borel sets. In fact the similarities between the models of Sections 2 and 3 are much deeper; the two models are essentially equivalent, although we will not elaborate on the meaning of this. Let us only say that the equivalence relies on the one-to-one correspondence of the sets [0, 1] and {0, 1}∞ obtained through the binary representation of real numbers. Intuitively, generating a real number at random, according to the uniform distribution (Lebesgue measure) on [0, 1], is probabilistically equivalent to generating each bit in its binary expansion at random. 4 COMPLETION OF A PROBABILITY SPACE Starting with an algebra F0 and a countably additive function P0 on that algebra, the Extension Theorem leads to a probability measure on the smallest σ-algebra containing F0 . Can we extend the measure further, to a larger σ-algebra? If so, is the extension unique, or will there have to be some arbitrary choices? We describe here a generic extension that assigns probabilities to certain additional sets A for which there is little choice. Consider a probability space (Ω, F, P). Suppose that B ∈ F, and P(B) = 0. Any set B with this property is called a null set. (Note that in this context, 12 “null” is not the same as “empty.”) Suppose now that A ⊂ B. If the set A is not in F, it is not assigned a probability; were it to be assigned one, the only choice that would not lead to a contradiction is a value of zero. The first step is to augment the σ-algebra F so that it includes all subsets of null sets. This is accomplished as follows: (a) Let N be the collection of all subsets of null sets; (b) Define F ∗ = σ(F ∪ N ), the smallest σ-algebra that contains F as well as all subsets of null sets. (c) Extend P in some natural manner to obtain a new probability measure P∗ on (Ω, F ∗ ). In particular, we let P∗ (A) = 0 for every subset A ⊂ B of every null set B ∈ F. It turns out that such an extension is always possible and unique. Details of this construction will be worked out in an exercise. The resulting probability space is said to be complete. It has the property that all subsets of null sets are included in the σ-algebra and are also null sets. When Ω = [0, 1] (or Ω = R), F is the Borel σ-algebra, and P is Lebesgue measure, we obtain an augmented σ-algebra F ∗ and a measure P∗ . The sets in F ∗ are called Lebesgue measurable sets. The new measure P∗ is referred to by the same name as the measure P (“Lebesgue measure”). 5 FURTHER REMARKS We record here a few interesting facts related to Borel σ-algebras and the Lebesgue measure. Their proofs tend to be fairly involved. (a) There exist sets that are Lebesgue measurable but not Borel measurable, i.e., F is a proper subset of F ∗ . (b) There are as many Borel measurable sets as there are points on the real line (this is the “cardinality of the continuum”), but there are as many Lebesgue measurable sets as there are subsets of the real line (which is a higher cardinality) [Billingsley] Note: In Lecture 4 we will introduce a Cantor set, which has cardinality of the continuum, while being of measure 0. Since all subsets of a Cantor set (being null-sets) are measurable, it is clear thar |F ∗ | ≥ |2R |. Showing that |F| = |R| is a lot more involved. Note that this difference in cardinalities automatically implies there is a “wealth” of Lebesgue-measurable sets which are not Borel. 13 (c) There exist subsets of [0, 1] that are not Lebesgue measurable; see Section 6 below and [Williams, p. 192]. (d) It is not possible to construct a probability space in which the σ-algebra includes all subsets of [0, 1], with the property that P({x}) = 0 for every x ∈ (0, 1] [Billingsley, pp. 45-46]. 6 APPENDIX: ON STRANGE SETS (optional reading) In this appendix, we provide some evidence that not every subset of (0, 1] is Lebesgue measurable, and, furthermore, that Lebesgue measure cannot be extended to a measure defined for all subsets of (0, 1]. Let “+” stand for addition modulo 1 in (0, 1]. For example, 0.5 + 0.7 = 0.2, instead of 1.2. You may want to visualize (0, 1] as a circle that wraps around so that after 1, one starts again at 0. If A ⊂ (0, 1], and x is a number, then A + x stands for the set of all numbers of the form y + x where y ∈ A. Define x and y to be equivalent if x + r = y for some rational number r. Then, (0, 1] can be partitioned into equivalence classes. (That is, all elements in the same equivalence class are equivalent, elements belonging to different equivalent classes are not equivalent, and every x ∈ (0, 1] belongs to exactly one equivalence class.) Let us pick exactly one element from each equivalence class, and let H be the set of the elements picked this way. (This fact that a set H can be legitimately formed this way involves the Axiom of Choice, a generally accepted axiom of set theory.) We will now consider the sets of the form H + r, where r ranges over the rational numbers in (0, 1]. Note that there are countably many such sets. The sets H + r are disjoint. (Indeed, if r1 6= r2 , and if the two sets H + r1 , H + r2 share the point h1 + r1 = h2 + r2 , with h1 , h2 ∈ H, then h1 and h2 differ by a rational number and are equivalent. If h1 6= h2 , this contradicts the construction of H, which contains exactly one element from each equivalence class. If h1 = h2 , then r1 = r2 , which is again a contradiction.) Therefore, (0, 1] is the union of the countably many disjoint sets H + r. The sets H + r, for different r, are “translations” of each other (they are all formed by starting from the set H and adding a number, modulo 1). Let us say that a measure is translation-invariant if it has the following property: if A and A + x are measurable sets, then P(A) = P(A + x). Suppose that P is a translation invariant probability measure, defined on all subsets of (0, 1]. Then, X �
X 1 = P (0, 1] = P(H + r) = P(H), r r 14 where the sum is taken over all rational numbers in (0, 1]. But this impossible. We conclude that a translation-invariant measure, defined on all subsets of (0, 1] does not exist. On the other hand, it can be verified that the Lebesgue measure is translationinvariant on the Borel σ-algebra, as well as its extension, the Lebesgue σalgebra. This implies that the Lebesgue σ-algebra does not include all subsets of (0, 1]. An even stronger, and more counterintuitive example is the following. It indicates, that the ordinary notion of area or volume cannot be applied to arbitrary sets. The Banach-Tarski Paradox. Let S be the two-dimensional surface of the unit sphere in three dimensions. There exists a subset F of S such that for any k ≥ 3, S = (τ1 F ) ∪ · · · ∪ (τk F ), where each τi is a rigid rotation and the sets τi F are disjoint. For example, S can be made up by three rotated copies of F (suggesting probability equal to 1/3, but also by four rotated copies of F , suggesting probability equal to 1/4). Ordinary geometric intuition clearly fails when dealing with arbitrary sets. 15