Language Of ProbabilityFinite Probability DistributionFinite Probability DistributionSample spaceProbabilityProbability DistributionEventsEventsEventsUniform DistributionMore Language Of Probability: ConditioningAnother way to calculate Birthday probability Pr(no collision)Independence!Independence!Independence!Monty Hall problemMonty Hall problemwhy was this tricky?Random VariableProbability DistributionFlip penny and nickel (unbiased)Flip penny and nickel (biased)Probability DistributionAn event is a subsetNew concept: Random VariablesRandom Variable: A measurement for an experimental outcomeE.g., tossing a fair coin n timesNotational conventionsTwo views of random variablesTwo coins tossedTwo views of random variablesTwo coins tossedTwo views of random variablesTwo diceIt’s a floor wax and a dessert toppingFrom Random Variables to EventsTwo coins tossedTwo diceFrom Random Variables to EventsFrom Events to Random VariablesDefinition: expectationThinking about expectationA quick calculation…Type checkingIndicator R.V.s: E[XA] = Pr(A)Adding Random VariablesAdding Random VariablesIndependenceLinearity of ExpectationLinearity of ExpectationLinearity of ExpectationLinearity of ExpectationBy inductionUse Linearity of ExpectationUse Linearity of ExpectationUse Linearity of ExpectationUse Linearity of ExpectationWhat about Products?But it is true if RVs are independentAnother problemStep right up…AnalysisAnalysisWhat’s going on?What’s going on?What’s going on?Great Theoretical Ideas In Computer ScienceJohn Lafferty CS 15-251 Fall 2006Lecture 10 Sept. 28, 2006 Carnegie Mellon University15-251ClassicsToday, we will learn about a formidable tool in probability that will allow us to solve problems that seem really really messy…Language Of ProbabilityThe formal language of probability is a very important tool in describing and analyzing probability distributions.Finite Probability DistributionA (finite) probability distribution D is a finite set Sof elements, where each element x in S has a positive real weight, proportion, or probability p(x). The weights must satisfy:Finite Probability DistributionA (finite) probability distribution D is a finite set Sof 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 spaceand elements x in S are called samples.Sample spaceA (finite) probability distribution D is a finite set Sof elements, where each element x in S has a positive real weight, proportion, or probability p(x). SSample spaceProbabilityA (finite) probability distribution D is a finite set Sof elements, where each element x in S has a positive real weight, proportion, or probability p(x). SxD(x) = p(x) = 0.2weight or probabilityof xProbability DistributionS0.20.130.060.110.170.10.1300.1weights must sum to 1A (finite) probability distribution D is a finite set Sof elements, where each element x in S has a positive real weight, proportion, or probability p(x).EventsA (finite) probability distribution D is a finite set Sof 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 isSEvent EEventsA (finite) probability distribution D is a finite set Sof elements, where each element x in S has a positive real weight, proportion, or probability p(x).S0.170.10.130PrD[E] = 0.4EventsA (finite) probability distribution D is a finite set Sof elements, where each element x in S has a positive real weight, proportion, or probability p(x).Uniform DistributionA (finite) probability distribution D is a finite set Sof 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.The probability of event A given event B is written Pr[ A | B ]and is defined to be = [][]PrPrABB∩More Language Of Probability: ConditioningΩABproportion of A ∩ Bto BSuppose we roll a whitedie and blackdie. What is the probability that the white is 1 given that the total is 7?event A = {white die = 1}event B = {total = 7}event A = {white die = 1}event B = {total = 7}Sample space S = { (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) }|A ∩ B| = Pr[A | B] = Pr[A ∩ B] = 1/36|B| Pr[B] 1/6This way does not care about the distribution.Can do this because Ωis uniformly distributed.Pr[A | B]Another way to calculate Birthday probability Pr(no collision)Pr(1stperson doesn’t collide) = 1.Pr(2nddoesn’t | no collisions yet) = 365/366.Pr(3rddoesn’t | no collisions yet) = 364/366.Pr(4thdoesn’t | no collisions yet) = 363/366.…Pr(23rddoesn’t| no collisions yet) = 344/366.1365/366364/366363/366Independence!A and B are independent events ifÅAÆÅBÆPr[ A | B ] = Pr[ A ]⇔Pr[ A ∩ B ] = Pr[ A ] Pr[ B ]⇔Pr[ B | A ] = Pr[ B ]What about Pr[ A | not(B) ] ?Independence!A1, A2, …, Akare independent events if knowingif some of them occurred does not change the probability of any of the others occurring.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., {A_1, A_2, A_3}are independent events if:Independence!A1, A2, …, Akare independent events if knowingif some of them occurred does not change the probability of any of the others occurring.Pr[A|X] = Pr[A]for all A = some Aifor all X = a conjunction of any of theothers (e.g., A2and A6and A7)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?Silver and GoldLet G1be the event that the first coin is gold.Pr[G1] = 1/2Let G2be the event that the second coin is gold.Pr[G2| G1] = Pr[G1and G2] / Pr[G1]= (1/3) / (1/2)= 2/3Note: G1and G2are not independent.Monty Hall problem•Announcer hides prize behind one of 3 doors at random.•You select some door.•Announcer opens
View Full Document