15 251 Great Theoretical Ideas in Computer Science Finite Probability Distribution A finite probability distribution D is a finite sample space S of elements or samples where each sample x in S has a non negative real weight or probability p x The weights must satisfy p x 1 x S weight or probability of x D x p x 0 1 0 17 0 1 0 13 0 11 0 2 0 0 13 0 1 0 06 Sample space Events Any set E S is called an event PrD E p x x E 0 17 0 0 13 0 1 PrD E 0 4 S Conditional Probability The probability of event A given event B is written Pr A B and is defined to be Pr A B Pr B S B A proportion of A B to B Conditional Probability The probability of event A given event B is written Pr A B and is defined to be Pr A B Pr B A and B are independent events if Pr A B Pr A Pr A B Pr A Pr B Pr B A Pr B 15 251 Classics Lecture 11 October 2 2007 Today we will learn about a formidable tool in probability that will allow us to solve problems that seem really really messy If I randomly put 100 letters into 100 addressed envelopes on average how many letters will end up in their correct envelopes Hmm k k Pr k letters end up in correct envelopes k k aargh On average in class of size m how many pairs of people will have the same birthday k k Pr exactly k collisions k k aargh The new tool is called Linearity of Expectation Random Variable To use this new tool we will also need to understand the concepts of Random Variable and Expectations Today s lecture not too much material but need to understand it well Random Variable Let S be sample space in a probability distribution A Random Variable is a real valued function on S S Sample space Random Variable Let S be sample space in a probability distribution A Random Variable is a real valued function on S Examples X value of white die in a two dice roll X 3 4 3 X 1 6 1 Y sum of values of the two dice Y 3 4 7 Y 1 6 7 W value of white die value of black die W 3 4 34 Y 1 6 16 Tossing a Fair Coin n Times S all sequences of H T n D uniform distribution on S D x n for all x 2 S Random Variables say n 10 X of heads X HHHTTHTHTT 5 Y 1 if heads tails 0 otherwise Y HHHTTHTHTT 1 Y THHHHTTTTT 0 Notational Conventions Use letters like A B E for events Use letters like X Y f g for R V s R V random variable Two Views of Random Variables Think of a R V as Input to the function is random A function from S to the reals Or think of the induced distribution on Randomness is pushed to the values of the function Two Coins Tossed X TT TH HT HH 0 1 2 counts the number of heads S Distribution on the 2 reals HH TT TH HT 0 1 It s a Floor Wax And a Dessert Topping It s a function on the sample space S It s a variable with a probability distribution on its values You should be comfortable with both views From Random Variables to Events For any random variable X and value a we can define the event A that X a Pr A Pr X a Pr x S X x a Two Coins Tossed X TT TH HT HH 0 1 2 counts of heads S HH TT TH X 2 0 1 HT Pr X a Pr x S X x a Distribution on X Pr X 1 Pr x S X x 1 Pr TH HT From Events to Random Variables For any event A can define the indicator random variable for A XA x 0 05 0 05 0 0 3 0 2 0 1 0 3 1 if x A 0 if x A 1 0 55 0 0 45 Definition Expectation The expectation or expected value of a random variable X is written as E X and is E X Pr x X x k Pr X k x S k X is a function on the sample space S X has a distribution on its values A Quick Calculation What if I flip a coin 2 times What is the expected number of heads E X S HH TT TH HT Pr x X x x S X 2 0 1 k k Pr X k A Quick Calculation What if I flip a coin 3 times What is the expected number of heads E X 1 8 0 3 8 1 3 8 2 1 8 3 1 But Pr X 1 5 0 Moral don t always expect the expected Pr X E X may be 0 Type Checking A Random Variable is the type of thing you might want to know an expected value of If you are computing an expectation the thing whose expectation you are computing is a random variable Indicator R V s E XA Pr A For any event A can define the indicator random variable for A XA x 1 if x A 0 if x A E XA 1 Pr XA 1 Pr A 1 A 0 Adding Random Variables If X and Y are random variables on the same set S then Z X Y is also a random variable Z x X x Y x E g rolling two dice X 1st die Y 2nd die Z sum of two dice Adding Random Variables Example Consider picking a random person in the world Let X length of the person s left arm in inches Y length of the person s right arm in inches Let Z X Y Z measures the combined arm lengths Independence Two random variables X and Y are independent if for every a b the events X a and Y b are independent How about the case of X 1st die Y 2nd die X left arm Y right arm Linearity of Expectation If Z X Y then E Z E X E Y Even if X and Y are not independent E Z Pr x Z x x S Pr x X x Y x x S Pr x X x Pr x Y x x S x S E X E Y Linearity of Expectation E g 2 fair flips X 1st coin Y 2nd coin Z X Y total heads What is E X E Y E Z 1 0 1 HT 1 1 2 HH 0 0 0 TT 0 1 1 TH Linearity of Expectation E g 2 fair flips X at least one coin is heads Y both coins are heads Z X Y Are X and Y independent What is …
View Full Document
Unlocking...