DARTMOUTH COSC 030 - 08prob (4 pages)

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