Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Slide 46Slide 47Slide 48Slide 49Slide 50Slide 51Slide 52Slide 53Slide 54Slide 55Slide 56Slide 57Slide 58Slide 59Slide 60Slide 61Slide 62Slide 63Slide 64Slide 65Slide 66Slide 67Slide 6815-251Great Theoretical Ideas in Computer Science15-251Flipping Coins for Computer ScientistsLecture 11 (September 28, 2010)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’tTeams A is now better than team BThe odds of A winning are 6:5What is the chance that A will beat B in the “best of 7” world series?i.e., in any game, A wins with probability 6/11Silver 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?Let us start simple…A fair coin is tossed 100 times in a rowWhat is the probability that we get exactly 50 heads?The set of all outcomes is {H,T}100There are 2100 outcomesOut of these, the number of sequences with 50 heads is10050/ 210010050If we draw a random sequence, theprobability of seeing such a sequence: = 0.07958923739…The sample space S, the set of all outcomes, is {H,T}100The Language of Probability“A fair coin is tossed 100 times in a row”Each sequence in S is equally likely, and hence has probability 1/|S|=1/2100“What is the probability that we get exactly 50 heads?”Let E = {x in S| x has 50 heads} be the event that we see half heads.The Language of ProbabilityPr(E) = |E|/|S| = |E|/2100Pr(E) = x in E Pr(x) = |E|/2100Set S of all 2100 sequences{H,T}100Probability of event E = proportion of E in SEvent E = Set of sequences with 50 H’s and 50 T’s10050/ 2100A fair coin is tossed 100 times in a rowWhat is the probability that we get 50 heads in a row?The sample space S, the set of all outcomes, is {H,T}100formalizing this problem…again, each sequence in S equally likely, and hence with probability 1/|S|=1/2100Now E = {x in S| x has 50 headsin a row} is the event of interest.What is |E|?25050HHHanythingHHH anythingT249HHHT249HHHT249HHHT249M49 50 4950 2 2 52 2 g g49100 5152 2 5202 2E gIf we roll a fair die, what is the probability that the result is an even number?½, obviouslyTrue, but let’s take the trouble to say this formally.Each outcome x in S is equally likely, i.e.,x in S, the probability that x occurs is 1/6.sample space S = {1,2,3,4,5,6}P( )116126136146156166x x 2,4,6E 1 1 1 3 1P ( )6 6 6 6 2E Suppose that a dice is weighted so that the numbers do not occur with equal frequency. 2,4,6E 2 1 3 4 2P( )6 12 12 6 3E P( )1 1/ 62 2 / 63 1/124 1/125 1/126 3/12x xtable of frequencies (proportions) (probabilities)Language of ProbabilityThe formal language of probability is a crucial tool in describing and analyzing problems involving probabilities…and in avoiding errors,ambiguities, and fallacious reasoning.Finite 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|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 LanguageSet of all 2100 sequences{H,T}100Probability of event E = proportion of E in SEvent E = Set of sequences with 50 H’s and 50 T’s10050/ 2100VisuallySuppose 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?Modeling this problemEach person born on a uniformly random day of the year, independent of the others.The year has 366 days.We assume this random experiment: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…Birthday ParadoxNumber of People Probabilityof no collisions21 0.55622 0.52423 0.49424 0.461Modeling this problemEach person born on a uniformly random day of the year, independent of the others.The year has 366 days.We assume this random experiment:Accounting for seasonal variations in birthdayswould make it more likely to have collisions!BTW, note that probabilities satisfy the following properties:2) P(E) ≥ 0 for all events E1) P(S) = 13) P(A B) = P(A) + P(B), for disjoint events A and BHence, P(A) = 1- P(A)axiomsofprobability2) P(E) ≥ 0 for all events E1) P(S) = 13) P(A B) = P(A) + P(B), for disjoint events A and BTo develop the notion of probability forinfinite spaces,
View Full Document
Unlocking...