6.042/18.] Mathematics for Computer Science April 22, 2005 Srini devadas and Eric Lehman Notes for recitation 18 The Law of Total Probability is a handy tool for breaking down the computation of a pro ability into distinct cases. More precisely, suppose we are interested in the probability of an event E: Pr(E). Suppose also that the random experiment can evolve in two different ways; that is, two different cases X and X are possible. Suppose also that it is easy to find the probability of each case: Pr(X)and Pr(X it easy to find the probability of the event in each case: Pr(E I X)and Pr(EI X) Then finding the probability of E is only two multiplications and an addition away Theorem 1(Law of Total Probability). Let e and X be events, and 0< Pr(x)<1. Then Pr(e) Pr(X)·Pr(E|X)+Pr(X)·Pr(E Proof. Let's simplify the right-hand side P(E|X)·Pr(X)+Pr(E|X)·Pr(X) Pr(E∩X) Pr(E∩X) Pr(X)+ E∩X)+Pr(E∩X) Pr(E) The first step uses the definition of conditional probability. On the next-to-last line, were adding the probabilities of all outcomes in E and X to the probabilities of all outcomes in E and not in X. Since every outcome in E is either in X or not in X, this is the sum of the probabilities of all outcomes in E, which equals Pr(E) What happens if the experiment can evolve in more than two different ways? That is, what if there are n cases, X1,..., Xn, which are mutually exclusive(no two cases can hap pen simultaneously) and collectively exhaustive (at least one case must happen? If it is still easy to find the probability of each case and the probability of the event in each case, then again finding Pr(E)is trivial Theorem 2. Let e be an event and let X1,..., Xn be disjoint events whose union exhausts the sample space. The P(E)=∑P(E|x)Pr(X) provided that Pr(X)≠0� � � � � � � � � � � � � � � 6.042/18.062J Mathematics for Computer Science April 22, 2005 Srini Devadas and Eric Lehman Notes for Recitation 18 The Law of Total Probability is a handy tool for breaking down the computation of a prob￾ability into distinct cases. More precisely, suppose we are interested in the probability of an event E: Pr (E). Suppose also that the random experiment can evolve in two different ways; that is, two different cases X and X are possible. Suppose also that • it is easy to find the probability of each case: Pr (X) and Pr X , • it easy to find the probability of the event in each case: Pr (E | X) and Pr E X | . Then finding the probability of E is only two multiplications and an addition away. Theorem 1 (Law of Total Probability). Let E and X be events, and 0 < Pr (X) < 1. Then Pr (E) = Pr (X) · Pr (E | X) + Pr X · Pr E | X Proof. Let’s simplify the right­hand side. Pr (E | X) · Pr (X) + Pr E X | · Pr X � � Pr E ∩ X � = Pr (E ∩ X) · Pr (X) + � � Pr � X Pr (X) Pr X · = Pr (E ∩ X) + Pr E ∩ X = Pr (E) The first step uses the definition of conditional probability. On the next­to­last line, we’re adding the probabilities of all outcomes in E and X to the probabilities of all outcomes in E and not in X. Since every outcome in E is either in X or not in X, this is the sum of the probabilities of all outcomes in E, which equals Pr (E). What happens if the experiment can evolve in more than two different ways? That is, what if there are n cases, X1, . . . , Xn, which are mutually exclusive (no two cases can hap￾pen simultaneously) and collectively exhaustive (at least one case must happen)? If it is still easy to find the probability of each case and the probability of the event in each case, then again finding Pr (E) is trivial. Theorem 2. Let E be an event and let X1, . . . , Xn be disjoint events whose union exhausts the sample space. Then n Pr (E) = Pr (E | Xi) · Pr (Xi) i=1 provided that Pr (Xi) =� 0