> " ! Help / FAQ # Alicia Clark $ > 12.1 Probability of an event One of the primary applications of counting is to calculate probabilities of random events. Probabili theory plays an important role in almost every area of science, economics, and business. In compu science, randomization and probability are ubiquitous. Here are a few examples: Algorithms can be designed to make random choices in order to avoid actions that correlate with input data. Probability theory is used to analyze the behavior and running time of random algorithms. Computer systems are often simulated and tested using randomized models for user behavio example, a network designer would use probability theory to design a network that avoids congestion under assumptions about the distribution of messages that need to be sent acros network. A computer chip manufacturer needs to predict the likelihood that a chip contains a defect depending on different features of the fabrication environment in which it is made. Probability would be used to analyze different environments and predict the likelihood that a chip has a d Probability is one of the primary tools in machine learning in which computers are used to dis patterns and rules in large sets of data. Bayes' Theorem about conditional probabilities provid way to reason formally about the likelihood of different causes given a set of observed data. A comprehensive introduction to probability theory and its role in computer science is beyond the s this material. Instead, the focus here is on how counting is used in probability. Consider a simple example in which a red and a blue die are thrown. A player in a game of dice may interested in different types of events that can occur as a result of the throw. For example, she may interested in the likelihood that both dice come up with an even number or that the sum of the num the dice is at least eight. The simple example of throwing a pair of dice contains many of the basic ingredients studied in probability. DeInition 12.1.1: Experiments and outcomes. An experiment is a procedure that results in one out of a number of possible outcomes. The set o all possible outcomes is called the sample space of the experiment. A subset of the sample spac is called an event. In the case of the red and blue die, the experiment is the process of throwing the dice. An outcome of the two dice is the number that shows up on the blue die and the number that shows up on the r The picture below shows two different outcomes of a roll of the dice: Figure 12.1.1: Two possible outcomes of a red and blue die. For simplicity, we describe an outcome by an ordered pair where the Irst number denotes the outc the blue die and the second number denotes the outcome of the red die. The outcome on the left is denoted (5, 3) and the outcome on the right is denoted (3, 5). The set of outcomes for each die is {1 4, 5, 6}, and the sample space for the two dice is S = {1, 2, 3, 4, 5, 6} {1, 2, 3, 4, 5, 6} An event is a subset of S. For example, the event E that the sum of the dice is exactly 8 is the follow E = {(2, 6), (3, 5)(4, 4), (5, 3), (6, 2)} Standard playing cards Another common example of an experiment is a card dealer who deals a hand with Ive cards to a p from a perfectly shuZed deck. A standard deck of playing cards consists of 52 cards. Each card ha rank and a suit. There are 13 possible ranks and 4 possible suits. Any rank-suit combination is poss resulting in 134 = 52 different cards. The different ranks and suits are listed below: Ranks: 2, 3, 4, 5, 6, 7, 8, 9, 10, J (for jack), Q (for queen), K (for king), A (for ace). Suits: (spades), (clubs), (hearts), (diamonds). The "8 of hearts", for example, is denoted 8. The sample space of 5-card hands consists of the s 5-subsets of the 52 cards. The order in which the cards are dealt is not important, just the set of ca the hand after the cards have been dealt. For example, one possible outcome of the experiment of a 5-card hand would be: Figure 12.1.2: A 5-card hand from a standard card deck. The number of different outcomes from dealing a 5-card hand is the number of 5-subsets of the 52 52 ( 5 ) . The event Ejack that the hand has four jacks would be the set of all hands of the form {J, J, J, J, *}, where the "*" could be any of the other 48 cards that are not jacks. The num outcomes in Ejack is 48. Discrete vs. continuous probability Discrete probability is concerned with experiments in which the sample space is a Inite or countab inInite set. Almost all of the experiments analyzed in this material have Inite sample spaces. A set countably in4nite if there is a one-to-one correspondence between the elements of the set and the integers. A set that is not countably inInite is said to be uncountably in4nite. A formal discussion o different kinds of inInity is beyond the scope of this material, but here are a couple of examples to intuitive feel for the difference between countably inInite and uncountably inInite sets. Examples of countably inInite sets include the set of all binary strings (of any length), the set of ord pairs of integers (Z Z), the set of all rational numbers. The set of real numbers is an example of an uncountably inInite set. In fact the set of real numbers Inite interval (for example the set of real numbers from 0 to 1) is also uncountably inInite. Here is a example of an experiment whose outcome is not countably inInite: a dart is thrown at a one meter target. The point at which the dart lands on the target is the outcome of the experiment. The samp space of all possible outcomes is best modeled by pairs (x, y), where x and y are real numbers in th from 0 to 1. PARTICIPATION ACTIVITY 12.1.1: Experiments, outcomes and events. 1) In the experiment of a 5-card hand, is the following an outcome or an event? {4, 6, 7, Q, K} outcome event 2) In the experiment of a 5-card hand, is the following an outcome or an event? {{4, 6, 7, Q, K}, {4, 9, 9, 9, K}} outcome event 3) In the example of a red and blue die that are thrown, deIne the event E to be that the number on both dice are multiples of 3. Which set corresponds to E? (3, 6) {(3, 3), (6, 6)} {(3, 3), (3, 6),(6, 3), (6, 6)} 4) Suppose a coin is iipped three times. The outcome of the experiment is the sequence of outcomes from each iip. For example, HHH denotes the outcome in which the coin comes up heads in each iip. How many distinct outcomes are there? 8 2 4 5) In the experiment where the coin is iipped three times, which set corresponds to the event that at least two of the three iips come up heads? {HHH, HHT} {HHH, HHT, HTH, THH} {HHH, TTH, THT, HTT} A natural question to ask about an experiment is: what is the likelihood (or probability) that a partic outcome occurs? DeInition 12.1.2: Probability distributions. A probability distribution over the outcomes of an experiment with a countable sample space S i function p from S to the set of real numbers in the interval from 0 to 1 with the property that p(s) = 1. sS If E S is an event, then the probability of event E is p(E) = p(s). sE Consider a dishonest dice player who shows up to a game with a loaded die. The player's die is bias that an outcome of 6 is twice as likely to occur as the other numbers. DeIne an experiment which i of the single die. The sample space is {1, 2, 3, 4, 5, 6}, and the probability distribution over the outco deIned by: p(1) = p(2) = p(3) = p(4) = p(5) = p(6) = 2 7 1 7 The event that the die comes up an even number is {2, 4, 6}. The probability of the event that the die comes up even is: p(2) + p(4) + p(6) = 1/7 + 1/7 + 2/7 = 4/7. PARTICIPATION ACTIVITY 12.1.2: Probability distributions - a loaded die. 1) In the loaded die example above, what is the probability of the event that the number on the die is 5 or 6? Check Show answer The uniform distribution In many scenarios, the probability of every outcome in the sample space is the same. The probabili distribution in which every outcome has the same probability is called the uniform distribution. Sin are |S| outcomes in sample space S and their probabilities sum to 1, under the uniform distribution each s S, p(s) = 1/|S|. The uniform distribution reduces questions about probabilities to questions counting because for every event E, p(E) = |E| |S| Returning to the experiment with the red and blue die, if the dice are fair, then each of the 36 outcom equally likely. The event that the sum of the two numbers is 8 is the set E = {(2, 6), (3, 5), (4, 4), (5, 3), (6, 2)}. The probability of the event E is |E|/|S| = 5/36. Example 12.1.1: Three iips of a fair coin. An experiment consists of three consecutive iips of a coin. The outcome is the sequence of outcomes of the three iips. There are eight possible outcomes in the sample space which are lis below. "H" stands for heads and "T" stands for tails: If the coin is a fair coin, then all eight outcomes are equally likely. The event that all three iips com out the same is E = {HHH, TTT}. The probability that all three iips come out the same is: p(E) = PARTICIPATION ACTIVITY |E| 2 1 = = |S| 8 4 12.1.3: Probability of events under a uniform distribution. Give your answer as an integer or a fraction, simpliIed to its lowest terms, (e.g., 3/4 instead of 9/12). 1) In an experiment consisting of three iips of a fair coin, what is the probability that the Irst two iips are both heads? Check Show answer 2) In an experiment consisting of three iips of a fair coin, what is the probability that the Irst two iips are the same? Check Show answer 3) In an experiment consisting of a roll of a In an experiment consisting of a roll of a red and blue die, what is the probability that the red die is one more than the blue die? Check Show answer Example 12.1.2: Redundant data storage. Consider a situation in which Iles are stored on a distributed network. Multiple copies of each Ile are stored around the network so that if one or more computers crash, the data is more likely to b available from at least one source. Suppose that three copies of a Ile are stored at different locations in a network of 30 computers and that at a particular moment, Ive random computers fail. Each subset of Ive computers are equally likely to be the Ive that have failed. What is the probability that there are no copies left of the Ile? The experiment is that a set of Ive computers in the network fail. An outcome of the experiment particular set of Ive failing computers. Thus, the number of distinct outcomes is ( 5 ) . We assum the uniform distribution in which each of the possible 5-sets of computers is equally likely to fail. The Ile is stored at three particular computers in the network, and the event in question is that th set of Ive failed computers includes all three of the computers storing the Ile. How many outcom are in the event? For every outcome in the event, the set of Ive failures includes the three that sto the Ile and the remaining two failures are selected from the 27 computers that do not store the I 30 Thus, the number of outcomes in the event is ( 2 ) . The probability that there are no remaining computers storing the Ile after a random set of Ive computers fail is: 27 |E| ( ) = 302 .002463 |S| ( 5) 27 The next example explores a situation in which messages are routed in a grid network. Every vertex graph is a computer that routes messages through the network. To better understand tramc and congestion, we consider only the tramc generated by messages going from point A to point B. One to calculate congestion would be to put more powerful routers at network vertices that must handl tramc. Thus, we would like to determine the probability that a randomly chosen path from A to B go through the vertex marked X. We consider only the paths that go directly from A to B by a series of transitions upwards and to the right. The path never moves downward or to the left. The diagram b shows one such path. Figure 12.1.3: Paths in a grid network. A direct path from A to B crosses eleven edges, seven of them are moves to the right and four of th moves upwards. The experiment is the process of selecting a direct path from A to B uniformly at r so that all such paths are equally likely. The number of direct paths from A to B is ( 7 ) . The outcom 11 the experiment is the path selected, so the size of the sample space is ( 7 ) . The animation below illustrates how to determine the number of outcomes in the event E that the chosen path passes th vertex X. 11 PARTICIPATION ACTIVITY 12.1.4: Calculating congestion in a grid network. Start X B E: path goes through X. ( |E| = # of paths from A to X |S| = () View animation caption(s) # of paths from X to B 6 edges: 2 up 4 right 5 edges: 2 up 3 right () () 6 4 A 11 7 )( p(E) = 5 3 ( )( ) () 6 4 5 3 11 7 = probability a random path goes through X = 5 7 ) Example 12.1.3: An example from a 5-card hand. A dealer deals a 5-card hand. If the deck is perfectly shuZed, then each 5-card hand is equally like and the distribution over the sample space of 5-card hands is uniform. What is the probability tha the hand has two pairs? The deInition of having two pairs is that there are two pairs of cards, eac pair has the same rank. The pairs have different rank from each other and the Ifth card (that is no part of a pair), has different rank from the pairs. The diagram below shows some examples that a and are not hands with two pairs: DeIne P to be the set of 5-card hands that have two pairs. The probability of event P is: p(P) = |P| ( 5) 52 The animation below shows how to determine |P|. PARTICIPATION ACTIVITY 12.1.5: Number of 5-card hands with two pairs. Start Number of 5 card hands with 2 pairs. 6 6 J J 13 2 4 2 4 44 2 2 { 1, 2, 3, 4, 5, 6, 7, 8, 9, J, Q, K, A }. { }. ( ) ( )( ) Select the ranks for the two pairs Select the suits for one pair Select the suits for the other pair Select the last card ( ))(( )()( ) () p(2-pair hand) = 13 2 4 2 52 5 4 44 2 .04754 View animation caption(s) PARTICIPATION ACTIVITY 12.1.6: Using counting to determine the probability of events. 1) In the grid graph shown below, what's the probability that a random direct path from A to B goes through the vertex in the upper left corner? 11 (7) 11 1 (4) 7 1 (7) 11 2) If a red and a blue die are thrown, then what is the probability that the numbers on the two dice are the same? 5 36 1 2 1 6 3) What is the probability that a random 5card hand has all four aces? 48 (5) 52 4 48 52 (5) 1 48 (5) Additional exercises EXERCISE 12.1.1: Coin iips and events. A coin is iipped four times. For each of the events described below, express the event as a set in roster notation. Each outcome is written as a string of length 4 from {H, T}, such as HHTH. Assum the coin is a fair coin, give the probability of each event. (a) The Irst and last iips come up heads. (b) There are at least two consecutive iips that come up heads. (c) The Irst iip comes up tails and there are at least two consecutive iips that come up heads. EXERCISE 12.1.2: The probability of an event under the uniform distribution - random permutations. A class with n kids lines up for recess. The order in which the kids line up is random with each ordering being equally likely. There are two kids in the class named Celia and Felicity. Give an expression for each of the probabilities below as a function of n. Simplify your Inal expression as much as possible so that your answer does not include any expressions of the form (b). a (a) What is the probability that Celia is Irst in line? (b) What is the probability that Celia is Irst in line and Felicity is last in line? (c) What is the probability that Celia and Felicity are next to each other in the line? EXERCISE 12.1.3: The probability of an event under the uniform distribution - selecting a pair of matching socks. There are 2n socks in a drawer, n white and n black. Two socks are selected at random from the drawer. Every way of selecting the two socks is equally likely. Source: ADUni, modiIed by Sandy Irani. (a) How many ways are there to select the two socks? (b) How many ways of selecting the socks result in two socks of the same color being chosen? (c) What is the probability that a randomly chosen pair of socks are the same color? Simplify yo Inal expression as much as possible so that it does not include any expressions of the form EXERCISE 12.1.4: The probability of an event under the uniform distribution - picking teams. 10 kids are randomly grouped into an A team with Ive kids and a B team with Ive kids. Each grou is equally likely. (a) What is the size of the sample space? (b) There are two kids in the group, Alex and his best friend Jose. What is the probability that Ale and Jose end up on the same team? (c) If the group consists of Ive girls and Ive boys, what is the probability that all the girls end up the same team? EXERCISE 12.1.5: The probability of an event under the uniform distribution - 5-card hands. A 5-card hand is dealt from a perfectly shuZed deck of playing cards. What is the probability of e of the following events? (a) What is the probability that the hand is a full house? A full house has three cards of the same rank and another pair of the same rank. For example, {4, 4, 4, J, J} is a full house What is the probability that the hand is a three of a kind? A three of a kind has 3 cards of the same rank. The other two cards do not have the same rank as each other and do not have th (b) same rank as the three with the same rank. For example, {4, 4, 4, J, 8} is a three kind. (c) What is the probability that all 5 cards have the same suit? What is the probability that the hand is a two of a kind? A two of a kind has two cards of the same rank (called the pair). Among the remaining three cards, not in the pair, no two have th (d) same rank and none of them have the same rank as the pair. For example, {4, 4, J, K, 8} is a two of a kind