15 251 Great Theoretical Ideas in Computer Science Infinite Sample spaces and Random Walks Lecture 12 October 4 2007 p 1 p p 1 p p 1 p p 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 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 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 An easy question Answer 2 0 2 1 1 5 But it never actually gets to 2 Is that a problem But it never actually gets to 2 Is that a problem 1 No by i 0 f i we really n mean limn 1 i 0 f i if this is undefined so is the sum In this case the partial sum is 2 n which goes 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 Ans p Flip exactly two times Ans 1 p p Flip exactly k times Ans 1 p k 1p Eventually stop Ans 1 assuming p 0 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 Pictorial view 1 p p 1 p p 1 p p p 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 1 Reason about expectations too p Suppose A is a node in this tree p A 1 p p 1 p p E X x Pr x X x E X A x2 A Pr x A X x I e it is as if we started the game at A Pr x A product of edges on path from A to x 1 p Expected number of heads p 1 p p 1 p p 1 p p What is expected number of flips Flip bias p coin until heads Expected number of heads p 1 p p Let X flips 1 p p E X E X B Pr B E X B Pr B 1 p 1 E X 1 p Solving p E X p 1 p E X 1 p p B event 1st flip is 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 Infinite probability spaces can sometimes be weird 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 1 General picture Let sample space S be leaves of a choice tree Let Sn leaves at depth n If limn 1Pr Sn 1 can define Pr A limn 1Pr An 1 p p 1 p p 1 p p For event A let An A Sn p Setting that doesn t fit our model Event Flip coin until heads 2 tails There s a reasonable chance this will never stop How to walk home drunk Abstraction of Student Life Eat No new ideas Wait Hungry Work 0 3 0 4 0 3 probability Work 0 01 Solve HW problem 0 99 Abstraction of Student Life No new ideas Eat Wait Hungry Work Like finite automata 0 3 0 4 of a but instead 0 99 0 01 determinisic or non0 3 deterministic action we have a probabilistic Work Solve HW action 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 voltage if edges all have same resistance 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 voltage k k n Pr hitting n before 0 starting at k Getting Back Home Lost in a city you want to …
View Full Document
Unlocking...