Great Theoretical Ideas In Computer Science Steven Rudich John Lafferty Lecture 20 Nov 3 2005 15 251 Classics CS 15 251 Fall 2005 Carnegie Mellon University 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 exactly 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 Expectatus Linearitus HMU Random Variable To use this new tool we will also need to understand the concept of a Random Variable Today s lecture not too much material but need to understand it well Probability Distribution A 2 finite probability distribution D a finite set S of elements samples each x2S has weight or probability p x 0 1 0 05 0 3 weights must sum to 1 0 2 0 05 0 S 0 1 0 3 Sample space Flip penny and nickel unbiased S HH TT TH HT Flip penny and nickel biased heads probability p S HH p2 TT 1 p 2 TH p 1 p HT p 1 p Probability Distribution S 0 05 0 05 0 0 1 0 3 0 2 0 3 An event is a subset S A 0 05 0 05 0 0 1 0 3 0 2 Pr A x 0 3 2 A p x 0 55 Running Example I throw a white die and a black die Sample space S 1 1 1 2 1 6 2 1 2 2 2 6 3 1 3 2 3 6 4 1 4 2 4 6 5 1 5 2 5 6 E 6 1 event that 6 2 6 6 1 3 1 4 1 5 2 3 2 4 3 3 3 4 2 5 Pr x 1 36 8 x 2 S 3 5 4 3 4 4 4 5 5 3 5 4 5 5 sum 6 3 3 6 4 6 5 Pr E E S proportion of E in S 3 36 New concept Random Variables Random Variables Random Variable a real valued function on S Toss a white die and a black die Examples X value of white die X 3 4 3 X 1 6 1 etc Y sum of values of the two dice Y 3 4 7 Y 1 6 7 etc W value of white die value of black die W 3 4 34 Y 1 6 16 Z 1 if two dice are equal 0 otherwise Z 4 4 1 Z 1 6 0 etc Sample space S 1 1 1 2 1 6 2 1 2 2 2 6 3 1 3 2 3 6 4 1 4 2 4 6 5 1 5 2 5 6 6 1 6 2 6 6 1 3 1 4 1 5 2 3 2 4 2 5 3 3 3 4 3 5 4 3 4 4 4 5 5 3 5 4 5 5 6 3 6 4 6 5 E g 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 a function from S to the reals or think of the induced distribution on Two coins tossed X TT TH HT HH 0 1 2 counts the number of heads S HH TT 2 0 TH HT 1 Two views of random variables Think of a R V as a function from S to the reals or think of the induced distribution on Two coins tossed X TT TH HT HH 0 1 2 counts the number of heads S HH TT TH HT Distribution on the 2 reals 0 1 Two views of random variables Think of a R V as a function from S to the reals or think of the induced distribution on Two dice I throw a white die and a black die Sample space S 1 1 1 2 1 3 1 4 1 5 1 6 2 1 2 2 2 3 2 5 2 6 3 1 3 2 3 3 3 5 3 6 4 1 4 2 4 3 4 5 4 6 5 1 5 2 5 3 5 5 5 6 X 6 1 sum of both 6 3 dice 6 2 6 5 6 6 2 4 3 4 4 4 5 4 6 4 function with X 1 1 2 X 1 2 X 2 1 3 X 6 6 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 2 S X x a Two coins tossed X TT TH HT HH 0 1 2 counts the number of heads Pr X a Pr x S X x a S Pr X 1 X HH TT TH HT 2 0 1 Pr x 2 S X x 1 Pr TH HT Distribution on X Two dice I throw a white die and a black die X sum Sample space S 1 1 1 2 1 5 1 6 2 1 2 2 2 5 2 6 3 1 3 2 3 5 3 6 4 1 4 2 4 5 4 6 5 1 5 2 5 5 5 6 6 1 6 2 6 5 6 6 1 3 1 4 2 3 2 4 3 3 3 4 4 3 4 4 5 3 5 4 6 3 6 4 Pr X 6 Pr x S X x 6 5 36 Pr X a Pr x S X x a 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 2 S X x a X has a X is a function distribution on on the sample space S its values From Events to Random Variables For any event A can define the indicator random variable for A XA x 0 05 0 0 3 0 2 1 0 if x 2 A if x A 0 05 1 0 1 0 55 0 3 0 0 45 Definition expectation The expectation or expected value of a random variable X …
View Full Document
Unlocking...