15-251Great Theoretical Ideas in Computer ScienceforSomeLecture 11 (February 17, 2009)Probability Theory ISome PuzzlesTeams A and B are equally goodIn any one game, each is equally likely to winWhat is most likely length of a “best of 7” series?Flip coins until either 4 heads or 4 tails Is this more likely to take 6 or 7 flips?6 and 7 Are Equally LikelyTo reach either one, after 5 games, it must be 3 to 2½ chance it ends 4 to 2; ½ chance it doesn’tSilver and GoldA bag has two silver coins, another has two gold coins, and the third has one of eachOne bag is selected at random. One coin from it is selected at random. It turns out to be goldWhat is the probability that the other coin is gold?3 choices of bag2 ways to order bag contents 6 equally likely pathsGiven that we see a gold, 2/3 of remaining paths have gold in them!Sometimes, probabilities can be counter-intuitive??Language of ProbabilityThe formal language of probability is a very important tool in describing and analyzing probability distributionFinite Probability DistributionA (finite) probability distribution D is a finite set S of elements, where each element t in S has a non-negative real weight, proportion, or probability p(t) p(t) = 1t SFor convenience we will define D(t) = p(t)S is often called the sample space and elements t in S are called samplesThe weights must satisfy:SSample spaceSample SpaceD(t) = p(t) = 0.2weight or probability of t0.20.130.060.110.170.10.1300.1EventsAny set E S is called an event p(t)t EPrD[E] = S0.170.10.130PrD[E] = 0.4Uniform DistributionIf each element has equal probability, the distribution is said to be uniform p(t) = t EPrD[E] = |E||S|A fair coin is tossed 100 times in a rowWhat is the probability that we get exactly half heads?The sample space S is the set of all outcomes {H,T}100Each sequence in S is equally likely, and hence has probability 1/|S|=1/2100Using the LanguageS = all sequencesof 100 tosses t = HHTTT……THp(t) = 1/|S|VisuallySet of all 2100sequences{H,T}100Probability of event E = proportion of E in SEvent E = Set of sequences with 50H’s and 50 T’s10050/ 2100Suppose we roll a white die and a black die What is the probability that sum is 7 or 11?(1,1), (1,2), (1,3), (1,4), (1,5), (1,6),(2,1), (2,2), (2,3), (2,4), (2,5), (2,6),(3,1), (3,2), (3,3), (3,4), (3,5), (3,6),(4,1), (4,2), (4,3), (4,4), (4,5), (4,6),(5,1), (5,2), (5,3), (5,4), (5,5), (5,6),(6,1), (6,2), (6,3), (6,4), (6,5), (6,6) }Pr[E] = |E|/|S| = proportion of E in S = 8/36Same Methodology!S = {23 people are in a roomSuppose that all possible birthdays are equally likelyWhat is the probability that two people will have the same birthday?t = (17,42,363,1,…, 224,177)23 numbersAnd The Same Methods Again!Sample space W = {1, 2, 3, …, 366}23Event E = { t W | two numbers in t are same }Count |E| instead!What is |E|?all sequences in S that have no repeated numbersE =|W| = 36623|E| = (366)(365)…(344)= 0.494…|W||E||E||W|= 0.506…and is defined to be = SABproportion of A BMore Language Of ProbabilityThe probability of event A given event B is written Pr[ A | B ]to BPr [ A B ]Pr [ B ]event A = {white die = 1}event B = {total = 7}Suppose we roll a white die and black dieWhat is the probability that the white is 1 given that the total is 7?(1,1), (1,2), (1,3), (1,4), (1,5), (1,6),(2,1), (2,2), (2,3), (2,4), (2,5), (2,6),(3,1), (3,2), (3,3), (3,4), (3,5), (3,6),(4,1), (4,2), (4,3), (4,4), (4,5), (4,6),(5,1), (5,2), (5,3), (5,4), (5,5), (5,6),(6,1), (6,2), (6,3), (6,4), (6,5), (6,6) }S = {|B|Pr[B]6|A B|=Pr [ A | B ]Pr [ A B ]1= =event A = {white die = 1} event B = {total = 7}Independence!A and B are independent events ifPr[ A | B ] = Pr[ A ]Pr[ A B ] = Pr[ A ] Pr[ B ] Pr[ B | A ] = Pr[ B ]Pr[A1| A2 A3] = Pr[A1]Pr[A2| A1 A3] = Pr[A2]Pr[A3| A1 A2] = Pr[A3]Pr[A1| A2] = Pr[A1] Pr[A1| A3] = Pr[A1]Pr[A2| A1] = Pr[A2] Pr[A2| A3] = Pr[A2]Pr[A3| A1] = Pr[A3] Pr[A3| A2] = Pr[A3]E.g., {A1, A2, A3}are independent events if:Independence!A1, A2, …, Akare independent events if knowing if some of them occurred does not change the probability of any of the others occurringSilver and GoldOne bag has two silver coins, another has two gold coins, and the third has one of eachOne bag is selected at random. One coin from it is selected at random. It turns out to be goldWhat is the probability that the other coin is gold?Let G1be the event that the first coin is goldPr[G1] = 1/2Let G2be the event that the second coin is goldPr[G2| G1] = Pr[G1and G2] / Pr[G1]= (1/3) / (1/2)= 2/3Note: G1and G2are not independentMonty Hall ProblemAnnouncer hides prize behind one of 3 doors at randomYou select some doorAnnouncer opens one of others with no prizeYou can decide to keep or switchWhat to do?Stayingwe win if we choose the correct doorSwitchingwe win if we choose the incorrect doorPr[ choosing correct door ] = 1/3Pr[ choosing incorrect door ] = 2/3Monty Hall ProblemSample space = { prize behind door 1, prize behind door 2, prize behind door 3 } Each has probability 1/3We are inclined to think:“After one door is opened, others are equally likely…”But his action is not independent of yours!Why Was This Tricky?Next, we will learn about a formidable tool in probability that will allow us to solve problems that seem really really messy…If I randomly put 100 letters into 100 addressed envelopes, on average how many letters will end up in their correct envelopes?On average, in class of size m, how many pairs of people will have the same birthday?The new tool is called “Linearity of Expectation”Random VariableTo use this new tool, we will also need to understand the concept of a Random VariableRandom VariableA Random Variable is a real-valued function on SExamples:X = value of white die in a two-dice rollX(3,4) = 3, X(1,6) = 1Y = sum of values of the two diceY(3,4) = 7, Y(1,6) = 7Let S be sample space in a probability distributionNotational ConventionsUse letters like A, B, E for eventsUse letters like X, Y, f, g for R.V.’sR.V. = random variableTwo Views of Random VariablesInput to the function is randomRandomness is “pushed” to the values of the functionThink of a R.V. as A function from S to the reals ROr think of the induced distribution on R012TTHTTHHH¼¼¼¼STwo Coins TossedX:
View Full Document
Unlocking...