Introduction to Probability: Problem Solutions

1 Introduction to Probability: Problem Solutions (last updated: 5/15/07)c Dimitri P. Bertsekas and John N. TsitsiklisMassachusetts Institute of TechnologyWWW site for book information and Scientific, Belmont, Massachusetts1C H A P T E R 1 Solution to Problem haveA={2,4,6},B={4,5,6},soA B={2,4,5,6}, and(A B)c={1,3}.On the other hand,Ac Bc={1,3,5} {1,2,3}={1,3}.Similarly, we haveA B={4,6}, and(A B)c={1,2,3,5}.On the other hand,Ac Bc={1,3,5} {1,2,3}={1,2,3,5}.Solution to Problem (a) By using a Venn diagram it can be seen that for anysetsSandT, we haveS= (S T) (S Tc).(Alternatively, argue that anyxmust belong to eitherTor toTc, soxbelongs toSif and only if it belongs toS Tor toS Tc.) Apply this equality withS=AcandT=B, to obtain the first relationAc= (Ac B) (Ac Bc).Interchange the roles ofAandBto obtain the second relation.(b) By De Morgan s law, we have(A B)c=Ac Bc,and by using the equalities of part (a), we obtain(A B)c=((Ac B) (Ac Bc)) ((A Bc) (Ac Bc))= (Ac B) (Ac Bc) (A Bc).

2 (c) We haveA={1,3,5}andB={1,2,3}, soA B={1,3}. Therefore,(A B)c={2,4,5,6},2andAc B={2},Ac Bc={4,6},A Bc={5}.Thus, the equality of part (b) is to Problem the events that the chosen student isa genius and a chocolate lover, respectively. We haveP(G) = ,P(C) = , andP(G C) = We are interested inP(Gc Cc), which is obtained with the followingcalculation:P(Gc Cc) = 1 P(G C) = 1 (P(G)+P(C) P(G C))= 1 ( + ) = to Problem first determine the probabilities of the six possibleoutcomes. Leta=P({1}) =P({3}) =P({5}) andb=P({2}) =P({4}) =P({6}).We are given thatb= 2a. By the additivity and normalization axioms, 1 = 3a+ 3b=3a+ 6a= 9a. Thus,a= 1/9,b= 2/9, andP({1,2,3}) = 4 to Problem outcome of this experiment can be any finite sequenceof the form (a1, a2, .. , an), wherenis an arbitrary positive integer,a1, a2, .. , an 1belong to{1,3}, andanbelongs to{2,4}. In addition, there are possible outcomesin which an even number is never obtained.

3 Such outcomes are infinite sequences(a1, a2, ..), with each element in the sequence belonging to{1,3}. The sample spaceconsists of all possible outcomes of the above two to Problem (a) Each possible outcome has probability 1/36. Thereare 6 possible outcomes that are doubles, so the probability of doubles is 6/36 = 1/6.(b) The conditioning event (sum is 4 or less) consists of the 6 outcomes{(1,1),(1,2),(1,3),(2,1),(2,2),( 3,1)},2 of which are doubles, so the conditional probability of doubles is 2/6 = 1/3.(c) There are 11 possible outcomes with at least one 6, namely, (6,6), (6, i), and (i,6),fori= 1,2, .. ,5. Thus, the probability that at least one die is a 6 is 11/36.(d) There are 30 possible outcomes where the dice land on different numbers. Out ofthese, there are 10 outcomes in which at least one of the rolls is a 6. Thus, the desiredconditional probability is 10/30 = 1 to Problem the event that the first toss is a head andletBbe the event that the second toss is a head.

