6.042/18.] Mathematics for Computer Science April 26, 2005 Srini devadas and Eric Lehman Lecture notes Independence 1 Independent events Suppose that we flip two fair coins simultaneously on opposite sides of a room. Intu- itively the way one coin lands does not affect the way the other coin lands. The mathe- matical concept that captures this intuition is called independence. In particular, events A and B are independent if and only if Pr(A∩B)=Pr(A)·Pr(B Generally, independence is something you assume in modeling a phenomenon-or wish you could realistically assume. Many useful probability formulas only hold if certain events are independent, so a dash of independence can greatly simplify the analysis of a 1.1 Examples Let's return to the experiment of flipping two fair coins. Let A be the event that the first coin comes up heads, and let b be the event that the second coin is heads. If we assume that a and B are independent, then the probability that both coins come up heads is e Pr(A∩B)=Pr(A)·Pr(B) 11 On the other hand, let C be the event that tomorrow is cloudy and r be the event that omorrow is rainy. Perhaps Pr(C)=1 5 and Pr(r)=1/10 around here. If these events were independent, then we could conclude that the probability of a rainy, cloudy day was quite small Pr(R∩C)=Pr(B)·Pr(C) 11 Unfortunately, these events are definitely not independent; in particular, is cloudy. Thus, the probability of a rainy, cloudy day is actually 1/10
6.042/18.062J Mathematics for Computer Science April 26, 2005 Srini Devadas and Eric Lehman Lecture Notes Independence 1 Independent Events Suppose that we flip two fair coins simultaneously on opposite sides of a room. Intuitively, the way one coin lands does not affect the way the other coin lands. The mathematical concept that captures this intuition is called independence. In particular, events A and B are independent if and only if: Pr (A ∩ B) = Pr (A) · Pr (B) Generally, independence is something you assume in modeling a phenomenon— or wish you could realistically assume. Many useful probability formulas only hold if certain events are independent, so a dash of independence can greatly simplify the analysis of a system. 1.1 Examples Let’s return to the experiment of flipping two fair coins. Let A be the event that the first coin comes up heads, and let B be the event that the second coin is heads. If we assume that A and B are independent, then the probability that both coins come up heads is: Pr (A ∩ B) = Pr (A) · Pr (B) 1 1 = 2 · 2 1 = 4 On the other hand, let C be the event that tomorrow is cloudy and R be the event that tomorrow is rainy. Perhaps Pr (C) = 1/5 and Pr (R) = 1/10 around here. If these events were independent, then we could conclude that the probability of a rainy, cloudy day was quite small: Pr (R ∩ C) = Pr (R) · Pr (C) 1 1 = 5 · 10 1 = 50 Unfortunately, these events are definitely not independent; in particular, every rainy day is cloudy. Thus, the probability of a rainy, cloudy day is actually 1/10
2 1.2 Working with Independence There is another way to think about independence that you may find more intuitive According to the definition, events a and b are independent if and only if: Pr(A∩B)=Pr(A)Pr(B) The equation on the left always holds if Pr(B)=0. Otherwise, we can divide both sides by Pr(B) and use the definition of conditional probability to obtain an alternative definition of independence Pr(a b)=Pr(a) or Pr (B)=0 This equation says that events A and B are independent if the probability of A is unaf- fected by the fact that B happens. In these terms, the two coin tosses of the previous section were independent, because the probability that one coin comes up heads is un affected by the fact that the other came up heads. turning to our other example, the probability of clouds in the sky is strongly affected by the fact that it is raining. So, as we noted before, these events are not independent. 1.3 Some intuition Suppose that A and B are disjoint events, as shown in the figure below. Are these events independent? Let's check. On one hand, we know Pr(A∩B)=0 because an b contains no outcomes On the other hand we have Pr(4)·Pr(B)>0 except in degenerate cases where A or B has zero probability. Thus, disjointness and inde- pendence are very different ideas Here's a better mental picture of what independent events look like
2 Independence 1.2 Working with Independence There is another way to think about independence that you may find more intuitive. According to the definition, events A and B are independent if and only if: Pr (A ∩ B) = Pr (A) · Pr (B). The equation on the left always holds if Pr (B) = 0. Otherwise, we can divide both sides by Pr (B) and use the definition of conditional probability to obtain an alternative definition of independence: Pr (A | B) = Pr (A) or Pr (B) = 0 This equation says that events A and B are independent if the probability of A is unaffected by the fact that B happens. In these terms, the two coin tosses of the previous section were independent, because the probability that one coin comes up heads is unaffected by the fact that the other came up heads. Turning to our other example, the probability of clouds in the sky is strongly affected by the fact that it is raining. So, as we noted before, these events are not independent. 1.3 Some Intuition Suppose that A and B are disjoint events, as shown in the figure below. A B Are these events independent? Let’s check. On one hand, we know Pr (A ∩ B) = 0 because A ∩ B contains no outcomes. On the other hand, we have Pr (A) · Pr (B) > 0 except in degenerate cases where A or B has zero probability. Thus, disjointness and independence are very different ideas. Here’s a better mental picture of what independent events look like
A B The sample space is the whole rectangle. Event A is a vertical stripe, and event B is a horizontal stripe. Assume that the probability of each event is proportional to its area in the diagram. Now if A covers an a-fraction of the sample space, and B covers a B-fraction then the area of the intersection region is a. B In terms of probability Pr(A∩B)=Pr(A)·Pr(B) 1.4 An Experiment with Two Coins Suppose that we flip two independent, fair coins. Consider the following two events a= the coins match(both are heads or both are tails) b= the first coin is heads Are these independent events? Intuitively, the answer is"no". After all, whether or not the coins match depends on how the first coin comes up; if we toss HH, they match, but if we toss TH, then they do not. However, the mathematical definition of independence does not correspond perfectly to the intuitive notion of"unrelated"or"unconnected These events actually are independent! Claim 1. Events A and B are independent Proof. We must show that Pr(An B)=Pr(A)- Pr(B) Step 1: Find the Sample Space. As shown in the tree diagram below, there are four possible outcomes: HH, HT, TH, and TT
Independence 3 ✁✁✁✁ ✁✁✁✁ ✁✁✁✁ ✁✁✁✁ ✁✁✁✁ ✁✁✁✁ ✁✁✁✁ ✂✁✂✁✂✁✂✁✂ ✂✁✂✁✂✁✂✁✂ ✂✁✂✁✂✁✂✁✂ ✂✁✂✁✂✁✂✁✂ ✂✁✂✁✂✁✂✁✂ ✂✁✂✁✂✁✂✁✂ ✂✁✂✁✂✁✂✁✂ ✄✁✄✁✄✁✄✁✄✁✄✁✄✁✄✁✄✁✄✁✄✁✄ ☎✁☎✁☎✁☎✁☎✁☎✁☎✁☎✁☎✁☎✁☎✁☎ ☎✁☎✁☎✁☎✁☎✁☎✁☎✁☎✁☎✁☎✁☎✁☎ ✆✁✆✁✆✁✆✁✆ ✆✁✆✁✆✁✆✁✆ ✝✁✝✁✝✁✝✁✝ ✝✁✝✁✝✁✝✁✝ A B The sample space is the whole rectangle. Event A is a vertical stripe, and event B is a horizontal stripe. Assume that the probability of each event is proportional to its area in the diagram. Now if A covers an αfraction of the sample space, and B covers a βfraction, then the area of the intersection region is α β· . In terms of probability: Pr (A ∩ B) = Pr (A) · Pr (B) 1.4 An Experiment with Two Coins Suppose that we flip two independent, fair coins. Consider the following two events: A = the coins match (both are heads or both are tails) B = the first coin is heads Are these independent events? Intuitively, the answer is “no”. After all, whether or not the coins match depends on how the first coin comes up; if we toss HH, they match, but if we toss T H, then they do not. However, the mathematical definition of independence does not correspond perfectly to the intuitive notion of “unrelated” or “unconnected”. These events actually are independent! Claim 1. Events A and B are independent. Proof. We must show that Pr(A ∩ B) = Pr(A) · Pr(B). Step 1: Find the Sample Space. As shown in the tree diagram below, there are four possible outcomes: HH, HT, T H, and T T
H12°H14 1/2°HT TH1/4 1/2 probability event A vent B event coin coin2 col A∩B? Step 2: Define Events of Interest. The outcomes in event A(coins match) and event B (first coin is heads) are checked in the tree diagram above Step 3: Compute Outcome Probabilities. Since the coins are independent and fair, all edge probabilities are 1/2. We find outcome probabilities by multiplying edge probabili ties along each root-to-leaf path. All outcomes have probability 1/4 Step 4: Compute Event Probabilities. Now we can verify that Pr(AnB)= Pr(a) Pr(B) 1 P(4)=Pr(HH)+Pr(Tn)=4+4=2 Pr(B)=Pr(HH)+Pr(HT) P(4∩B)=P(HH)=4 Therefore, a and b are independent events as claimed 1.5 A Variation of the Two-Coin Experiment Suppose that we alter the preceding experiment so that the coins are independent, but not fair. In particular, suppose each coin is heads with probability p and tails with probability 1-p where p might not be 1 /2. As before, let a be the event that the coins match, and let B the event that the first coin is heads. Are events A and b independent for all values of The problem is worked out in the tree diagram below
4 Independence T H H H T 1/2 T 1/2 1/2 1/2 1/2 1/2 TT TH HT HH probability coin 1 coin2 event A: coins match? event B: 1st coin heads? 1/4 1/4 1/4 1/4 event A B? Step 2: Define Events of Interest. The outcomes in event A (coins match) and event B (first coin is heads) are checked in the tree diagram above Step 3: Compute Outcome Probabilities. Since the coins are independent and fair, all edge probabilities are 1/2. We find outcome probabilities by multiplying edge probabilities along each roottoleaf path. All outcomes have probability 1/4. Step 4: Compute Event Probabilities. Now we can verify that Pr (A ∩ B) = Pr (A) · Pr (B): 1 1 1 Pr(A) = Pr(HH) + Pr(T T) = + = 4 4 2 1 1 1 Pr(B) = Pr(HH) + Pr(HT) = + = 4 4 2 1 Pr(A ∩ B) = Pr(HH) = 4 Therefore, A and B are independent events as claimed. 1.5 A Variation of the TwoCoin Experiment Suppose that we alter the preceding experiment so that the coins are independent, but not fair. In particular, suppose each coin is heads with probability p and tails with probability 1 − p where p might not be 1/2. As before, let A be the event that the coins match, and let B the event that the first coin is heads. Are events A and B independent for all values of p? The problem is worked out in the tree diagram below
hT P(I-P) 、pTHp(l-p) 1 coin 1 probability even event coin 2 coin Ist coin A∩B? match? heads We can read event probabilities off the tree diagram Pr(4)=Pr(HH)+Pr(TT)=p2+(1-p)2=2p2-2p+1 Pr(B)=Pr(HH)+Pr(hT)=p+p(1-p)=p Pr(A∩B)=Pr(HH)=p2 Now events A and B are independent if and only if Pr(An B)= Pr(A)- Pr(B)or, equiv- alently (2p2-2p+1)·p=p2 Since both sides are multiples of p, one solution is p=0. Dividing both sides by p and simplifying leaves a quadratic equation 2p2-3p+1=0 According to the quadratic formula, the remaining solutions are p= l and p= 1/2 This analysis shows that events A and B are independent only if the coins are either fair or completely biased toward either heads or tails. Evidently, there was some dependence lurking at the fringes of the previous problem, but it was kept at bay because the coins The Ultimate Application Surprisingly, this has an application to Ultimate Frisbee. Here is an excerpt from the Tenth Edition rules
� � Independence 5 T H H H T T TT TH HT HH probability event A: coins match? event B: 1st coin heads? event A B? p p p 1-p 1-p 1-p (1-p) 2 p(1-p) p(1-p) p 2 coin 2 coin 1 We can read event probabilities off the tree diagram: 2 Pr (A) = Pr (HH) + Pr (T T) = p 2 + (1 − p) 2 = 2p − 2p + 1 Pr (B) = Pr (HH) + Pr (HT) = p 2 + p(1 − p) = p Pr (A ∩ B) = Pr (HH) = p 2 Now events A and B are independent if and only if Pr (A ∩ B) = Pr (A)·Pr (B) or, equivalently: 2 2p 2 − 2p + 1 = · p p Since both sides are multiples of p, one solution is p = 0. Dividing both sides by p and simplifying leaves a quadratic equation: 2p 2 − 3p + 1 = 0 According to the quadratic formula, the remaining solutions are p = 1 and p = 1/2. This analysis shows that events A and B are independent only if the coins are either fair or completely biased toward either heads or tails. Evidently, there was some dependence lurking at the fringes of the previous problem, but it was kept at bay because the coins were fair! The Ultimate Application Surprisingly, this has an application to Ultimate Frisbee. Here is an excerpt from the Tenth Edition rules: