15 251 Great Theoretical Ideas in Computer Science Infinite Sample spaces and Random Walks Lecture 12 October 1 2009 p 1 p p 1 p p 1 p p Probability Refresher 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 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 Infinite Sample Spaces 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 1 An easy question Answer 2 What is i 0 i But it never actually gets to 2 Is that a problem 0 1 1 5 2 But it never actually gets to 2 Is that a problem A related question Suppose I flip a coin of bias p stopping when I first get heads What s the chance that I Flip exactly once p Flip exactly two times 1 p p Flip exactly k times 1 p k 1p Eventually stop 1 assuming p 0 Expected number of flips Flip bias p coin until you see heads No by i 0 f i n we really mean limn i 0 f i if this limit is undefined so is the sum In this case the partial sum is 2 n which goes to 2 A related question Pr flip once Pr flip 2 times Pr flip 3 times 1 p 1 p p 1 p 2p 1 p 3p 1 Or using q 1 p q i 0 i 1 1 q Pictorial view 1 p p 1 p p 1 p p Let r v Z number of flips until heads x p What is E Z Sample space S leaves in this tree Pr x product of edges on path to x If p 0 Pr not halting by time n 0 as n 2 Reason about expectations too p 1 p p Suppose A is a node in this tree Expected number of heads A A 1 p p Pr x A product of edges on path from A to x Let Z flips until heads 1 p Infinite Probability spaces Notice we are using infinite probability spaces here but we really only defined things for finite spaces so far Z Number of flips with bias p coin until you see a heads Infinite probability spaces can sometimes be weird E Z 1 p Luckily in CS we will almost always be looking at spaces that can be viewed as choice trees where Pr haven t halted by time t 0 as t For unbiased coin p expected value 2 flips A definition for infinite spaces If limn Pr Sn 1 can define 1 E Z 1 p Solving p E Z p 1 p E Z 1 p Geometric p r v For event A let An A Sn 1 p p E Z E Z A Pr A E Z A Pr A E Z A x A Pr x A Z x I e it is as if we started the game at A Let Sn leaves at depth n 1 p p A event 1st flip is heads E Z x Pr x Z x Let sample space S be leaves of a choice tree A 1 p p 1 p p p p Setting that doesn t fit our model 1 p p Event Flip coin until heads 2 tails 1 p p 1 p p There s a reasonable chance this will never stop Pr A limn Pr An 3 Abstraction of Student Life Random Walks or how to walk home drunk Wait 0 3 0 4 0 3 Abstraction of Student Life Eat Wait Hungry Work probability No new ideas Eat No new ideas Work 0 01 0 99 Solve HW problem Simpler Random Walks on Graphs Hungry Work Like finite automata but 0 3 instead0 4 of a determinisic 0 99 0 01 or non deterministic 0 3 action we have a probabilistic action Work Solve HW Example questions What is the probability of problem 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 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 4 Simpler Random Walks on Graphs Simpler Random Walks on Graphs At any node go to one of the neighbors of the node with equal probability At any node go to one of the neighbors of the node with equal probability Random Walk on a Line 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 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 You leave when you are broke or have n 0 n 0 n k k Xt k 1 2 t i is RV for change in your money at time i 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 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 Question 2 what is the probability that you leave with n You leave when you are broke or have n E Xt k 0 n k Question 2 what is the probability that you leave with n 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 5 Random Walks and Electrical Networks 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 What is chance I reach green before red 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 Same as voltage if edges are resistors and we put 1 volt battery between green and red Random Walks and Electrical Networks Another Way To Look At It You go into a casino with k and at each time …
View Full Document
Unlocking...