4 We must compare the conditionalprobabilitiesP(A B|A) andP(A B|A B). We haveP(A B|A) =P((A B) A)P(A)=P(A B)P(A),andP(A B|A B) =P((A B) (A B))P(A B)=P(A B)P(A B).3 SinceP(A B) P(A), the first conditional probability above is at least as large, soAlice is right, regardless of whether the coin is fair or not. In the case where the coinis fair, that is, if all four outcomesHH,HT,T H,T Tare equally likely, we haveP(A B)P(A)=1/41/2=12,P(A B)P(A B)=1/43/4= generalization of Alice s reasoning is that ifA,B, andCare events such thatB CandA B=A C(for example, ifA B C), then the eventAis at leastas likely if we know thatBhas occurred than if we know thatChas occurred. Alice sreasoning corresponds to the special case whereC=A to Problem this Problem , there is a tendency to reason thatsince the opposite face is either heads or tails, the desired probability is 1/2. This is,however, wrong, because given that heads came, it is more likely that the two-headedcoin was chosen.

5 The correct reasoning is to calculate the conditional probabilityp=P(two-headed coin was chosen|heads came)=P(two-headed coin was chosen and heads came)P(heads came).We haveP(two-headed coin was chosen and heads came) =13,P(heads came) =12,so by taking the ratio of the above two probabilities, we obtainp= 2/3. Thus, theprobability that the opposite face is tails is 1 p= 1 to Problem the event that the batch will be A2 A3 A4, whereAi,i= 1, .. ,4, is the event that theith item isnot defective. Using the multiplication rule, we haveP(A) =P(A1)P(A2|A1)P(A3|A1 A2)P(A4|A1 A2 A3) =95100 9499 9398 9297= to Problem the definition of conditional probabilities, wehaveP(A B|B) =P(A B B)P(B)=P(A B)P(B)=P(A|B).Solution to Problem the event that Alice does not find her paper indraweri. Since the paper is in draweriwith probabilitypi, and her search is successfulwith probabilitydi, the multiplication rule yieldsP(Ac) =pidi, so thatP(A) = 1 the event that the paper is in , thenA B=B,P(A B) =P(B), and we haveP(B|A) =P(A B)P(A)=P(B)P(A)=pj1 , ifi=j, we haveP(B|A) =P(A B)P(A)=P(B)P(A|B)P(A)=pi(1 di)1 to Problem (a) Figure provides a sequential description for thethree different strategies.

6 Here we assume 1 point for a win, 0 for a loss, and 1/2 pointfor a draw. In the case of a tied 1-1 score, we go to sudden death in the next game,and Boris wins the match (probabilitypw), or loses the match ( probability 1 pw).(i) Using the total probability theorem and the sequential description of Fig. (a),we haveP(Boris wins) =p2w+ 2pw(1 pw) termp2wcorresponds to the win-win outcome, and the term 2pw(1 pw)pwcorre-sponds to the win-lose-win and the lose-win-win - 0 Timid playpwBold play( a )( b )(c)Bold playBold playBold playBold playTimid playTimid playTimid play0 - 01 - 02 - 01 - 11 - 10 - 10 - 20 - 20 - 11 - - 01 - 01 - 11 - 10 - 10 - :Sequential descriptions of the chess match histories under strategies(i), (ii), and (iii).5(ii) Using Fig. (b), we haveP(Boris wins) =p2dpw,corresponding to the draw-draw-win outcome.(iii) Using Fig. (c), we haveP(Boris wins) =pwpd+pw(1 pd)pw+ (1 pw) termpwpdcorresponds to the win-draw outcome, the termpw(1 pd)pwcorre-sponds to the win-lose-win outcome, and the term (1 pw)p2wcorresponds to lose-win-win outcome.

7 (b) Ifpw<1/2, Boris has a greater probability of losing rather than winning any onegame, regardless of the type of play he uses. Despite this, the probability of winningthe match with strategy (iii) can be greater than 1/2, provided thatpwis close enoughto 1/2 andpdis close enough to 1. As an example, ifpw= andpd= , withstrategy (iii) we haveP(Boris wins) = + (1 ) + (1 ) strategies (i) and (ii), the corresponding probabilities of a win can be calculatedto be approximately and , respectively. What is happening here is that withstrategy (iii), Boris is allowed to select a playing styleafterseeing the result of the firstgame, while his opponent is not. Thus, by being able to dictate the playing style ineach game after receiving partial information about the match s outcome, Boris gainsan to Problem (m, k) be the probability that the starting playerwins when the jar initially containsmwhite andkblack balls.

