15 251 Great Theoretical Ideas in Computer Science 15 251 Flipping Coins for Computer Scientists Probability Theory I Lecture 11 September 28 2010 Some Puzzles Teams A and B are equally good In any one game each is equally likely to win What 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 Likely To reach either one after 5 games it must be 3 to 2 chance it ends 4 to 2 chance it doesn t Teams A is now better than team B The odds of A winning are 6 5 i e in any game A wins with probability 6 11 What is the chance that A will beat B in the best of 7 world series Silver and Gold A bag has two silver coins another has two gold coins and the third has one of each One bag is selected at random One coin from it is selected at random It turns out to be gold What is the probability that the other coin is gold Let us start simple A fair coin is tossed 100 times in a row What is the probability that we get exactly 50 heads The set of all outcomes is H T 100 There are 2100 outcomes Out of these the number of 100 sequences with 50 heads is 50 If we draw a random sequence the probability of seeing such a sequence 100 2100 0 07958923739 50 The Language of Probability A fair coin is tossed 100 times in a row The sample space S the set of all outcomes is H T 100 Each sequence in S is equally likely and hence has probability 1 S 1 2100 The Language of Probability 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 Pr E E S E 2100 Pr E x in E Pr x E 2100 Event E Set of sequences with 50 H s and 50 T s Set S of all 2100 sequences H T 100 Probability of event E proportion of E in S 100 2100 50 A fair coin is tossed 100 times in a row What is the probability that we get 50 heads in a row formalizing this problem The sample space S the set of all outcomes is H T 100 again each sequence in S equally likely and hence with probability 1 S 1 2100 Now E x in S x has 50 heads in a row is the event of interest HH H 50 anything HH H T anything HH H T T 249 249 HH H M T 250 249 HH H 249 E 52g2 49 52 100 51 0 2 2 49 50 49 50g2 2 52g2 If we roll a fair die what is the probability that the result is an even number obviously True but let s take the trouble to say this formally sample space S 1 2 3 4 5 6 Each outcome x in S is equally likely i e x in S the probability that x occurs is 1 6 x P x 1 2 3 4 5 6 1 6 1 6 1 6 1 6 1 6 1 6 E 2 4 6 1 1 1 3 1 P E 6 6 6 6 2 Suppose that a dice is weighted so that the numbers do not occur with equal frequency table of frequencies proportions probabilities x P x 1 1 6 E 2 2 6 3 1 12 2 4 1 12 P E 5 1 12 6 6 3 12 2 4 6 1 3 4 2 12 12 6 3 Language of Probability The 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 Distribution A 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 The weights must satisfy t S p t 1 For convenience we will define D t p t S is often called the sample space and elements t in S are called samples Sample Space 0 1 0 17 0 13 0 11 0 2 0 0 13 0 1 S 0 06 Sample space weight or probability of t D t p t 0 2 Events Any set E S is called an event PrD E p t t E 0 17 0 0 13 0 1 PrD E 0 4 S Uniform Distribution If each element has equal probability the distribution is said to be uniform PrD E p t t E E S Using the Language The sample space S is the set of all outcomes H T 100 Each sequence in S is equally likely and hence has probability 1 S 1 2100 Visually Event E Set of sequences with 50 H s and 50 T s Set of all 2100 sequences H T 100 Probability of event E proportion of E in S 100 2100 50 Suppose we roll a white die and a black die What is the probability that sum is 7 or 11 Same Methodology S 1 1 1 2 1 6 2 1 2 2 2 6 3 1 3 2 3 6 4 1 4 2 4 6 Pr E E S 5 1 5 2 5 6 6 1 6 2 1 3 1 4 1 5 2 3 2 4 2 5 3 3 3 4 3 5 4 3 4 4 4 5 proportion of E in 5 5 S 8 36 5 3 5 4 6 3 6 4 6 5 23 people are in a room Suppose that all possible birthdays are equally likely What is the probability that two people will have the same birthday Modeling this problem We assume this random experiment Each person born on a uniformly random day of the year independent of the others The year has 366 days And The Same Methods Again Sample space W 1 2 3 366 23 t 17 42 363 1 224 177 23 numbers Event E t W two numbers in t are same What is E Count E instead E all sequences in S that have no repeated numbers E 366 365 344 W 36623 E W 0 494 E 0 506 W Birthday Paradox Number of People Probability of no collisions 21 0 556 22 0 524 23 0 494 24 0 461 Modeling this problem We assume this random experiment Each person born on a uniformly random day of the year independent of the others The year has 366 days Accounting for seasonal variations in birthdays would make it more likely to have collisions BTW note that probabilities satisfy the following properties 1 P S 1 2 P E 0 for all events E 3 P A B P A P B for disjoint …
View Full Document
Unlocking...