Course Notes, Week 13: Random Variables, Distributions and Expectation

Massachusetts Institute of Technology 6.042J/18.062J, Fall ’05: Mathematics for Computer Science Prof. Albert R. Meyer and Prof. Ronitt Rubinfeld Course Notes, Week 13 November 28 revised December 6, 2005, 1407 minutes Random Variables, Distributions and Expectation 1 Random Variables We’ve used probablity to model a variety of experiments, games, and tests. Throughout, we have tried to compute probabilities of events. We asked, for example, what is the probability of the event that you win the Monty Hall game? What is the probability of the event that it rains, given that the weatherman carried his umbrella today? What is the probability of the event that you have a rare disease, given that you tested positive? But one can ask more general questions about an experiment. How hard will it rain? How long will this illness last? How much will I lose playing 6.042 games all day? These ques­ tions are fundamentally different and not easily phrased in terms of events. The problem is that an event either does or does not happen: you win or lose, it rains or doesn’t, you’re sick or not. But these questions are about matters of degree: how much, how hard, how long? To approach these questions, we need a new mathematical tool. 1.1 Definition Let’s begin with an example. Consider the experiment of tossing three independent, un­ biased coins. Let C be the number of heads that appear. Let M = 1 if the three coins come up all heads or all tails, and let M = 0 otherwise. Now every outcome of the three coin flips uniquely determines the values of C and M . For example, if we flip heads, tails, heads, then C = 2 and M = 0. If we flip tails, tails, tails, then C = 0 and M = 1. In effect, C counts the number of heads, and M indicates whether all the coins match. Since each outcome uniquely determines C and M , we can regard them as functions map­ ping outcomes to numbers. For this experiment, the sample space is: S = {HHH, HHT, HT H, HT T, T HH, T HT, T T H, T T T } . Now C is a function that maps each outcome in the sample space to a number as follows: C(HHH) C(HHT ) C(HT H) C(HT T ) = = = = 3 2 2 1 C(T HH) C(T HT ) C(T T H) C(T T T ) = = = = Copyright © 2005, Prof. Albert R. Meyer and Prof. Ronitt Rubinfeld. 2 1 1 0. 2 Course Notes, Week 13: Random Variables, Distributions and Expectation Similarly, M is a function mapping each outcome another way: M (HHH) M (HHT ) M (HT H) M (HT T ) = = = = 1 0 0 0 M (T HH) M (T HT ) M (T T H) M (T T T ) = = = = 0 0 0 1. The functions C and M are examples of random variables. In general, a random variable is a function whose domain is the sample space. (The codomain can be anything, but we’ll usually use a subset of the real numbers.) Notice that the name “random variable” is a misnomer; random variables are actually functions! 1.2 Indicator Random Variables An indicator random variable (or simply an indicator, or a Bernoulli random variable) is a random variable that maps every outcome to either 0 or 1. The random variable M is an example. If all three coins match, then M = 1; otherwise, M = 0. Indicator random variables are closely related to events. In particular, an indicator parti­ tions the sample space into those outcomes mapped to 1 and those outcomes mapped to 0. For example, the indicator M partitions the sample space into two blocks as follows: HHH �� T T T� � M =1 HHT � HT H HT T �� T HH T HT M =0 T T H� . In the same way, an event partitions the sample space into those outcomes in the event and those outcomes not in the event. Therefore, each event is naturally associated with a certain indicator random variable and vice versa: an indicator for an event E is an indicator random variable that is 1 for all outcomes in E and 0 for all outcomes not in E. Thus, M is an indicator random variable for the event that all three coins match. 1.3 Random Variables and Events There is a strong relationship between events and more general random variables as well. A random variable that takes on several values partitions the sample space into several blocks. For example, C partitions the sample space as follows: T T T� � �� C=0 T � TH T �� HT C=1 HT T� �T HH HT ��H C=2 HHT� �HHH �� � . C=3 Each block is a subset of the sample space and is therefore an event. Thus, we can regard an equation or inequality involving a random variable as an event. For example, the event that C = 2 consists of the outcomes T HH, HT H, and HHT . The event C ≤ 1 consists of the outcomes T T T , T T H, T HT , and HT T . Course Notes, Week 13: Random Variables, Distributions and Expectation 3 Naturally enough, we can talk about the probability of events defined by equations in­ volving random variables. For example: Pr {C = 2} = Pr {T HH} + Pr {HT H} + Pr {HHT } 1 1 1 = + + 8 8 8 3 = . 8 As another example: Pr {M = 1} = Pr {T T T } + Pr {HHH} 1 1 = + 8 8 1 = . 4 1.4 Conditional Probability Mixing conditional probabilities and events involving random variables creates no new difficulties. For example, Pr {C ≥ 2 | M = 0} is the probability that at least two coins are heads (C ≥ 2), given that not all three coins are the same (M = 0). We can compute this probability using the definition of conditional probability: Pr {[C ≥ 2] ∩ [M = 0]} Pr {M = 0} Pr {{T HH, HT H, HHT }} = Pr {{T HH, HT H, HHT, HT T, T HT, T T H}} 3/8 = 6/8 1 = . 2 Pr {C ≥ 2 | M = 0} = The expression [C ≥ 2] ∩ [M = 0] on the first line may look odd; what is the set operation ∩ doing between an inequality and an equality? But recall that, in this context, [C ≥ 2] and [M = 0] are events, namely, sets of outcomes. 1.5 Independence The notion of independence carries over from events to random variables as well. Ran­ dom variables R1 and R2 are independent if for all x1 in the codomain of R1 , and x2 in the codomain of R2 , we have: Pr {[R1 = x1 ] ∩ [R2 = x2 ]} = Pr {R1 = x1 } · Pr {R2 = x2 } . 4 Course Notes, Week 13: Random Variables, Distributions and Expectation As with events, we can formulate independence for random variables in an equivalent and perhaps more intuitive way: random variables R1 and R2 are independent if for all x1 and x2 in the codomains of R1 and R2 respectively, such that Pr {R2 = x2 } > 0, we have: Pr {R1 = x1 | R2 = x2 } = Pr {R1 = x1 } . In words: the probability that R1 takes on a particular value is unaffected by the value of R2 . As an example, are C and M independent? Intuitively, the answer should be “no”. The number of heads, C, completely determines whether all three coins match; that is, whether M = 1. But, to verify this intuition, we must find some x1 , x2 ∈ R such that: Pr {[C = x1 ] ∩ [M = x2 }] = � Pr {C = x1 } · Pr {M = x2 } . One appropriate choice of values is x1 = 2 and x2 = 1. In this case, we have: Pr {[C = 2] ∩ [M = 1]} = 0 but Pr {C = 2} · Pr {M = 1} = 3 1 · = � 0. 8 4 The first probability is zero because we never have exactly two heads (C = 2) when all three coins match (M = 1). The other two probabilities were computed earlier. The notion of independence generalizes to a set of random variables as follows. Random variables R1 , R2 , . . . , Rn are mutually independent if for all x1 , x2 , . . . , xn , in the codomains of R1 , R2 , . . . , Rn respectively, we have: Pr {[R1 = x1 ] ∩ [R2 = x2 ] ∩ · · · ∩ [Rn = xn ]} = Pr {R1 = x1 } · Pr {R2 = x2 } · · · Pr {Rn = xn } . A consequence of this definition of mutual independence is that the probability that any subset of the variables takes a particular set of values is equal to the product of the proba­ bilites that the individual variables take their values. Thus, for example, if R1 , R2 , . . . , R100 are mutually independent random variables, then it follows that: Pr {[R1 = 7] ∩ [R7 = 9.1] ∩ [R23 = π]} = Pr {R1 = 7} · Pr {R7 = 9.1} · Pr {R23 = π} . 2 The Birthday Principle There are 100 students in a lecture hall. What is the probability that some two people share a birthday? Maybe about 1/3? Let’s check! We’ll use the following two variables throughout our analysis: • Let n be the number of people in the group. • Let d be the number of days in the year. Course Notes, Week 13: Random Variables, Distributions and Expectation 5 Furthermore, we’ll make the assumption that birthdays are uniformly­distributed, inde­ pendent random variables. This assumption is not really valid in the real world, since more babies are born at certain times of year and the birthdays of twins are clearly not independent. However, our analysis of this problem applies to many situations in com­ puter science that are unaffected by twins, leap days, and romantic holidays anyway, so we won’t dwell on those complications. The sample space for this experiment consists of all ways of assigning birthdays to the people of the group. There are dn such assignments, since the first person can have d different birthdays, the second person can have d different birthdays, and so forth. Fur­ thermore, every such assignment is equally probable by our assumption that birthdays are uniformly­distributed and mutually independent, so the sample space is uniform. Let D be the event that everyone has a distinct birthday. This is the complement of the event that we’re interested in, but the probability of D is easier to evaluate. Later we can � � use the fact that Pr D = 1−Pr {D} to compute the probability we really want. Anyway, event D consists of d(d − 1)(d − 2) · · · (d − n + 1) outcomes, since we can select the birthday of the first person in d days, the birthday of the second person in d − 1 ways, and so forth. Therefore, the probability that everyone has a different birthday is: Pr {D} = d(d − 1)(d − 2) · · · (d − n + 1) . dn For n = 100, this probability is actually fantastically small —less than one in a million! If there are 100 people in a room, two are almost certain to share a birthday. Let’s use an approximation to rewrite the right side of the preceding equation in a more insightful form: � �� �� � � � 2 n−1 0 1 ··· 1 − 1− 1− Pr {D} = 1 − d d d d ≈ e0 · e−1/d · e−2/d · · · e−(n−1)/d =e −n(n−1) 2d . In the first step, we pair each term in the numerator with a d term in the denominator. Next, we use the approximation e−x ≈ 1 − x, which is pretty accurate when x is small.1 In the last step, we combine exponents using the familiar formula 0 + 1 + 2 + · · · + (n − 1) = n(n − 1)/2. √ The exponent in the final expression above is −1 when n ≈ 2d. This is roughly the break­ even point, where the probability that two people share a birthday is in the ballpark of 1/2. This leads to a rule called the birthday principle, which is useful in many contexts in computer science: √ If there are d days in a year and 2d people in a room, then the probability that two share a birthday is about 1 − 1/e ≈ 0.632. 1 This approximation is obtained by truncating the Taylor series e−x = 1 − x + x2 /2! − x3 /3! + · · · 6 Course Notes, Week 13: Random Variables, Distributions and Expectation √ For example, this principle says that if you have 2 · 365 ≈ 27 people in a room, then the probability that two share a birthday is about 0.632. The actual probability is about 0.626, so the approximation is quite good. The Birthday Principle is a great rule of thumb with surprisingly many applications. For example, cryptographic systems and digital signature schemes must be hardened against “birthday attacks”. The principle also tells us how many items can be inserted into a hash table before one starts to experience collisions. 3 Probability Distributions A random variable is defined to be a function whose domain is the sample space of an experiment. Often, however, random variables with essentially the same properties show up in completely different experiments. For example, some random variable that come up in polling, in primality testing, and in coin flipping all share some common properties. If we could study such random variables in the abstract, divorced from the details any particular experiment, then our conclusions would apply to all the experiments where that sort of random variable turned up. Such general conclusions could be very useful. There are a couple tools that capture the essential properties of a random variable, but leave other details of the associated experiment behind. The probability density function (pdf) for a random variable R with codomain V is a function PDFR : V → [0, 1] defined by: PDFR (x) = Pr {R = x} A consequence of this definition is that � PDFR (x) = 1 x∈V since the random variable always takes on exactly one value in the set V . As an example, let’s return to the experiment of rolling two fair, independent dice. As before, let T be the total of the two rolls. This random variable takes on values in the set V = {2, 3, . . . , 12}. A plot of the probability density function is shown below: 6/36 6 PDFR (x) 3/36 - 2 3 4 5 6 7 8 x∈V 9 10 11 12 Course Notes, Week 13: Random Variables, Distributions and Expectation 7 The lump in the middle indicates that sums close to 7 are the most likely. The total area of all the rectangles is 1 since the dice must take on exactly one of the sums in V = {2, 3, . . . , 12}. A closely­related idea is the cumulative distribution function (cdf) for a random variable R. This is a function CDFR : V → [0, 1] defined by: CDFR (x) = Pr {R ≤ x} As an example, the cumulative distribution function for the random variable T is shown below: 1 6 CDFR (x) 1/2 0 - 2 3 4 5 6 7 8 9 10 11 12 x∈V The height of the i­th bar in the cumulative distribution function is equal to the sum of the heights of the leftmost i bars in the probability density function. This follows from the definitions of pdf and cdf: CDFR (x) = Pr {R ≤ x} � = Pr {R = y} y≤x = � PDFR (y) y≤x In summary, PDFR (x) measures the probability that R = x and CDFR (x) measures the probability that R ≤ x. Both the PDFR and CDFR capture the same information about the random variable R— you can derive one from the other— but sometimes one is more convenient. The key point here is that neither the probability density function nor the cu­ mulative distribution function involves the sample space of an experiment. Thus, through these functions, we can study random variables without reference to a particular experi­ ment. We’ll now look at three important distributions and some applications. 8 Course Notes, Week 13: Random Variables, Distributions and Expectation 3.1 Bernoulli Distribution Indicator random variables are perhaps the most common type because of their close association with events. The probability density function of an indicator random variable B is always PDFB (0) = p PDFB (1) = 1 − p where 0 ≤ p ≤ 1. The corresponding cumulative distribution function is: CDFB (0) = p CDFB (1) = 1 3.2 Uniform Distribution A random variable that takes on each possible value with the same probability is called uniform. For example, the probability density function of a random variable U that is uniform on the set {1, 2, . . . , N } is: PDFU (k) = 1 N And the cumulative distribution function is: CDFU (k) = k N Uniform distributions come up all the time. For example, the number rolled on a fair die is uniform on the set {1, 2, . . . , 6}. 3.3 The Numbers Game Let’s play a game! I have two envelopes. Each contains an integer in the range 0, 1, . . . , 100, and the numbers are distinct. To win the game, you must determine which envelope con­ tains the larger number. To give you a fighting chance, I’ll let you peek at the number in one envelope selected at random. Can you devise a strategy that gives you a better than 50% chance of winning? For example, you could just pick an evelope at random and guess that it contains the larger number. But this strategy wins only 50% of the time. Your challenge is to do better. So you might try to be more clever. Suppose you peek in the left envelope and see the number 12. Since 12 is a small number, you might guess that that other number is larger. Course Notes, Week 13: Random Variables, Distributions and Expectation 9 But perhaps I’m sort of tricky and put small numbers in both envelopes. Then your guess might not be so good! An important point here is that the numbers in the envelopes may not be random. I’m picking the numbers and I’m choosing them in a way that I think will defeat your guess­ ing strategy. I’ll only use randomization to choose the numbers if that serves my end: making you lose! 3.3.1 Intuition Behind the Winning Strategy Amazingly, there is a strategy that wins more than 50% of the time, regardless of what numbers I put in the envelopes! Suppose that you somehow knew a number x between my lower number and higher num­ bers. Now you peek in an envelope and see one or the other. If it is bigger than x, then you know you’re peeking at the higher number. If it is smaller than x, then you’re peek­ ing at the lower number. In other words, if you know an number x between my lower and higher numbers, then you are certain to win the game. The only flaw with this brilliant strategy is that you do not know x. Oh well. But what if you try to guess x? There is some probability that you guess correctly. In this case, you win 100% of the time. On the other hand, if you guess incorrectly, then you’re no worse off than before; your chance of winning is still 50%. Combining these two cases, your overall chance of winning is better than 50%! Informal arguments about probability, like this one, often sound plausible, but do not hold up under close scrutiny. In contrast, this argument sounds completely implausible— but is actually correct! 3.3.2 Analysis of the Winning Strategy For generality, suppose that I can choose numbers from the set {0, 1, . . . , n}. Call the lower number L and the higher number H. Your goal is to guess a number x between L and H. you select x at random from among the half­integers: � 1 1 1 , 1 , 2 , ..., n − 2 2 2 To avoid confusing equality cases, 1 2 � But what probability distribution should you use? The uniform distribution turns out to be your best bet. An informal justification is that if I figured out that you were unlikely to pick some number— say 50 12 — then I’d always put 50 and 51 in the evelopes. Then you’d be unlikely to pick an x between L and H and would have less chance of winning. 10 Course Notes, Week 13: Random Variables, Distributions and Expectation After you’ve selected the number x, you peek into an envelope and see some number p. If p > x, then you guess that you’re looking at the larger number. If p < x, then you guess that the other number is larger. All that remains is to determine the probability that this strategy succeeds. We can do this with the usual four­step method and a tree diagram. Step 1: Find the sample space. You either choose x too low (< L), too high (> H), or just right (L < x < H). Then you either peek at the lower number (p = L) or the higher number (p = H). This gives a total of six possible outcomes. # peeked at choice of x 1/2 p=L p=H L/n 1/2 x too low x just right 1/2 p=L result probability lose L/2n win L/2n win (H−L)/2n win (H−L)/2n win (n−H)/2n lose (n−H)/2n p=H (H−L)/n 1/2 x too high 1/2 p=L (n−H)/n p=H 1/2 Step 2: Define events of interest. marked in the tree diagram. The four outcomes in the event that you win are Step 3: Assign outcome probabilities. First, we assign edge probabilities. Your guess x is too low with probability L/n, too high with probability (n − H)/n, and just right with probability (H − L)/n. Next, you peek at either the lower or higher number with equal probability. Multiplying along root­to­leaf paths gives the outcome probabilities. Step 4: Compute event probabilities. The probability of the event that you win is the sum of the probabilities of the four outcomes in that event: L H −L H −L n−H + + + 2n 2n 2n 2n 1 H −L = + 2 2n 1 1 ≥ + 2 2n Pr {win} = The final inequality relies on the fact that the higher number H is at least 1 greater than the lower number L since they are required to be distinct. Sure enough, you win with this strategy more than half the time, regardless of the num­ bers in the envelopes! For example, if I choose numbers in the range 0, 1, . . . , 100, then Course Notes, Week 13: Random Variables, Distributions and Expectation 11 1 you win with probability at least 12 + 200 = 50.5%. Even better, if I’m allowed only num­ bers in the range 0, . . . , 10, then your probability of winning rises to 55%! By Las Vegas standards, those are great odds! 3.4 Binomial Distribution Of the more complex distributions, the binomial distribution is surely the most impor­ tant in computer science. The standard example of a random variable with a binomial distribution is the number of heads that come up in n independent flips of a coin; call this random variable H. If the coin is fair, then H has an unbiased binomial density function: � � n −n PDFH (k) = 2 k � � This follows because there are nk sequences of n coin tosses with exactly k heads, and each such sequence has probability 2−n . Here is a plot of the unbiased probability density function PDFH (k) corresponding to n = 20 coins flips. The most likely outcome is k = 10 heads, and the probability falls off rapidly for larger and smaller values of k. These falloff regions to the left and right of the main hump are usually called the tails of the distribution. 0.18 0.16 0.14 0.12 0.1 0.08 0.06 0.04 0.02 0 0 5 10 15 20 An enormous number of analyses in computer science come down to proving that the tails of the binomial and similar distributions are very small. In the context of a prob­ lem, this typically means that there is very small probability that something bad happens, which could be a server or communication link overloading or a randomized algorithm running for an exceptionally long time or producing the wrong result. 12 3.4.1 Course Notes, Week 13: Random Variables, Distributions and Expectation The General Binomial Distribution Now let J be the number of heads that come up on n independent coins, each of which is heads with probability p. Then J has a general binomial density function: � � n k PDFJ (k) = p (1 − p)n−k k �n� As before, there are k sequences with k heads and n − k tails, but now the probability of each such sequence is pk (1 − p)n−k . As an example, the plot below shows the probability density function PDFJ (k) corre­ sponding to flipping n = 20 independent coins that are heads with probabilty p = 0.75. The graph shows that we are most likely to get around k = 15 heads, as you might expect. Once again, the probability falls off quickly for larger and smaller values of k. 0.25 0.2 0.15 0.1 0.05 0 0 3.4.2 5 10 15 20 Approximating the Binomial Density Function There is an approximate closed­form formula for the general binomial density function, though it�is�a bit unwieldy. First, we need an approximation for a key term in the exact formula, nk . For convenience, let’s replace k by αn where α is a number between 0 and 1. Then, from Stirling’s formula, we find that: � � n 2nH(α) ≤� αn 2πα(1 − α)n where H(α) is the famous entropy function: H(α) ::= α log2 1 1 + (1 − α) log2 α 1−α Course Notes, Week 13: Random Variables, Distributions and Expectation �n� This upper bound on αn is very tight and serves as an excellent approximation. 13 Now let’s plug this formula into the general binomial density function. The probability of flipping αn heads in n tosses of a coin that comes up heads with probability p is: 2nH(α) · pαn (1 − p)(1−α)n PDFJ (αn) ≤ � 2πα(1 − α)n (1) This formula is ugly as a bowling shoe, but quite useful. For example, suppose we flip a fair coin n times. What is the probability of getting exactly 21 n heads? Plugging α = 1/2 and p = 1/2 into this formula gives: 2nH(1/2) PDFJ (αn) ≤ � · 2−n 2π(1/2)(1 − (1/2))n � 2 = πn Thus, for example, √ if we flip a fair coin 100 times, the probability of getting exactly 50 heads is about 1/ 50π ≈ 0.079 or around 8%. 3.5 Approximating the Cumulative Binomial Distribution Function Suppose a coin comes up heads with probability p. As before, let the random variable J be the number of heads that come up on n independent flips. Then the probability of getting at most k heads is given by the cumulative binomial distribution function: CDFJ (k) = Pr {J ≤ k} = = k � PDFJ (i) i=0 k � � i=0 � n i p (1 − p)n−i i Evaluating this expression directly would be a lot of work for large k and n, so now an approximation would be really helpful. Once again, we can let k = αn; that is, instead of thinking of the absolute number of heads (k), we consider the fraction of flips that are heads (α). The following approximation holds provided α < p: 1−α · PDFJ (αn) 1 − α/p 1−α 2nH(α) ·� · pαn (1 − p)(1−α)n ≤ 1 − α/p 2πα(1 − α)n CDFJ (αn) ≤ 14 Course Notes, Week 13: Random Variables, Distributions and Expectation In the first step, we upper bound the summmation with a geometric sum and apply the formula for the sum of a geometric series. (The details are dull and omitted.) Then we insert the approximate formula (1) for PDFJ (αn) from the preceding section. You have to press a lot of buttons on a calculator to evaluate this formula for a specific choice of α, p, and n. (Even computing H(α) is a fair amount of work!) But for large n, evaluating the cumulative distribution function exactly requires vastly more work! So don’t look gift blessings in the mouth before they hatch. Or something. As an example, the probability of flipping at most 25 heads in 100 tosses of a fair coin is obtained by setting α = 1/4, p = 1/2 and n = 100: CDFJ �n� 4 �n� 3 1 − (1/4) ≤ · PDFJ ≤ · 1.913 · 10−7 . 1 − (1/4)/(1/2) 4 2 This says that flipping 25 or fewer heads is extremely unlikely, which is consistent with our earlier claim that the tails of the binomial distribution are very small. In fact, notice that the probability of flipping 25 or fewer heads is only 50% more than the probability of flipping exactly 25 heads. Thus, flipping exactly 25 heads is twice as likely as flipping any number between 0 and 24! Caveat: The upper bound on CDFJ (αn) holds only if α < p. If this is not the case in your problem, then try thinking in complementary terms; that is, look at the number of tails flipped instead of the number of heads. In our example, the probability of flipping 75 or more heads is the same as the probability of flipping 25 or fewer tails. By the above analysis, this is also extremely small. 3.6 Polling Suppose we want to estimate the fraction of the U.S. voting population who would favor Hillary Clinton over Rudy Giuliani in the year 2008 presidential election.2 Let p be this unknown fraction. Let’s suppose we have some random process —say throwing darts at voter registration lists— which will select each voter with equal probability. We can define a Bernoulli variable, K, by the rule that K = 1 if the random voter most prefers Clinton, and K = 0 otherwise. Now to estimate p, we take a large number, n, of random choices of voters3 and count the fraction who favor Clinton. That is, we define variables K1 , K2 , . . . , where Ki is in­ terpreted to be the indicator variable for the event that the ith chosen voter prefers Clin­ ton. Since our choices are made independently, the Ki ’s are independent. So formally, 2 We can only keep our fingers crossed for this race to happen – when they ran against each other for the U.S. Senate in 2000, they generated some of the best entertainment in TV history. 3 We’re choosing a random voter n times with replacement. That is, we don’t remove a chosen voter from the set of voters eligible to be chosen later; so we might choose the same voter more than once in n tries! We would get a slightly better estimate if we required n different people to be chosen, but doing so complicates both the selection process and its analysis with little gain in accuracy. Course Notes, Week 13: Random Variables, Distributions and Expectation 15 we model our estimation process by simply assuming we have mutually independent Bernoulli variables K1 , K2 , . . . , each with the same probability, p, of being equal to 1. Now let Sn be their sum, that is, n � Sn ::= Ki . (2) i=1 So Sn has the binomial distribution with parameter, n, which we can choose, and un­ known parameter, p. The variable Sn /n describes the fraction of voters in our sample who favor Clinton. We would expect that Sn /n should be something like p. We will use the sample value, Sn /n, as our statistical estimate of p. In particular, suppose we want our estimate of p to be within 0.04 of p at least 95% of the time. Namely, we want � �� � � Sn � � � Pr � − p� ≤ 0.04 ≥ 0.95 . n Let � be the margin of error we can tolerate, and let δ be the probability that our result lies outside this margin. We’re interested in having � = 0.04 and δ ≤ 0.05, but the derivation will be clearer if we postpone plugging these values in until the end. We want to determine the number, n, of times we must poll voters so that the value, Sn /n, of our estimate will, with probability at least 1 − δ, be within � of the actual fraction in the nation favoring Clinton. We can define δ, the probability that our poll is off by more than the margin of error �, as follows: � � � � Sn Sn ≤p−� + Pr ≥p+� δ = Pr n n � �� � � �� � too many in sample too many in sample prefer “Giuliani” prefer “Clinton” = Pr {Sn ≤ (p − �)n} + Pr {Sn ≥ (p + �)n} . Now CDFSn ((p − �)n) ::= Pr {Sn ≤ (p − �)n} Also, Pr {Sn ≥ (p + �)n} = Pr {n − Sn ≤ ((1 − p) − �)n} . But Tn ::= n − Sn is simply the number of voters in the sample who prefer Giuliani, which is a sum of Bernoulli random variables with parameter 1 − p, and therefore Pr {Tn ≤ ((1 − p) − �)n} = CDFTn ((1 − p) − �)n. Hence δ = CDFSn ((p − �)n) + CDFTn (((1 − p) − �)n). (3) 16 Course Notes, Week 13: Random Variables, Distributions and Expectation So we have reduced getting a good estimate of the required sample size to finding good bounds on two cumulative binomial distributions with parameters p and 1 − p respec­ tively. Using the bound on the cumulative binomial distribution function allows us to calculate an expression bounding (3) in terms of n, � and p. The problem is that this bound would contain p, the fraction of Americans that prefer Clinton. This is the unknown number we are trying to determine by polling! Fortunately, there is a simple way out of this circularity. Since (3) is symmetric in p, it has an inflection point when p = 1/2, and this inflection point is, in fact, its maximum: Fact. For all �, n, the maximum value of δ in equation (3) occurs when p = 1/2. In other words, the binomial tails fall off most slowly when p = 1/2. Using this fact, and plugging into the equations for CDFSn ((p − �)n) and CDFTn (((1 − p) − �)n), we get the following theorem: Theorem 3.1 (Binomial Sampling). Let K1 , K2 , . . . , be a sequence of mutually independent 0­1­valued random variables with the same expectation, p, and let Sn ::= n � Ki . i=1 Then, for 1/2 > � > 0, � �� � � Sn � 1 + 2� 2−n(1−H((1/2)−�)) ·� Pr �� − p�� ≥ � ≤ . n 2� 2π(1/4 − �2 )n (4) We want � = 0.04, so plugging into (4) gives δ ≤ 13.5 · 2−n(0.00462) √ 1.2492 n (5) where δ is the probability that our estimate is not within � of p. We want to poll enough people so that δ ≤ 0.05. The easiest way to find the necessary sample size n is to plug in values for n to find the smallest one where in the righthand side of (5) is ≤ 0.05: n = people polled 500 600 623 650 664 700 upper bound on probability poll is wrong 9.7% 6.4% 5.9% 5.3% 5.0% ← our poll size 4.3% Course Notes, Week 13: Random Variables, Distributions and Expectation 17 So 95% of the time, polling 6644 people will yield a fraction that is within 0.04 of the actual fraction of voters preferring Clinton. A remarkable point is that the population of the country has no effect on the poll size! Whether there are a thousand people or a billion in the country, polling only a few hun­ dred is sufficient! This method of estimation by sampling a quantity —voting preference in this example— is a technique that can obviously be used to estimate many other unknown quantities. Problem 1. Explaining Sampling to a Jury We just showed that merely sampling 662 voters will yield a fraction that, 95% of the time, is within 0.04 of the of the actual fraction of voters who prefer Clinton. The actual size of the voting population (10’s of millions) was never considered because it did not matter. Suppose you were going to serve as an expert witness in a trial. How would you explain why the number of people necessary to poll does not depend on the population size? 4 Confidence Levels Suppose a pollster uses a sample of 662 random voters to estimate the fraction of voters who prefer Clinton, and the pollster finds that 364 of them prefer Clinton. It’s tempting, but sloppy, to say that this means: False Claim. With probability 0.95, the fraction, p, of voters who prefer Clinton is 364/662±0.04. Since 364/662 − 0.04 > 0.50, there is a 95% chance that more than half the voters prefer Clinton. What’s objectionable about this statement is that it talks about the probability or “chance” that a real world fact is true, namely that the actual fraction, p, of voters favoring Clinton is more than 0.50. But p is what it is, and it simply makes no sense to talk about the probability that it is something else. For example, suppose p is actually 0.49; then it’s nonsense to ask about the probability that it is within 0.04 of 364/662 —it simply isn’t. A more careful summary of what we have accomplished goes this way: We have described a probabilistic procedure for estimating the value of the actual fraction, p. The probability that our estimation procedure will yield a value within 0.04 of p is 0.95. This is a bit of a mouthful, so special phrasing closer to the sloppy language is commonly used. The pollster would describe his conclusion by saying that At the 95% confidence level, the fraction of voters who prefer Clinton is 364/662± 0.04. 4 An exact calculation of the binomial CDF shows that a somewhat smaller poll size of 612 would be sufficient. 18 Course Notes, Week 13: Random Variables, Distributions and Expectation It’s important to remember that confidence levels refer to the results of estimation pro­ cedures for real­world quantities. The real­world quantity being estimated is typically unknown, but fixed; it is not a random variable, so it makes no sense to talk about the probability that it has some property. 5 Expected Value The expectation or expected value of a random variable is a single number that tells you a lot about the behavior of the variable. Roughly, the expectation is the average value, where each value is weighted according to the probability that it comes up. Formally, the expected value of a random variable R defined on a sample space S is: � E [R] = R(w) Pr {w} w∈S To appreciate its signficance, suppose S is the set of students in a class, and we select a student uniformly at random. Let R be the selected student’s exam score. Then E [R] is just the class average— the first thing everyone want to know after getting their test back! In the same way, expectation is usually the first thing one wants to determine about any random variable. Let’s work through an example. Let R be the number that comes up on a fair, six­sided die. Then the expected value of R is: E [R] = 6 � k=1 =1· = k· 1 6 1 1 1 1 1 1 +2· +3· +4· +5· +6· 6 6 6 6 6 6 7 2 This calculation shows that the name “expected value” is a little misleading; the random variable might never actually take on that value. You can’t roll a 3 21 on an ordinary die! 5.1 Equivalent Definitions of Expectation There are some other ways of writing the definition of expectation. Sometimes using one of these other formulations can make computing an expectation a lot easier. One option is to group together all outcomes on which the random variable takes on the same value. Theorem 5.1. E [R] = � x∈range(R) x · Pr {R = x} Course Notes, Week 13: Random Variables, Distributions and Expectation 19 Proof. We’ll transform the left side into the right. Let [R = x] be the event that R = x. � E [R] = R(w) Pr {w} w∈S � = � R(w) Pr {w} x∈range(R) w∈[R=x] � = � x Pr {w} x∈range(R) w∈[R=x] ⎛ � = ⎝x · x∈range(R) � = ⎞ � Pr {w}⎠ w∈[R=x] x · Pr {R = x} x∈range(R) On the second line, we break the single sum into two. The outer sum runs over all possible values x that the random variable takes on, and the inner sum runs over all outcomes taking on that value. Thus, we’re still summing over every outcome in the sample space exactly once. On the last line, we use the definition of the probability of the event [R = x]. Corollary 5.2. If R is a natural­valued random variable, then: E [R] = ∞ � i · Pr {R = i} i=0 When you are considering a random variable that takes on values only in the natural numbers, N ::= {0, 1, 2, . . . }, there is yet another way to write the expected value: Theorem 5.3. If R is a natural­valued random variable, then: E [R] = ∞ � Pr {R > i} i=0 Proof. Consider the sum: Pr {R = 1} + Pr {R = 2} + Pr {R = 3} + · · · + Pr {R = 2} + Pr {R = 3} + · · · + Pr {R = 3} + · · · + ··· The columns sum to 1 · Pr {R = 1}, 2 · Pr {R = 2}, 3 · Pr {R = 3}, etc. Thus, the whole sum is equal to: ∞ � i · Pr {R = i} = E [R] i=0 20 Course Notes, Week 13: Random Variables, Distributions and Expectation Here, we’re using Corollary 5.2. On the other hand, the rows sum to Pr {R > 0}, Pr {R > 1}, Pr {R > 2}, etc. Thus, the whole sum is also equal to: ∞ � Pr {R > i} i=0 These two expressions for the whole sum must be equal, which proves the theorem. 5.2 Expected Value of an Indicator Variable The expected value of an indicator random variable for an event is just the probability of that event. (Remember that a random variable IA is the indicator random variable for event A, if IA = 1 when A occurs and IA = 0 otherwise.) Lemma 5.4. If IA is the indicator random variable for event A, then E [IA ] = Pr {A} . Proof. E [IA ] = 1 · Pr {IA = 1} + 0 · Pr {IA = 0} = Pr {IA = 1} = Pr {A} . (Def. of IA ) For example, if A is the event that a coin with bias p comes up heads, E [IA ] = Pr {IA = 1} = p. 5.3 Mean Time to Failure Let’s look at a problem where one of these alternative definitions of expected value is particularly helpful. A computer program crashes at the end of each hour of use with probability p, if it has not crashed already. What is the expected time until the program crashes? If we let R be the number of hours until the crash, then the answer to our problem is E [R]. This is a natural­valued variable, so we can use the formula: E [R] = ∞ � i=0 Pr {R > i} Course Notes, Week 13: Random Variables, Distributions and Expectation 21 We have R > i only if the system remains stable after i opportunities to crash, which happens with probability (1 − p)i . Plugging this into the formula above gives: E [R] = ∞ � (1 − p)i i=0 1 1 − (1 − p) 1 = p = The closed form on the second line comes from the formula for the sum of an infinite geometric series where the ratio of consecutive terms is 1 − p. So, for example, if there is a 1% chance that the program crashes at the end of each hour, then the expected time until the program crashes is 1/0.01 = 100 hours. The general prin­ ciple here is well­worth remembering: if a system fails at each time step with probability p, then the expected number of steps up to the first failure is 1/p. 5.3.1 Making a Baby Girl A couple really wants to have a baby girl. There is a 50% chance that each child they have is a girl, and the genders of their children are mutually independent. If the couple insists on having children until they get a girl, then how many baby boys should they expect first? This is really a variant of the previous problem. The question, “How many hours until the program crashes?” is mathematically the same as the question, “How many children must the couple have until they get a girl?” In this case, a crash corresponds to having a girl, so we should set p = 1/2. By the preceding analysis, the couple should expect a baby girl after having 1/p = 2 children. Since the last of these will be the girl, they should expect just one boy. Something to think about: If every couple follows the strategy of having children until they get a girl, what will eventually happen to the fraction of girls born in this world?