15 251 Great Theoretical Ideas in Computer Science Some Puzzles Probability Theory Counting in Terms of Proportions Lecture 10 September 25 2008 Teams A and B are equally good In any one game each is equally likely to win What is the 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 3 choices of bag 2 ways to order bag contents 6 equally likely paths Silver and Gold One 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 Given that we see a gold 2 3 of remaining paths have gold in them Finite Probability Distribution So sometimes probabilities can be counter intuitive A finite probability distribution p is a finite set S of elements together with a nonnegative real weight or probability p x for each element x in S The weights must satisfy x S p x 1 S is often called the sample space and elements x in S are called samples Language of Probability The formal language of probability is a very important tool in computer science and science Sample Space 0 17 0 1 0 13 0 11 0 2 0 0 13 0 1 S 0 06 Sample space weight or probability of x p x 0 2 Events A fair coin is tossed 100 times in a row Any set E S is called an event PrD E x E p x 0 17 0 0 13 S What is the probability that we get exactly half heads 0 1 PrD E 0 4 Uniform Distribution If each element has equal probability the distribution is said to be uniform PrD E x E p x 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 Suppose we roll a white die and a black die S all sequences of 100 tosses What is the probability that sum is 7 or 11 x HHTTT TH p x 1 S Event E Set of sequences with 50 H s and 50 T s Same Methodology S 1 1 2 1 3 1 4 1 5 1 6 1 Set of all 2100 sequences H T 100 Probability of event E proportion of E in S 100 2100 50 1 2 2 2 3 2 4 2 5 2 6 2 1 3 2 3 3 3 4 3 5 3 6 3 1 4 2 4 3 4 4 4 5 4 6 4 1 5 2 5 3 5 4 5 5 5 6 5 1 6 2 6 3 6 4 6 5 6 6 6 Pr E E S proportion of E in S 8 36 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 And The Same Methods Again Sample space W 1 2 3 366 23 E all sequences in S that have no repeated numbers E 366 365 344 W 36623 E W 0 494 E 0 506 W Sons of Adam Adam was X inches tall He had two sons One was X 1 inches tall x 17 42 363 1 224 177 23 numbers Event E x W two numbers in x are same What is E Count E instead One was X 1 inches tall Each of his sons had two sons More Language Of Probability 1X 1 X 1 X 2 1 X 3 1 1 X 4 1 X 1 2X X 1 3 4 X 2 X 2 1 X 1 3 6X The probability of event A given event B is written Pr A B and is defined to be 4 X 2 Pr A B X 3 1 Pr B 1 X 4 In the nth generation there will be 2n males each with one of n 1 different heights h0 h1 hn n hi X n 2i occurs with proportion i 2n Unbiased Binomial Distribution On n 1 Elements Let S be any set h0 h1 hn where each element hi has an associated probability n i 2n Any such distribution is called an Unbiased Binomial Distribution or an Unbiased Bernoulli Distribution S B proportion of A B A to B Suppose we roll a white die and black die What is the probability that the white is 1 given that the total is 7 event A white die 1 event B total 7 S 1 1 2 1 3 1 4 1 5 1 6 1 1 2 2 2 3 2 4 2 5 2 6 2 Pr A B 1 3 2 3 3 3 4 3 5 3 6 3 Pr A B Pr B event A white die 1 1 4 2 4 3 4 4 4 5 4 6 4 1 5 2 5 3 5 4 5 5 5 6 5 A B B 1 6 2 6 3 6 4 6 5 6 6 6 1 6 event B total 7 Independence A and B are independent events if Pr A B Pr A Pr A B Pr A Pr B Pr B A Pr B Declaration of Independence A1 A2 Ak are independent events if knowing if some of them occurred does not change the probability of any of the others occurring E g A1 A2 A3 are independent events if 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 Silver and Gold One 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 G1 be the event that the first coin is gold Monty Hall Problem Pr G1 1 2 Sample space prize behind door 1 prize behind door 2 prize behind door 3 Let G2 be the event that the second coin is gold Each has probability 1 3 Pr G2 G1 Pr G1 and G2 Pr G1 1 3 1 2 2 3 Note G1 and G2 are not independent Monty Hall Problem Announcer hides prize behind one of 3 doors at random You select some door Announcer opens one of others with no prize You can decide to keep or switch What to …
View Full Document
Unlocking...