Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6An easy questionSlide 8A related questionSlide 10Pictorial viewReason about expectations too!Expected number of headsSlide 14Infinite Probability spacesGeneral pictureSetting that doesn’t fit our modelSlide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Slide 46Slide 47Slide 48Slide 49Slide 50Slide 51Slide 52Slide 53Slide 54Slide 55Slide 56Slide 57Slide 58Slide 59Slide 60Slide 61Slide 6215-251Great Theoretical Ideas in Computer ScienceInfinite Sample spacesand Random WalksLecture 12 (October 4, 2007)p1-p...ppp1-p1-pProbability RefresherWhat’s a Random Variable?A Random Variable is a real-valued function on a sample space SE[X+Y] = E[X] + E[Y]Probability RefresherWhat does this mean: E[X | A]?Probability RefresherWhat does this mean: E[X | A]?Pr[ A ] = Pr[ A | B ] Pr[ B ] + Pr[ A | B ] Pr[ B ]Is this true:Yes!Probability RefresherWhat does this mean: E[X | A]?E[ X ] = E[ X | A ] Pr[ A ] + E[ X | A ] Pr[ A ]Pr[ A ] = Pr[ A | B ] Pr[ B ] + Pr[ A | B ] Pr[ B ]Is this true:Yes!Similarly:An easy question 0 1 1.5 2But it never actually gets to 2. Is that a problem?Answer: 2But it never actually gets to 2. Is that a problem?No, by i=0 f(i), we really 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 to 2.1nA related questionSuppose 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)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,A A related question questionPictorial viewSample 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.p1-p...ppp1-p1-pp1-p...ppp1-p1-pReason about expectations too!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.Suppose A is a nodein this treePr(x|A)=product of edges on path from A to x.AExpected number of headsFlip bias-p coin until heads. What is expected number of flips?p1-p...ppp1-p1-pExpected number of headsp1-p...ppp1-p1-pE[X] = E[X|B] × Pr(B) + E[X|:B] × Pr(:B)Let X = # flips.B = event “1st flip is heads”Solving: p × E[X] = p + (1-p) E[X] = 1/p.= 1 × p + (1 + E[X]) × (1-p).Infinite Probability spacesNotice 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 pictureLet sample space S be leaves of a choice tree.Let Sn = {leaves at depth · n}.For event A, let An = A \ Sn.If limn!1Pr(Sn)=1, can define:Pr(A)=limn!1Pr(An).p1-p...ppp1-p1-pSetting that doesn’t fit our modelEvent: “Flip coin until #heads > 2*#tails.”There’s a reasonable chance this will never stop...How to walk home drunkNo newideasSolve HWproblemEatWaitWorkWork0.30.30.40.990.01probabilityHungryAbstraction of Student LifeAbstraction of Student LifeLike finite automata, but instead of a determinisic or non-deterministic action, we have a probabilistic actionExample questions: “What is the probability of reaching goal on string Work,Eat,Work?”No newideasSolve HWproblemEatWaitWorkWork0.30.30.40.990.01Hungry-Simpler:Random Walks on GraphsAt any node, go to one of the neighbors of the node with equal probability-Simpler:Random Walks on GraphsAt any node, go to one of the neighbors of the node with equal probability-Simpler:Random Walks on GraphsAt any node, go to one of the neighbors of the node with equal probability-Simpler:Random Walks on GraphsAt any node, go to one of the neighbors of the node with equal probability-Simpler:Random Walks on GraphsAt any node, go to one of the neighbors of the node with equal probability0 nkRandom Walk on a LineYou go into a casino with $k, and at each time step, you bet $1 on a fair gameYou leave when you are broke or have $nQuestion 1: what is your expected amount of money at time t?Let Xt be a R.V. for the amount of $$$ at time t0 nkRandom Walk on a LineYou go into a casino with $k, and at each time step, you bet $1 on a fair gameYou leave when you are broke or have $nXt = k + 1 + 2 + ... + t, (i is RV for change in your money at time i)So, E[Xt] = kE[i] = 00 nkRandom Walk on a LineYou go into a casino with $k, and at each time step, you bet $1 on a fair gameYou leave when you are broke or have $nQuestion 2: what is the probability that you leave with $n?Random Walk on a LineQuestion 2: what is the probability that you leave with $n?E[Xt] = kE[Xt] = E[Xt| Xt = 0] × Pr(Xt = 0) + E[Xt | Xt = n] × Pr(Xt = n) + E[ Xt | neither] × Pr(neither)As t ∞, Pr(neither) 0, also somethingt < nHence Pr(Xt = n) k/n k = n × Pr(Xt = n) + (somethingt) × Pr(neither)0 nkAnother Way To Look At ItYou go into a casino with $k, and at each time step, you bet $1 on a fair gameYou leave when you are broke or have $nQuestion 2: what is the probability that you leave with $n?= probability that I hit green before I hit red-What is chance I reach green before red?Random Walks and Electrical NetworksSame as voltage if edges are resistors and we put 1-volt battery between green and red-Random Walks and Electrical NetworksSame as equations for voltage if edges all have same resistance!px = Pr(reach green first starting from x)pgreen= 1, pred = 0And for the rest px = Averagey Nbr(x)(py)0 nkAnother Way To Look At ItYou go into a casino with $k, and at each time step, you bet $1 on a fair gameYou leave when you are broke or have $nQuestion 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 get back to your hotelHow should you do this?Requires a good memory and a piece of chalkDepth First Search!Getting Back Home-How about walking randomly?Will this work?When will I get home?Is Pr[ reach home ] = 1?What is E[ time to reach home ]?Pr[ will reach home ] = 1We Will Eventually Get HomeLook
View Full Document
Unlocking...