Great Theoretical Ideas In Computer Science John Lafferty CS 15 251 Lecture 10 Sept 28 2006 15 251 Classics Fall 2006 Carnegie Mellon University Today we will learn about a formidable tool in probability that will allow us to solve problems that seem really really messy Language Of Probability The formal language of probability is a very important tool in describing and analyzing probability distributions Finite Probability Distribution A finite probability distribution D is a finite set S of elements where each element x in S has a positive real weight proportion or probability p x The weights must satisfy Finite Probability Distribution A finite probability distribution D is a finite set S of elements where each element x in S has a positive real weight proportion or probability p x For notational convenience we will define D x p x S is often called the sample space and elements x in S are called samples Sample space A finite probability distribution D is a finite set S of elements where each element x in S has a positive real weight proportion or probability p x Sample space S Probability A finite probability distribution D is a finite set S of elements where each element x in S has a positive real weight proportion or probability p x S x weight or probability of x D x p x 0 2 Probability Distribution A finite probability distribution D is a finite set S of elements where each element x in S has a positive real weight proportion or probability p x 0 1 0 17 0 11 0 2 0 weights must sum to 1 0 13 0 1 S 0 13 0 06 Events A finite probability distribution D is a finite set S of elements where each element x in S has a positive real weight proportion or probability p x Any subset E of S is called an event The probability of event E is Events A finite probability distribution D is a finite set S of elements where each element x in S has a positive real weight proportion or probability p x S Event E Events A finite probability distribution D is a finite set S of elements where each element x in S has a positive real weight proportion or probability p x 0 17 0 PrD E 0 4 0 13 0 1 S Uniform Distribution A finite probability distribution D is a finite set S of elements where each element x in S has a positive real weight proportion or probability p x If each element has equal probability the distribution is said to be uniform More Language Of Probability Conditioning The probability of event A given event B is written Pr A B Pr A B and is defined to be Pr B 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 Sample space 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 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 event A white die 1 1 6 2 6 3 6 4 6 5 6 6 6 event B total 7 Pr A B B Pr A B 1 36 A B Pr A B Pr B 1 6 Can do this because is uniformly distributed This way does not care about the distribution Another way to calculate Birthday probability Pr no collision Pr 1st person doesn t collide 1 Pr 2nd doesn t no collisions yet 365 366 Pr 3rd doesn t no collisions yet 364 366 Pr 4th doesn t no collisions yet 363 366 Pr 23rd doesn t no collisions yet 344 366 1 365 366 364 366 363 366 Independence A and B are independent events if Pr A B Pr A Pr A B Pr A Pr B A Pr B A Pr B B What about Pr A not B 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 A 1 A 2 A 3 are independent events if Pr A1 A2 Pr A1 Pr A2 A1 Pr A2 Pr A3 A1 Pr A3 Pr A1 A2 A3 Pr A1 Pr A2 A1 A3 Pr A2 Pr A3 A1 A2 Pr A3 Pr A1 A3 Pr A1 Pr A2 A3 Pr A2 Pr A3 A2 Pr A3 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 Pr A X Pr A for all A some Ai for all X a conjunction of any of the others e g A2 and A6 and A7 Silver and Gold One bag has two silver coins another has two gold coins and the third has one of each One of the three bags is selected at random Then one coin is selected at random from the two in the bag 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 Pr G1 1 2 Let G2 be the event that the second coin is gold 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 do Monty Hall problem Sample space prize behind door 1 prize behind door 2 prize behind door 3 Each has probability 1 3 Staying we win if we choose the correct door Pr choosing correct door 1 3 Switching we win if we choose the incorrect door Pr choosing incorrect door 2 3 why was this tricky We are inclined to think After one door is opened others are equally likely But his action is not independent of yours Now about that formidable tool 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 Hmm k k Pr exactly k letters end up in correct envelopes k k aargh On average in class of size m how many pairs of people will have the same birthday k k Pr exactly k collisions k k aargh The new tool is called Linearity of Expectation Expectatus Linearitus HMU Random Variable To use this new tool we will also need to understand the concept of a Random Variable Today s lecture not too much material but need to understand …
View Full Document
Unlocking...