DOC PREVIEW
CORNELL CS 2800 - CS 2800 Lecture Notes

This preview shows page 1 out of 3 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 3 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 3 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CS 2800: Discrete Math Oct. 17, 2011LectureLecturer: John Hopcroft Scribe: Dan & JuneReview1 Monte Hall ProblemThe Monte Hall Problem is an interesting excercise in conditional probability. In the scenario, you are ona game show competing for a grand prize. The game consists of you choosing among three doors and youare awarded whatever prize hides behind the door you choose. You know that one of the doors is hiding asports car and the other two are hiding goats. Obviously, it is your objective to choose the door hiding thecar. However, you do not know which door is hiding what prize.When the game begins you select a door (let’s say door A), but it is not opened yet. Because there aretwo goats, at least one of the two doors you did not choose must be hiding a goat. So, as an added twist,the host of this show - Monte Hall - will open this door (let’s say door B) and reveal a goat. He then posesthis question: “ Do you wish to change your selection to the other remaining door (door C)? ”What do you do? Many people will first assume that switching doors will neither help or hurt yourchances. Their reasoning is that when you initially choose, each door has a 1/3 chance of hiding a car andMonte revealing one door doesn’t change this uniform probability. This turns out to be false. In reality,you double your chances of winning the car if you choose to switch. For a mathematical explanation, you’llneed to turn to conditional probability and Bayes Theorem (covered in the next lecture). However, we candevelop some intuition to convince you of this startling effect.Let’s consider the only two cases. Case 1 is when you initially choose a door with a goat behind it. Then,Monte will reveal the only remaining goat and, clearly, you should switch to the final door (which must behiding the car). In Case 2, you initially choose the door with the car behind it. Then, Monte will revealeither of two remaining goats and ask you if you wish to switch. Obviously, you will lose the car if you switchand it is better to keep your first choice.Hopefully you now see why switching is twice likely to get you the car: it is the better choice in Case 1and Case 1 is twice as likely to occur! If you repeated the game many times, switching your choice will giveyou a car twice as often as it will give you a goat. So, if anyone ever presents you with an option like this,you should always switch!2 Probability IntroProbablility is formally covered in the next lecture. This quick introduction will serve to first build intuitionon the subject.A common way to define probability is with counting. For example, we can continuously flip a fair coinand count how many times heads comes up. Over time, we’ll surely notice that about half of the outcomesare heads. So, we call the probablility of a single flip bing heads 1/2. A direct result of this definition isthat probabilities must always be between 0 and 1 inclusive. Yes, somethings can have probability 0: theprobability that weather in Ithaca will be exactly 120 degrees tomorrow is virtually 0.Another product of this definition is that the sum the probabilities of all possible events must be 1. In theexample above, this is simply 1/2 for heads + 1/2 for tails = 1. Again, a formal treatment of this property iscovered in the next lecture. A good way of remembering this fact is by understanding that something musthappen. When you toss a perfect fair coin, either it lands on heads or tails. There are no other options. Since1a probability of 1 leaves no room for other events to occur, it makes sense that the sum of the probabilitiesof the two outcomes equals 1.Let’s say somebody now told you that they had devised a system of choosing an integer greater than 1such that the probability of a number being picked is equal to its reciprocal. For example, the probabilitythat you choose 5 = 1/5 and 100 has a 1/100 chance of being picked. Is this possible? The answer is no.To check schemes like these, the only thing you have to ensure is that the sum of all probabilities equals 1.If you sum the infinite series 1/2 + 1/3 + 1/4 ... (a.k.a the harmonic series) you will notice that it diverges,Pi>11i= ∞. Notice, if we changed the scheme so that the probability is proportional to the square ofthe reciprocal, then something different occurs. The infinite sum 1/4 + 1/9 + 1/16 ... actually converges toπ2/6. While this also doesn’t sum to 1, it is a more manageable situation. We can now simply normalizethe probability of each event so that the sum does equal one, but their relative probabilities do not change.For the reciprocal squared example, we would multiply each probability by 6/π2.3 PokerPoker involves being dealt a 5 card hand from a 52 card deck. The 52 cards are organized by suit andrank. There are 4 suits, and 13 ranks. The suits are spade, diamond, heart, and club. The ranks are2, 3, . . . , 10, J, Q, K, A. Certain combinations of the 5 cards are called, flushes, royal flushes, full house, etc.The rarer the named combination your hand is the more likely you are to win. In Poker the order of yourcards does not matter. (If you are unfamiliar with the game, check it out on wikipedia - gambling withmoney is unadvised.) The number of possible 5 card hands is525Example A flush is a 5 card hand, where all the cards are of the same suit, eg all cards are diamonds, orall cards are clubs, etc. Here we calculate the probability of being dealt a flush.First we find the number of hands that are a flush. There are 4 possible suits, spades, diamonds, hearts,and clubs. For each suit there are 13 cards of that suit. Now, there are135ways to get a flush in a givensuit. So, there are 4135hands that are flushes. The probability of getting a flush is then4135525≈ 0.00198Example A hand with a pair is a 5 card hand where exactly two cards have the same rank. Here wecalculate the probability of being dealt a pair.First, for a given rank there are 4 cards so there are42ways to select a pair. There are 13 ranks, so thereare 13 ∗42ways to just select a pair. Now we have to combine this with the number of ways the remaining3 cards can be picked. Well, for the hand to be a pair, none of the remaining three can be of the same rankas the pair (otherwise we’ll have three-of-a-kind or four-of-a-kind). So, there are 12 remaining ranks and 3cards to choose. We can’t forget, though, that each of the 12 remaining ranks has 4 cards per suit. Thus,the


View Full Document

CORNELL CS 2800 - CS 2800 Lecture Notes

Download CS 2800 Lecture Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view CS 2800 Lecture Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view CS 2800 Lecture Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?