DARTMOUTH COSC 030 - 08prob (4 pages)

Previewing page 1 of 4 page document View the full content.
View Full Document

08prob



Previewing page 1 of actual document.

View the full content.
View Full Document
View Full Document

08prob

52 views


Pages:
4
School:
Dartmouth College
Course:
Cosc 030 - Discrete Math Computer Sci
Discrete Math Computer Sci Documents
Unformatted text preview:

Experiments With Random Outcomes Examples Toss a fair coin which side does it land on CS 30 Discrete Mathematics Outcomes HEADS TAILS Roll a fair die what number shows on top Outcomes 1 2 3 4 5 6 ShufOle a deck of cards pick top which card Amit Chakrabarti Probability Probability Spaces Sample space set of outcomes of an experiment Any nonempty set can be a sample space Ours in this course will usually be Oinite sets Sometimes we ll use N or N 0 or Z as a sample space Probability function on such a sample space S is a function Pr S R such that nonnegativity x S Pr x 0 normalization x S Pr x 1 Probability space a pair S Pr Outcomes 2 2 7 Q A Toss a biased coin heads 3 as likely as tails Outcomes HEADS TAILS but something s different Sort n numbers using QuickSort how fast does it run Train a deep belief network on images of puppies Some Simple Probability Spaces Some uniform probability spaces Toss a fair coin which side does it land on Take S H T Pr H 1 2 Pr T 1 2 Roll a fair die what number shows on top Take S 1 2 3 4 5 6 Pr 1 Pr 2 Pr 6 1 6 ShufOle a deck of cards pick top which card Take S 2 2 7 Q A Pr x 1 52 for each x S A nonuniform probability space Toss a biased coin heads 3 as likely as tails Take S H T Pr H 3 4 Pr T 1 4 Modeling it Right How is the Pr function determined It s a modeling choice Roll two fair dice number thrown sum of values Possible outcomes S 2 3 4 12 is Pr uniform Correct question Should we de ine Pr to be uniform over S If we did then Pr 7 1 11 Let s try it out Uh oh looks like Pr 7 1 6 how to justify Model it right an outcome is a pair die1 die2 So S1 1 1 1 2 1 3 6 6 If dice are fair it makes sense to let Pr be uniform over S1 Sum 7 when outcome is one of 1 6 2 5 3 4 4 3 5 1 6 1 Pr Sum 7 1 36 1 36 1 36 1 36 1 36 1 36 1 6 Uniform Probability Space Suppose S Pr is a uniform probability space For all x S Pr x 1 S For all E S Pr E x E Pr x E S Easy calculations Roll two fair dice Pr throwing a 7 Take S 1 1 1 2 1 3 6 6 uniform probabilities Event of interest E7 1 6 2 5 3 4 4 3 5 2 6 1 Pr E7 E7 S 6 36 1 6 Once you re a consummate expert Pr throwing a 7 6 favorable outcomes 36 total outcomes 1 6 Events Have probability space S Pr De inition An event is a set E S De inition The probability of E is Pr E x E Pr x Earlier deOinition guarantees 0 Pr E 1 why Roll two fair dice what is Pr throwing a 7 Take S1 1 1 1 2 1 3 6 6 i j Pr i j 1 36 Event of interest E7 1 6 2 5 3 4 4 3 5 2 6 1 Pr E7 Pr 1 6 Pr 2 5 Pr 6 1 1 36 6 1 6 For all S have events impossibility and S certainty Pr 0 Pr S 1 Being Systematic Four step method 1 Find the sample space 2 DeOine events of interest 3 Determine outcome probabilities 4 Compute event probabilities Described beautifully in LLM 17 1 17 4 you must read it Derangement Problem in Four Steps Randomly match n names to n faces What s the probability of getting zero matches correct Sn f f is an injection n n En d x1 xn Sn d xi xj for all i j Dn f Sn f is a derangement f Sn f x x for all x n 3 Determine outcome probabilities Uniform probabilities interpretation of words randomly match 4 Compute event probabilities 0 t n 1 Find the sample space 2 DeOine events of interest 2 DeOine events of interest Probability that everyone in this class has a unique birthday Assume d days year n students Sn d x1 xn 1 xi d for each i 1 Find the sample space Pr Dn Dn Sn Birthday Problem n 1 t n t 0 t n 1 t t Birthday Paradox Pr n people scattered over d days have distinct birthdays Answer Pr En d d d 1 d 2 d n 1 dn e n n 1 2d Note if n 2d then Pr En d e 1 1 e 0 3679 Using n 40 d 365 Pr En d e 2 137 0 118 Pr some two of you have same birthday 1 0 118 0 882 88 2 3 Determine outcome probabilities Uniform probabilities a simplifying assumption 4 Compute event probabilities Pr En d En d Sn d d d 1 d 2 d n 1 dn 1 0 d 1 1 d 1 2 d 1 n 1 d e 0 d e 1 d e 2 d e n 1 d e 0 1 2 n 1 d e n n 1 2d Combining Events and Probabilities Events A B S for some sample space S Event A B corresponds to A or B Event A B corresponds to A and B Event corresponds to not A Consequence of deOinitions Gen lized sum rule Pr A B Pr A Pr B Pr A B Analogous to generalized sum principle of counting Disjoint sum rule A B Pr A B Pr A Pr B When A B say A and B are disjoint they can t both occur Don t call such events independent Super important Complement rule Pr 1 Pr A Concepts Sample space probability function Uniform probabilities Events Theorems Sum rules complement rule Pr derangement 1 e in the limit Birthday paradox Pr e n n 1 2d Study Bee Review crucial Four step method All examples in LLM Chapter 17


View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view 08prob 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 08prob 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?