EECS 70 Discrete Mathematics and Probability TheorySpring 2014 Anant Sahai Note 10Introduction to Basic Discrete ProbabilityIn the last note we considered the probabilistic experiment where we flipped a fair coin 10, 000 times andcounted the number of Hs. We asked "what is the chance that we get between 4900 and 5100 Hs".At a more basic level, we asked “what was the chance that we got a head?”In this note we will begin to formalize these notions for an arbitrary probabilistic experiment. We will startby introducing the space of all possible outcomes of the experiment, called a sample space. Exactly oneof these will be realized. In our current model, each element of the sample space is assigned a probability- which tells us how likely it is to occur when we actually perform the experiment. The mathematicalformalism we introduce might take you some time to get used to. But you should remember that ultimatelyit is just a precise way to say what we mean when we describe a probabilistic experiment like flipping a coinn times.Random ExperimentsThe outcome of the random experiment is called a sample point. The sample space, often denoted by Ω, isthe set of all possible outcomes.An example of such an experiment is tossing a coin 4 times. HT HT is an example of a sample point andthe sample space has 16 elements:How do we determine the chance of each particular outcome, such as HHT T , of our experiment? In orderto do this, we need to define the probability for each sample point, as we will do below.Probability SpacesA probability space is a sample space Ω, together with a probability Pr[ω ] for each sample point ω , suchthatEECS 70, Spring 2014, Note 10 1• 0 ≤ Pr[ω ] ≤ 1 for all ω ∈ Ω.•∑ω ∈ΩPr[ω ] = 1, i.e., the sum of the probabilities of all outcomes is 1.The easiest, and intuitively paradigmatic, case is that of uniform probability.Uniform ProbabilityThe easiest way to assign probabilities to sample points is uniformly: if |Ω| = N, then Pr[x] =1N∀x ∈ Ω.For example, if we toss a fair coin 4 times, each of the 16 sample points (as pictured above) is assignedprobability116. We will see examples of non-uniform probability distributions soon.After performing an experiment, we are often interested in knowing whether an event occurred. For example,the might be interested in the event that there were “exactly 2 H’s in four tosses of the coin". How do weformally define the concept of an event in terms of the sample space Ω? Here is a beautiful answer. We willidentify the event “exactly 2 H’s in four tosses of the coin" with the subset consisting of those outcomes inwhich there are exactly two H’s:{HHT T, HT HT, HT T H, T HHT, T HT H, T T HH} ⊆ Ω. Now we turn this around and say that formally anevent A is just a subset of the sample space, A ⊆ Ω.Another way to think about it is to associate “properties” with experimental outcomes. An event of interest isabout one such property1. The set A is then just the set of those outcomes that have that property. Followingthe same example as above, the property is “having exactly 2 Hs” where the outcomes are strings of length4.How should we define the probability of an event A? Naturally, we should just add up the probabilities of thesample points in A. For uniform probability, this is the same as asking what is the frequency of the relevantproperty among possible outcomes.Formally, for any event A ⊆ Ω, we define the probability of A to bePr[A] =∑ω ∈APr[ω ].Thus the probability of getting exactly two H’s in four coin tosses can be calculated using this definition asfollows. A consists of all sequences that have exactly two H’s, and so |A| = 6. For this example, there are24= 16 possible outcomes for flipping four coins. Thus, each sample point ω ∈ A has probability116; and,as we saw above, there are six sample points in A, giving us Pr[A] = 6 ·116=38.For the special case when the probability is uniform,Pr[A] =|A||Ω|So probability is just a kind of generalized proportion and is exactly proportion in the uniform case.Rolling Dice ExampleThe next random experiment we will discuss consists of rolling two dice. In this experiment, Ω = {(i, j) :1 ≤ i, j ≤ 6}. The probability space is uniform, i.e. all of the sample points have the same probability, which1If you have noticed a connection here between sets and propositions, this is no coincidence.EECS 70, Spring 2014, Note 10 2must be1|Ω|. In this case, |Ω| = 36, so each sample point has probability136. In such circumstances, theprobability of any event A is clearly justPr[A] =# of sample points in A# of sample points in Ω=|A||Ω|.So for uniform spaces, computing probabilities reduces to counting sample points!Now consider two events: the event A that the sum of the dice is at least 10 and the event B that there isat least one 6. By writing out the number of sample points in each event, we can determine the number ofsample points in each event; |A| = 6 and |B| = 11. By the observation above, it follows that Pr[A] =636=16and Pr[B] =1136.Nonuniform ProbabilityThe general formalism above works for any assignment of probability “weights” on outcomes, not justuniform probability.However, for beginners, it is useful to think about nonuniform probability as being a view of a story that isfundamentally uniform underneath. For example, back to the fair coin toss example, the uniform perspectivesays that the experimental outcome is the string of tosses. However, someone could also look at the sameexperiment and instead say that the outcome is the number of heads. In that case, the sample space justhas five possibilities {0, 1, 2, 3, 4} and the probability is not uniform. We have Pr[0] = Pr[4] =116, Pr[1] =Pr[3] =416=14, and as we saw above Pr[2] =616=38. Notice that these numbers sum up to one.When all of the probabilities involved are rational2numbers and the set of outcomes is finite, it is alwayspossible to come up with such a uniform back-story for nonuniform probabilities.The Monty Hall ProblemIn an (in)famous 1970s game show hosted by one Monty Hall, a contestant was shown three doors; behindone of the doors was a prize, and behind the other two were goats. The contestant (who prefers cars togoats) picks a door (but doesn’t open it). Then Hall’s assistant (Carol), opens one of the other two doors,revealing a goat (since Carol knows where the prize is, and there are two goats, she can always do this).
View Full Document
Unlocking...