8 We have, using thetotal probability theorem,p(m, k) =mm+k+km+k(1 p(m, k 1))= 1 km+kp(m, k 1).The probabilitiesp(m,1), p(m,2), .. , p(m, n) can be calculated sequentially using thisformula, starting with the initial conditionp(m,0) = to Problem derive a recursion for the probabilitypithat a whiteball is chosen from theith jar. We have, using the total probability theorem,pi+1=m+ 1m+n+ 1pi+mm+n+ 1(1 pi) =1m+n+ 1pi+mm+n+ 1,starting with the initial conditionp1=m/(m+n). Thus, we havep2=1m+n+ 1 mm+n+mm+n+ 1=mm+ generally, this calculation shows that ifpi 1=m/(m+n), thenpi=m/(m+n).Thus, we obtainpi=m/(m+n) for to Problem ,n i(k) denote the probability that afterkex-changes, a jar will containiballs that started in that jar andn iballs that started inthe other jar. We want to findpn,0(4). We argue recursively, using the total probabilitytheorem. We havepn,0(4) =1n 1n pn 1,1(3),pn 1,1(3) =pn,0(2) + 2 n 1n 1n pn 1,1(2) +2n 2n pn 2,2(2),pn,0(2) =1n 1n pn 1,1(1),pn 1,1(2) = 2 n 1n 1n pn 1,1(1),pn 2,2(2) =n 1n n 1n pn 1,1(1),pn 1,1(1) = these equations, we obtainpn,0(4) =1n2(1n2+4(n 1)2n4+4(n 1)2n4)=1n2(1n2+8(n 1)2n4).

9 Solution to Problem Problem with the guard s reasoning is that it isnot based on a fully specified probabilistic model. In particular, in the case where bothof the other prisoners are to be released, the probabilistic method of choosing whichidentity to reveal is not be precise, let A, B, and C be the prisoners, and let A be the one who asksthe guard. Suppose that all prisoners are a priori equally likely to be released. Supposealso that if B and C are to be released, then the guard chooses B or C with equalprobability to reveal to A. Then there four possible outcomes:(1) A and B are to be released, and the guard says B ( probability 1/3).(2) A and C are to be released, and the guard says C ( probability 1/3).(3) B and C are to be released, and the guard says B ( probability 1/6).(4) B and C are to be released, and the guard says C ( probability 1/6).ThenP(A is to be released|guard says B) =P(A is to be released and guard says B)P(guard says B)=1/31/3 + 1/6= ,P(A is to be released|guard says C) = , regardless of the identity revealed by the guard, the probability that A is releasedis equal to 2/3, the a priori probability of being to Problem the maximum and minimum of thetwo amounts, respectively.

10 Consider the three eventsA={X < m),B={m< X <m),C={m < X).LetA(orBorC) be the event thatA(orBorC, respectively) occursandyou firstselect the envelope containing the larger amountm. LetA(orBorC) be the eventthatA(orBorC, respectively) occursandyou first select the envelope containing thesmaller amountm. Finally, consider the eventW={you end up with the envelope containingm}.We want to determineP(W) and check whether it is larger than 1/2 or the total probability theorem, we haveP(W|A) =12(P(W|A) +P(W|A))=12(1 + 0) =12,P(W|B) =12(P(W|B) +P(W|B))=12(1 + 1) = 1,P(W|C) =12(P(W|C) +P(W|C))=12(0 + 1) = these relations together with the total probability theorem, we obtainP(W) =P(A)P(W|A) +P(B)P(W|B) +P(C)P(W|C)=12(P(A) +P(B) +P(C))+12P(B)=12+12P(B).SinceP(B)>0 by assumption, it follows thatP(W)>1/2, so your friend is to Problem (a) We use the formulaP(A|B) =P(A B)P(B)=P(A)P(B|A)P(B).Since all crows are black, we haveP(B) = 1 q.}}}