Create Presentation
Download Presentation

Download Presentation
## CS 173: Discrete Mathematical Structures

- - - - - - - - - - - - - - - - - - - - - - - - - - - E N D - - - - - - - - - - - - - - - - - - - - - - - - - - -

**CS 173:Discrete Mathematical Structures**Cinda Heeren heeren@cs.uiuc.edu Siebel Center, rm 2213 Office Hours: M 11a-12p**CS 173 Announcements**• Homework 9 available. Due 11/7, 8a. • Exam 2, Nov 9, 7-9p. Email Cinda with conflicts. • Today’s lecture covers material from Rosen, sections 5.1-5.3. Cs173 - Spring 2004**CS 173 Probability**We roll a single die, what are the possible outcomes? {1,2,3,4,5,6} The set of possible outcomes is called the sample space. We roll a pair of dice, what is the sample space? Depends on what we’re going to ask. Often convenient to choose a sample space of equally likely events. {(1,1),(1,2),(1,3),…,(6,6)} Cs173 - Spring 2004**CS 173 Probability**Define a probability measure on a set S to be a real-valued function, Pr, with domain 2S so that: • For any subset A in 2S, 0 Pr(A) 1. • Pr() = 0, Pr(S) = 1. • If subsets A and B are disjoint, then Pr(A U B) = Pr(A) + Pr(B). Pr(A) is “the probability of event A.” A sample space, together with a probability measure, is called a probability space. S = {1,2,3,4,5,6} For A S, Pr(A) = |A|/|S| Ex. “Prob of an odd #” A = {1,3,5}, Pr(A) = 3/6 Cs173 - Spring 2004**Inclusion-Exclusion**CS 173 Probability Some things you already know: If A is a subset of S, let ~A be the complement of A wrt S. Then Pr(~A) = 1 - Pr(A) If A and B are subsets of S, then Pr(A U B) = Pr(A) + Pr(B) - Pr(A B) A thought to ponder… What if I asked you to pick a uniformly random positive integer? Cs173 - Spring 2004**Experiment**CS 173 Probability Choose a door to win a prize! Monty Hall puzzle. http://www.letsmakeadeal.com/ Cs173 - Spring 2004**CS 173 Probability**Rules of the game: • Pair up and choose one person to be Monty, the other to be a contestant. • Repeat 5 times, recording 1 point for every win: • Monty: secretly choose one door to be the car (the other two are goats). • Contestant: tell Monty which door you choose. • Monty: reveal a goat, and offer to let contestant switch doors. • Contestant: decline the offer. • Monty: reveal the prize! Cs173 - Spring 2004**CS 173 Probability**Rules of the game: • Pair up and choose one person to be Monty, the other to be a contestant. • Repeat 5 times, recording 1 point for every win: • Monty: secretly choose one door to be the car (the other two are goats). • Contestant: tell Monty which door you choose. • Monty: reveal a goat, and offer to let contestant switch doors. • Contestant: accept the offer and switch doors. • Monty: reveal the prize! Cs173 - Spring 2004**Questions?**CS 173 Probability What is the probability that a 5 card poker hand contains a royal flush? S = all 5 card poker hands. A = all royal flushes Pr(A) = |A|/|S| Pr(A) = 4/C(52,5) Cs173 - Spring 2004**CS 173 Probability**Which is more likely: • Rolling an 8 when 2 dice are rolled? • Rolling an 8 when 3 dice are rolled? • No clue. Cs173 - Spring 2004**36**5 CS 173 Probability What is the probability of a total of 8 when 2 dice are rolled? What is the size of the sample space? How many rolls satisfy our condition of interest? So the probability is 5/36. Cs173 - Spring 2004**216**C(7,2) CS 173 Probability What is the probability of a total of 8 when 3 dice are rolled? What is the size of the sample space? How many rolls satisfy our condition of interest? So the probability is 21/216. Cs173 - Spring 2004**CS 173 Conditional Probability**Let E and F be events with Pr(F) > 0. The conditional probability of E given F, denoted by Pr(E|F) is defined to be: Pr(E|F) = Pr(EF)/Pr(F). F E Cs173 - Spring 2004**CS 173 Conditional Probability**Pr(E|F) = Pr(EF)/Pr(F). A bit string of length 4 is generated at random so that each of the 16 bit strings is equally likely. What is the probability that it contains at least two consecutive 0s, given that its first bit is a 0? Pr(F) = 1/2 Pr(EF)? 0000 0001 0010 0011 0100 Pr(EF) = 5/16 Pr(E|F) = 5/8 Cs173 - Spring 2004**No**CS 173 Independence The events E and F are independent if and only if Pr(EF) = Pr(E) x Pr(F). Let E be the event that a family of n children has children of both sexes. Lef F be the event that a family of n children has at most one boy. Are E and F independent if n = 2? Cs173 - Spring 2004**Yes**CS 173 Independence The events E and F are independent if and only if Pr(EF) = Pr(E) x Pr(F). Let E be the event that a family of n children has children of both sexes. Lef F be the event that a family of n children has at most one boy. Are E and F independent if n = 3? Cs173 - Spring 2004**No**CS 173 Independence The events E and F are independent if and only if Pr(EF) = Pr(E) x Pr(F). Let E be the event that a family of n children has children of both sexes. Lef F be the event that a family of n children has at most one boy. Are E and F independent if n = 4? Cs173 - Spring 2004**No**CS 173 Independence The events E and F are independent if and only if Pr(EF) = Pr(E) x Pr(F). Let E be the event that a family of n children has children of both sexes. Lef F be the event that a family of n children has at most one boy. Are E and F independent if n = 5? Cs173 - Spring 2004**No**Yes No No CS 173 Independence The events E and F are independent if and only if Pr(EF) = Pr(E) x Pr(F). Let E be the event that a family of n children has children of both sexes. Lef F be the event that a family of n children has at most one boy. Are E and F independent if n = 4? n = 2? n = 3? n = 5? Cs173 - Spring 2004**23**183 365 730 CS 173 Birthdays How many people have to be in a room to assure that the probability that at least two of them have the same birthday is greater than 1/2? Let pn be the probability that no people share a birthday among n people in a room. Then 1 - pn is the probability that 2 or more share a birthday. We want the smallest n so that 1 - pn > 1/2. Cs173 - Spring 2004**.58**C(n,k)pk(1-p)n-k C(8,3) CS 173 Bernoulli Trials A coin is tossed 8 times. What is the probability of exactly 3 heads in the 8 tosses? THHTTHTT is a tossing sequence… How many ways of choosing 3 positions for the heads? What is the probability of a particular sequence? In general: The probability of exactly k successes in n independent Bernoulli trials with probability of success p, is Cs173 - Spring 2004**C(n,k)pk(1-p)n-k**.73.32 Assumes independent trials C(5,3)0.730.32 + C(5,4)0.740.31 + C(5,5)0.750.30 CS 173 Bernoulli Trials A game of Jewel Quest is played 5 times. You clear the board 70% of the time. What is the probability that you win a majority of the 5 games? Sanity check: What is the probability the the result is WWLLW? In general: The probability of exactly k successes in n independent Bernoulli trials with probability of success p, is Cs173 - Spring 2004**-2**0 2 S CS 173 Random Variables For a given sample space S, a random variable is any real valued function on S. Suppose our experiment is a roll of 2 dice. S is set of pairs. • X = sum of two dice. X((2,3)) = 5 • Y = difference between two dice. Y((2,3)) = 1 • Z = max of two dice. Z((2,3)) = 3 Cs173 - Spring 2004**0**1 2 3 4 CS 173 Random Variables A probability distribution on a r.v. X is just an allocation of the total probability, 1, over the possible values of X. How many movies have you watched in the last week? Picture gives a probability distribution! The chart gives likelihood that a randomly selected student watched each of the particular numbers of movies. Cs173 - Spring 2004**CS 173 Random Variables**Example: Do you ever play the game Racko? Suppose we are playing a game with cards labeled 1 to 20, and we draw 3 cards. We bet that the maximum card has value 17 or greater. What’s the probability we win the bet? Let r.v. X denote the maximum card value. The possible values for X are 3, 4, 5, …, 20. Filling in this box would be a pain. We look for a general formula. Cs173 - Spring 2004**20**6840 60 1140 I’m not telling. C(20,3) C(i-1,2) Pr(X = 17) + Pr(X = 18) + Pr(X = 19) + Pr(X = 20) 0.51 These are the table values. CS 173 Random Variables X is value of the highest card among the 3 selected. 20 cards are labeled 1 through 20. We want Pr(X = i), i = 3,…20. Denominator first: How many ways are there to select the 3 cards? How many choices are there that result in a max card whose value is i? Pr(X = i) = C(i-1, 2) / C(20,3) We win the bet if the max card, X is 17 or greater. What’s the probability we win? Cs173 - Spring 2004