1 Due September 6 Problems 1.20, 1.26, 1.30 from the textbook Add-on sketch of a proof of existence of a set which is not Lebesgue-measurable. The original example is due to G. Vitali. Let = [0, 1); we will show that there is no translation-invariant (probability) measure P defined on all subsets of . Translation-invariance here means that for all , P(A) = P(A+ ); the set A+ is obtained by translating A by , i.e., A+ = {x [0, 1) y A, x y Z}. (We considered [0, 2) in class, but [0, 1) helps to shorten notation a bit.) 1. Introduce an equivalence relation: x y if x y Q. The interval is then split into nonintersecting equivalence classes, C : = C . 2. By axiom of choice there exists a set V containing exactly one element from each equivalence class. Observe that [0, 1) is the union of rational translations of V = V+q . qQ[0,1) This holds because the orbit (all rational translations) of each element of V is exactly the entire corresponding equivalence class. 3. The countable additivity property then requires that 1 = P() = P(V+q ). qQ[0,1) The latter sum, however, is either zero or infinity, depending on whether P(V+q ) = P(V) is zero or greater than zero. So V cannot be in our -algebra and thus we reach a contradiction. Copyright 2014. OUP Oxford. All rights reserved. May not be reproduced in any form without permission from the publisher, except fair uses permitted under U.S. or applicable copyright law. 8 Events and probabilities T S Proof The complement of i=1 A i equals i=1 ( \\ A i ), which is the union of the complements of events and is therefore an event. Hence the intersection of the Ai is an event also, as before. 2 Property If A F then P(A) + P( \\ A) = 1. Proof The events A and  \\ A are disjoint with union , and so 1 = P() = P(A) + P( \\ A). 2 Property If A, B F then P(A B) + P(A B) = P(A) + P(B). Proof The set A is the union of the disjoint sets A \\ B and A B, and hence P(A) = P(A \\ B) + P(A B) by (1.14). A similar remark holds for the set B, giving that P(A) + P(B) = P(A \\ B) + 2P(A B) + P(B \\ A) \u0001 = P (A \\ B) (A B) (B \\ A) + P(A B) = P(A B) + P(A B). by (1.14) 2 Property If A, B F and A B then P(A) P(B). Proof We have that P(B) = P(A) + P(B \\ A) P(A). 2 It is often useful to draw a Venn diagram when working with probabilities . For example, to illustrate the formula P(A B) + P(A B) = P(A) + P(B), we might draw the diagram in Figure 1.1, and note that the probability of A B is the sum of P(A) and P(B) minus P(A B), since the last probability is counted twice in the simple sum P(A) + P(B).  A B AB Fig. 1.1 A Venn diagram illustrating the fact that P(A B) = P(A) + P(B) P(A B). In the following exercises, (, F , P) is a probability space. EBSCO Publishing : eBook Collection (EBSCOhost) - printed on 9/4/2016 4:30 PM via UNIV OF ARIZONA AN: 852090 ; Grimmett, Geoffrey, Welsh, D. J. A..; Probability : An Introduction Account: uariz Copyright 2014. OUP Oxford. All rights reserved. May not be reproduced in any form without permission from the publisher, except fair uses permitted under U.S. or applicable copyright law. 1.5 Discrete sample spaces 9 Exercise 1.19 If A, B F , show that P(A \\ B) = P(A) P(A B). Exercise 1.20 If A, B, C F , show that P(A B C) = P(A) + P(B) + P(C) P(A B) P(B C) P(A C) + P(A B C). Exercise 1.21 Let A, B, C be three events such that 5 , P(A) = 10 3 , P(A B) = 10 7 , P(B) = 10 4 , P(B C) = 10 1 . P(A B C) = 10 6 , P(C) = 10 2 , P(A C) = 10 By drawing a Venn diagram or otherwise, find the probability that exactly two of the events A, B, C occur. Exercise 1.22 A fair coin is tossed 10 times (so that heads appears with probability 21 at each toss). Describe the appropriate probability space in detail for the two cases when (a) the outcome of every toss is of interest, (b) only the total number of tails is of interest. In the first case your event space should have 22 events. 1.5 10 events, but in the second case it need have only 211 Discrete sample spaces Let E be an experiment with probability space (, F , P). The structure of this space depends greatly on whether  is a countable set (that is, a finite or countably infinite set) or an uncountable set. If  is a countable set, we normally take F to be the set of all subsets of , for the following reason. Suppose that  = {1 , 2 , . . . } and, for each , we are interested in whether or not this given is the actual outcome of E ; then we require that each singleton set {} belongs to F . Let A . Then A is countable (since  is countable), and so A maySbe expressed as the union of the countably many i which belong to A, giving that A = A {} F by (1.4). The probability P(A) of the event A is determined by the collection of probabilities P({}) as ranges over , since, by (1.14), X P({}). P(A) = A We usually write P() for the probability P({}) of an event containing only one point in . Example 1.23 (Equiprobable outcomes) If  = {1 , 2 , . . . , N } and P(i ) = P( j ) for all i and j , then P() = 1/N for , and P(A) = |A|/N for A . Example 1.24 (Random integers) There are 'intuitively clear' statements which are without meaning in probability theory, and here is an example: if we pick a positive integer at random, then it is an even integer with probability 12 . Interpreting 'at random' to mean that each positive integer is equally likely to be picked, then this experiment would have probability space (, F , P), where EBSCO Publishing : eBook Collection (EBSCOhost) - printed on 9/4/2016 4:30 PM via UNIV OF ARIZONA AN: 852090 ; Grimmett, Geoffrey, Welsh, D. J. A..; Probability : An Introduction Account: uariz Copyright 2014. OUP Oxford. All rights reserved. May not be reproduced in any form without permission from the publisher, except fair uses permitted under U.S. or applicable copyright law. 10 Events and probabilities (a)  = {1, 2, . . . }, (b) F is the set of all subsetsP of , (c) if A , then P(A) = i A P(i ) = |A|, where is the probability that any given integer, i say, is picked. However, if = 0 then P() = if > 0 then P() = X i=1 X i=1 0 = 0, = , neither of which is in agreement with the rule that P() = 1. One possible way of interpreting the italicized statement above is as follows. Let N be a large positive integer, and let E N be the experiment of picking an integer from the finite set  N = {1, 2, . . . , N} at random. The probability that the outcome of E N is even is \u0012 \u0013 1 1 1 1 if N is odd, if N is even, and 2 2 N so that, as N , the required probability tends to 12 . Despite this sensible interpretation of the italicized statement, we emphasize that this statement is without meaning in its present form and should be shunned by serious probabilists. The most elementary problems in probability theory are those which involve experiments such as the shuffling of cards or the throwing of dice, and these usually give rise to situations in which every possible outcome is equally likely to occur. This is the case of Example 1.23 above. Such problems usually reduce to the problem of counting the number of ways in which some event may occur, and the following exercises are of this type. Exercise 1.25 Show that if a coin is tossed n times, then there are exactly \u0012 \u0013 n! n = k! (n k)! k sequences of possible outcomes in which exactly k heads are obtained. If the coin is fair (so heads and tails are equally likely on each toss), show that the probability of getting at least k heads is n \u0012 \u0013 1 X n . r 2n r=k Exercise 1.26 We distribute r distinguishable balls into n cells at random, multiple occupancy being permitted. Show that (a) there are n r possible arrangements, \u0001 (b) there are rk (n 1)rk arrangements in which the first cell contains exactly k balls, EBSCO Publishing : eBook Collection (EBSCOhost) - printed on 9/4/2016 4:30 PM via UNIV OF ARIZONA AN: 852090 ; Grimmett, Geoffrey, Welsh, D. J. A..; Probability : An Introduction Account: uariz Copyright 2014. OUP Oxford. All rights reserved. May not be reproduced in any form without permission from the publisher, except fair uses permitted under U.S. or applicable copyright law. 1.6 Conditional probabilities 11 (c) the probability that the first cell contains exactly k balls is \u0013 \u0012 \u0013 \u0012 \u0013k \u0012 1 rk 1 r 1 . n n k Exercise 1.27 In a game of bridge, the 52 cards of a conventional pack are distributed at random between the four players in such a way that each player receives 13 cards. Show that the probability that each player receives one ace is 24 48! 134 = 0.105 . . . . 52! Exercise 1.28 Show that the probability that two given hands in bridge contain k aces between them is \u0013 \u001e\u0012 \u0013 \u0012 \u0013\u0012 52 48 4 . 26 k 26 k Exercise 1.29 Show that the probability that a hand in bridge contains 6 spades, 3 hearts, 2 diamonds and 2 clubs is \u0012 \u0013\u0012 \u0013\u0012 \u00132 \u001e\u0012 \u0013 52 13 13 13 . 13 2 3 6 Exercise 1.30 Which of the following is more probable: (a) getting at least one six with 4 throws of a die, (b) getting at least one double six with 24 throws of two dice? This is sometimes called 'de Mere's paradox', after the professional gambler Chevalier de Mere, who believed these two events to have equal probability. 1.6 Conditional probabilities Let E be an experiment with probability space (, F , P). We may sometimes possess some incomplete information about the actual outcome of E without knowing this outcome entirely. For example, if we throw a fair die and a friend tells us that an even number is showing, then this information affects our calculations of probabilities. In general, if A and B are events (that is, A, B F ) and we are given that B occurs, then, in the light of this information, the new probability of A may no longer be P(A). Clearly, in this new circumstance, A occurs if and only if A B occurs, suggesting that the new probability of A should be proportional to P(A B). We make this chat more formal in a definition.7 Definition 1.31 If A, B F and P(B) > 0, the (conditional) probability of A given B is denoted by P(A | B) and defined by P(A | B) = P(A B) . P(B) 7 We emphasize that this is a definition rather than a theorem. EBSCO Publishing : eBook Collection (EBSCOhost) - printed on 9/4/2016 4:30 PM via UNIV OF ARIZONA AN: 852090 ; Grimmett, Geoffrey, Welsh, D. J. A..; Probability : An Introduction Account: uariz (1.32) Copyright 2014. OUP Oxford. All rights reserved. May not be reproduced in any form without permission from the publisher, except fair uses permitted under U.S. or applicable copyright law. 12 Events and probabilities Note that the constant of proportionality in (1.32) has been chosen so that the probability P(B | B), that B occurs given that B occurs, satisfies P(B | B) = 1. We must next check that this definition gives rise to a probability space. Theorem 1.33 If B F and P(B) > 0 then (, F , Q) is a probability space where Q : F R is defined by Q(A) = P(A | B). Proof We need only check that Q is a probability measure on (, F ). Certainly Q(A) 0 for A F and P( B) = 1, Q() = P( | B) = P(B) and it remains to check that Q satisfies (1.14). Suppose that A1 , A2 , . . . are disjoint events in F . Then ! ! ! [ [ 1 Ai = Q Ai B P P(B) i i ! [ 1 = (Ai B) P P(B) i 1 X P(Ai B) since P satisfies (1.14) = P(B) i X = Q(Ai ). 2 i Exercise 1.34 If (, F , P) is a probability space and A, B, C are events, show that P(A B C) = P(A | B C)P(B | C)P(C) so long as P(B C) > 0. Exercise 1.35 Show that P(B | A) = P(A | B) P(B) P(A) if P(A) > 0 and P(B) > 0. Exercise 1.36 Consider the experiment of tossing a fair coin 7 times. Find the probability of getting a prime number of heads given that heads occurs on at least 6 of the tosses. 1.7 Independent events We call two events A and B 'independent' if the occurrence of one of them does not affect the probability that the other occurs. More formally, this requires that, if P(A), P(B) > 0, then P(A | B) = P(A) and P(B | A) = P(B). (1.37) Writing P(A | B) = P(A B)/P(B), we see that the following definition is appropriate. EBSCO Publishing : eBook Collection (EBSCOhost) - printed on 9/4/2016 4:30 PM via UNIV OF ARIZONA AN: 852090 ; Grimmett, Geoffrey, Welsh, D. J. A..; Probability : An Introduction Account: uariz Copyright 2014. OUP Oxford. All rights reserved. May not be reproduced in any form without permission from the publisher, except fair uses permitted under U.S. or applicable copyright law. 1.7 Independent events 13 Definition 1.38 Events A and B of a probability space (, F , P) are called independent if P(A B) = P(A)P(B), (1.39) and dependent otherwise. This definition is slightly more general than (1.37) since it allows the events A and B to have zero probability. It is easily generalized as follows to more than two events. A family A = (Ai : i I ) of events is called independent if, for all finite subsets J of I , ! Y \\ P P(Ai ). (1.40) Ai = i J i J The family A is called pairwise independent if (1.40) holds whenever |J | = 2. Thus, three events, A, B, C, are independent if and only if the following equalities hold: P(A B C) = P(A)P(B)P(C), P(A C) = P(A)P(C), P(A B) = P(A)P(B), P(B C) = P(B)P(C). There are families of events which are pairwise independent but not independent. Example 1.41 Suppose that we throw a fair four-sided die (you may think of this as a square die thrown in a two-dimensional universe). We may take  = {1, 2, 3, 4}, where each  is equally likely to occur. The events A = {1, 2}, B = {1, 3}, C = {1, 4} are pairwise independent but not independent. Exercise 1.42 Let A and B be events satisfying P(A), P(B) > 0, and such that P(A | B) = P(A). Show that P(B | A) = P(B). Exercise 1.43 If A and B are events which are disjoint and independent, what can be said about the probabilities of A and B? Exercise 1.44 Show that events A and B are independent if and only if A and  \\ B are independent. Exercise 1.45 Show that events A 1 , A 2 , . . . , A m are independent if and only if  \\ A 1 ,  \\ A 2 , . . . ,  \\ A m are independent. Exercise 1.46 If A 1 , A 2 , . . . , A m are independent and P(A i ) = p for i = 1, 2, . . . , m, find the probability that (a) none of the A i occur, (b) an even number of the A i occur. Exercise 1.47 On your desk, there is a very special die with a prime number p of faces, and you throw this die once. Show that no two events A and B can be independent unless either A or B is the whole sample space or the empty set. EBSCO Publishing : eBook Collection (EBSCOhost) - printed on 9/4/2016 4:30 PM via UNIV OF ARIZONA AN: 852090 ; Grimmett, Geoffrey, Welsh, D. J. A..; Probability : An Introduction Account: uariz