115-251Great Theoretical Ideas in Computer ScienceInfinite Sample spacesand Random WalksLecture 12 (October 1, 2009)p1-pppp1-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]?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:Air Marshal ProblemEvery passenger has an assigned seatThere are n-1 passengers and n seatsBefore the passengers board, an air marshal sits on a random seatWhen a passenger enters the plane, if their assigned seat is taken, they pick a seat at randomWhat is the probability that the last passenger to enter the plane sits in their assigned seat?Infinite Sample Spaces2An easy question0 1 1.5 2But it never actually gets to 2. Is that a problem?Answer: 2What is ∑i=0 (½)i ?∞But it never actually gets to 2. Is that a problem?∞nNo, by ∑i=0 f(i), we really mean limn→ ∞∑i=0f(i).if this limit is undefined, so is the sumIn this case, the partial sum is 2-(½)n, which goes to 2.A related questionSuppose I flip a coin of bias p, stopping when I first get heads.What’s the chance that I:Flip exactly once?pFlip exactly two times?(1-p)pFlip exactly k times?(1-p)k-1pEventually stop?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 + ... = 1Or, using q = 1-p,A A related questionquestion∑i = 0∞qi=11-qExpected number of flipsFlip bias-p coin until you see heads.Let r.v. Z = number of flips until headsWhat is E[Z]?Pictorial 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→∞.p1-pppp1-p1-px3p1-pppp1-p1-pReason about expectations too!E[Z] = ∑xPr(x) Z(x).E[Z|A] = ∑x∈ APr(x|A) Z(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 headsp1-pppp1-p1-pE[Z] = E[Z|A] × Pr(A) + E[Z|¬A] × Pr(¬A)Let Z = # flips until headsA = event “1st flip is heads”Solving: p × E[Z] = p + (1-p)⇒ E[Z] = 1/p.= 1 × pAA¬+ (1 + E[Z]) × (1-p).Geometric(p) r.v.Z = Number of flips with bias-p coin until you see a headsE[Z] = 1/pFor unbiased coin (p = ½), expected value = 2 flipsInfinite Probability spacesNotice we are using infinite probability spaces here, but we really only defined things for finitespaces 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→∞.A definition for infinite spacesLet sample space S be leaves of a choice tree.p1-pppp1-p1-pLet Sn= {leaves at depth ≤ n}.For event A, let An= A∩ Sn.If limn→∞Pr(Sn)=1, can define:Pr(A)=limn→∞Pr(An).Setting that doesn’t fit our modelEvent: “Flip coin until #heads > 2 × #tails.”There’s a reasonable chance this will never stop...4Random Walks:or, 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 probability5-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 Xtbe 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,(δiis 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/nk = n × Pr(Xt= n) + (somethingt) × Pr(neither)60 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?7Will 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 at the first n stepsThere is a non-zero chance p1that we get homeIn fact, p1≥ (1/n)nSuppose we don’t reach home in first n stepsThen, wherever we are, there is a chance p2≥ (1/n)nthat we hit home in the next n steps from
View Full Document
Unlocking...