15 251 Some Great Theoretical Ideas in Computer Science for This Course Probability Refresher What s a Random Variable A Random Variable is a real valued function on a sample space S E X Y E X E Y Probability Refresher What does this mean E X A Is this true Pr A Pr A B Pr B Pr A B Pr B Yes Similarly E X E X A Pr A E X A Pr A Air Marshal Problem Every passenger has an assigned seat There are n 1 passengers and n seats Before the passengers board an air marshal sits on a random seat When a passenger enters the plane if their assigned seat is taken they pick a seat at random What is the probability that the last passenger to enter the plane sits in their assigned seat Several years ago Berkeley faced a law suit 1 of male applicants admitted to graduate school was 10 2 of female applicants admitted to graduate school was 5 Grounds for discrimination SUIT Berkeley did a survey of its departments to find out which ones were at fault Every department was more likely to admit a female than a male of females accepted to department X of female applicants to department X of males accepted to department X of male applicants to department X How can this be Answer Women tended to apply to departments that admit a smaller percentage of their applicants Women Men Dept Applied Accepted Applied Accepted A 99 4 1 0 B 1 1 99 10 total 100 5 100 10 A single summary statistic such as an average or a median may not summarize the data well Try to get a white ball Better Choose one box and pick a random ball from it Max the chance of getting a white ball 5 11 3 7 Try to get a white ball Better Better 6 9 9 14 Try to get a white ball Better Better Try to get a white ball Better Better Better 11 20 12 21 Simpson s Paradox Arises all the time Be careful when you interpret numbers Department of Transportation requires that each month all airlines report their on time record of on time flights landing at nation s 30 busiest airports of total flights into those airports http www bts gov programs oai Different airlines serve different airports with different frequency An airline sending most of its planes into fair weather airports will crush an airline flying mostly into foggy airports It can even happen that an airline has a better record at each airport but gets a worse overall rating by this method Alaska airlines LA Phoenix San Diego SF Seattle America West on time flights on time flights 88 9 94 8 91 7 559 233 232 85 6 92 1 85 5 811 5255 448 83 1 85 8 605 71 3 449 214 76 7 262 6 Alaska Air beats America West at each airport OVERALL 86 7 377 89 1 7225 but America West has5a better overall rating Geometric Random Variable Flip a coin with probability p of heads Let X number of times the coin has to be flipped until we get a heads E X E X flip 1 is H Pr flip 1 is H E X flip 1 is T Pr flip 1 is T p E X 1 1 p p E X 1 p 1 p E X 1 p CMULand All CMU SCS students fly off to space and colonize the moon Faced with the problem that there are more men than women the authorities impose a new rule When having kids stop after you have a girl Will the number of new girls be higher than the number of new boys What if the rule is stop after having two girls Coupon Collector s Problem There are n types of coupons in cereal boxes Want to collect them all On average how many cereal boxes do I have to buy to get them all Random Walks Lecture 12 February 19 2009 How to walk home drunk Abstraction of Student Life Eat No new ideas Wait Hungry Work 0 3 0 4 0 3 probability 0 01 Solve HW problem 0 99 Work Abstraction of Student Life Eat No new ideas Wait Hungry Work 0 3 0 4 0 3 0 01 0 99 Work Solve HW Example questions What is the probability problem of reaching goal on string Work Eat Work Simpler Random Walks on Graphs At any node go to one of the neighbors of the node with equal probability Simpler Random Walks on Graphs At any node go to one of the neighbors of the node with equal probability Simpler Random Walks on Graphs At any node go to one of the neighbors of the node with equal probability Simpler Random Walks on Graphs At any node go to one of the neighbors of the node with equal probability Simpler Random Walks on Graphs At any node go to one of the neighbors of the node with equal probability Random Walk on a Line You go into a casino with k and at each time step you bet 1 on a fair game You leave when you are broke or have n 0 n k Question 1 what is your expected amount of money at time t Let Xt be a R V for the amount of at time t Random Walk on a Line You go into a casino with k and at each time step you bet 1 on a fair game You leave when you are broke or have n 0 n k Xt k 1 2 t i is RV for change in your money at time i E i 0 So E Xt k Random Walk on a Line You go into a casino with k and at each time step you bet 1 on a fair game You leave when you are broke or have n 0 n k Question 2 what is the probability that you leave with n Random Walk on a Line Question 2 what is the probability that you leave with n E Xt k E Xt E Xt Xt 0 Pr Xt 0 E Xt Xt n Pr Xt n E Xt neither Pr neither k n Pr Xt n somethingt Pr neither As t Pr neither 0 also somethingt n Hence Pr Xt n k n Another Way To Look At It You go into a casino with k and at each time step you bet 1 on a fair game You leave when you are broke or have n 0 n k Question 2 what is the probability that you leave with n probability that I hit green before I hit red Random Walks and Electrical Networks What is chance I reach green before red Same as voltage if edges are resistors and we put 1 volt battery between green and Random Walks and Electrical Networks px Pr reach green first starting from x pgreen 1 pred 0 And for the rest px Averagey Nbr x py Same as equations for …
View Full Document
Unlocking...