6.042/18.062] Mathematics for Computer Science May11,2005 Srini devadas and Eric Lehman Notes for Recitation 23 1 Stencil the flea There is a small flea named Stencil. To his right, there is an endless flat plateau. One inch to his left is the Cliff of Doom, which drops to a raging sea filled with flea-eating monsters Cliff of doom 2222 Each second, Stencil hops 1 inch to the right or 1 inch to the left with equal probability, independent of the direction of all previous hops. If he ever lands on the very edge of the cliff, then he teeters over and falls into the sea Our job is to analyze the life of Stencil. Does he have any chance of avoiding a fatal plunge? If not, how long will he hop around before he takes the plunge?
6.042/18.062J Mathematics for Computer Science May 11, 2005 Srini Devadas and Eric Lehman Notes for Recitation 23 1 Stencil the flea There is a small flea named Stencil. To his right, there is an endless flat plateau. One inch to his left is the Cliff of Doom, which drops to a raging sea filled with fleaeating monsters. 1 inch Cliff of Doom Each second, Stencil hops 1 inch to the right or 1 inch to the left with equal probability, independent of the direction of all previous hops. If he ever lands on the very edge of the cliff, then he teeters over and falls into the sea. oops... Our job is to analyze the life of Stencil. Does he have any chance of avoiding a fatal plunge? If not, how long will he hop around before he takes the plunge?
Recitation 2 Problem 1. Let's begin with a simpler problem. Suppose that Stencil is n inches from the left side of an island w inches across: Cliff of Cliff of Doom Disaster n other words, Stencil starts at position n, for some 0 n w and there are cliffs at positions O and w. Let Rn be the probability he falls to the right off the Cliff of Disaster, given that he starts at position n (a)What are the values of ro and Rn? When 0< n< w, can you express Rn in terms of Rn-1 and Rn+1?(Hint: Total Probability!) Solution. If n=W, he starts at position w and immediately falls from the Cliff of Disaster, so Ru= 1. On the other hand, if he starts at position 0, then he falls from the Cliff of Doom immediately, so Ro=0 Now suppose that he stands somewhere in the middle of the island, so that 0<n< Then we can break the analysis of his fate into two cases based on the direction of his first hop If his first hop is to the left, then he lands at position n- 1 and eventually falls off the Cliff of Disaster with probability Rn-1 On the other hand, if his first hop is to the right, then he lands at position n +1 and eventually falls off the Cliff of Disaster with probability Rn+1 Therefore by the Total probability theorem we have Rn=oRn-1+oRn+1 (b) Solve the linear recurrence (you dont see any linear recurrence? talk to your TA to find Rn. (There is our usual guide on the last page. Solution. We rearrange the terms in the recurrence equation R 2Rn-Rn- The characteristic equation is 2x+1=0 This equation has a double root at a =1. There is no inhomogenous part, so the general solution has the form R
Recitation 23 2 Problem 1. Let’s begin with a simpler problem. Suppose that Stencil is n inches from the left side of an island w inches across: Cliff of Disaster Cliff of Doom 0 n w In other words, Stencil starts at position n, for some 0 ≤ n ≤ w and there are cliffs at positions 0 and w. Let Rn be the probability he falls to the right off the Cliff of Disaster, given that he starts at position n. (a) What are the values of R0 and Rn? When 0 < n < w, can you express Rn in terms of Rn−1 and Rn+1? (Hint: Total Probability!) Solution. If n = w, he starts at position w and immediately falls from the Cliff of Disaster, so Rw = 1. On the other hand, if he starts at position 0, then he falls from the Cliff of Doom immediately, so R0 = 0. Now suppose that he stands somewhere in the middle of the island, so that 0 < n < w. Then we can break the analysis of his fate into two cases based on the direction of his first hop: • If his first hop is to the left, then he lands at position n − 1 and eventually falls off the Cliff of Disaster with probability Rn−1. • On the other hand, if his first hop is to the right, then he lands at position n + 1 and eventually falls off the Cliff of Disaster with probability Rn+1. Therefore, by the Total Probability Theorem, we have: 1 1 Rn = Rn−1 + Rn+1 2 2 (b) Solve the linear recurrence (you don’t see any linear recurrence? talk to your TA!) to find Rn. (There is our usual guide on the last page.) Solution. We rearrange the terms in the recurrence equation: Rn+1 = 2Rn − Rn−1 The characteristic equation is: 2 x − 2x + 1 = 0 This equation has a double root at x = 1. There is no inhomogenous part, so the general solution has the form: Rn = a · 1n n1n + b · = a + bn
Recitation 2 Substituting in the boundary conditions Ro =0 and Rw= l gives two linear equa tions 1=a+b The solution to this system is a =0, b=1/. Therefore, the solution to the recur- fence Rn=n/w (c) So you know the probability that Stencil falls off the right side. Can you quickly deduce the probability that he will . falls off the left side?. lives on forever? g at pi hich is(w-n)/ This is bad news. The probability that Stencil eventually falls off one cliff or the other Is Theres no hope! The probability that he hops around on the island forever is zero (d) Now let's go back to the original probler m, where Stencil is 1 inch from the left edge of an infinite plateau. What is the probability that he lives on forever? Solution. The probability that he eventually falls into the sea is 1 lim Our little friend is doomed!
Recitation 23 3 Substituting in the boundary conditions R0 = 0 and Rw = 1 gives two linear equations: 0 = a 1 = a + bw The solution to this system is a = 0, b = 1/w. Therefore, the solution to the recurrence is: Rn = n/w (c) So you know the probability that Stencil falls off the right side. Can you quickly deduce the probability that he will . . .falls off the left side? . . . lives on forever? Solution. We exploit the symmetry of the problem: the probability that he falls off the left side starting at position n is the same as the probability that he falls of the right side starting at position w − n, which is (w − n)/n. This is bad news. The probability that Stencil eventually falls off one cliff or the other is: n + w − n = 1 w w There’s no hope! The probability that he hops around on the island forever is zero. (d) Now let’s go back to the original problem, where Stencil is 1 inch from the left edge of an infinite plateau. What is the probability that he lives on forever? Solution. The probability that he eventually falls into the sea is: w − 1 lim = 1 w→∞ w Our little friend is doomed!
Recitation 2 Problem 2. By now you must already know the tragic fate that awaits poor little Stencil the flea. On the bright side, though, Stencil may get to hop around for a while before he sinks beneath the waves let's find out how much he is expected to live. We should begin with the simpler setup as before: Cliff of Cliff of Doom Disaster Let Xn be the expected number of hops he takes before falling off a cliff (a)What are the values of Xo and Xu? If0< n< w, can you express Xn in terms of Xn-1 and Xn?(Hint: Total Expectation! Solution. If he starts at either edge of the island, then he dies immediately If he starts somewhere in the middle of the island(0 n< w), then we can ag break down the analysis into two cases based on his first hop If his first hop is to the left, then he lands at position n-1 and can expect to live for another Xn-1 steps If his first hop is to the right, then he lands at position n+ l and his expected lifespan is Xn+1 Thus, by the Total Expectation Theorem and linearity, his expected lifespan is Xn=1+=Xn-1+=Xn+1 The leading 1 accounts for his first hop (b) Now you should solve the recurrence Solution We can rewrite the last line as 2Xn-X As before, the characteristic equation is x2-2x+1=0
Recitation 23 4 Problem 2. By now you must already know the tragic fate that awaits poor little Stencil the flea. On the bright side, though, Stencil may get to hop around for a while before he sinks beneath the waves. Let’s find out how much he is expected to live. We should begin with the simpler setup as before: Cliff of Disaster Cliff of Doom 0 n w Let Xn be the expected number of hops he takes before falling off a cliff. (a) What are the values of X0 and Xw? If 0 < n < w, can you express Xn in terms of Xn−1 and Xn? (Hint: Total Expectation!) Solution. If he starts at either edge of the island, then he dies immediately: X0 = 0 Xw = 0 If he starts somewhere in the middle of the island (0 < n < w), then we can again break down the analysis into two cases based on his first hop: • If his first hop is to the left, then he lands at position n − 1 and can expect to live for another Xn−1 steps. • If his first hop is to the right, then he lands at position n + 1 and his expected lifespan is Xn+1. Thus, by the Total Expectation Theorem and linearity, his expected lifespan is: 1 1 Xn = 1 + Xn−1 + Xn+1 2 2 The leading 1 accounts for his first hop. (b) Now you should solve the recurrence. Solution. We can rewrite the last line as: Xn+1 = 2Xn − Xn−1 − 2 As before, the characteristic equation is: 2 x − 2x + 1 = 0
Recitation 23 There is a double-root at 1, so the homogenous solution has the form a+ Theres an inhomogenous term, so we also need to find a particular solution. Since this term is a constant, we should try a particular solution of the form Xn=c and then try Xn=c+dn and then Xn=c+dn +en and so forth. As it turns out, the first two possibilities don,'t work, but the third does. Substituting in this guess gives 2Xn-Xn-I c+dn+1)+e(n+1)2=2(c+dn+en2)-(c+d(n-1)+e(n-1)2) All the c and d terms cancel, so Xn=c+dn-n2 is a particular solution for all c and d. For simplicity, lets take c=d=0. Thus, our particular solution is Xn=-n Adding the homogenous and particular solutions gives the general form of the so- on Xn=a+bn -n' Substituting in the boundary conditions Xo=0 and Xw=0 gives two linear equa tions 0=a+b The solution to this system is a=0 and b= w. Therefore the solution to the recurrence equation is Xn=wn-n=n(w-n (c) Return to the original problem, where Stencil has the Cliff of Doom 1 inch to his left and an infinite plateau to this right: What is his expected lifespan there? Solution. In this case, his expected lifespan is lim1(u-1)=∞ Yes, Stencil is expected to live forever! (d)Compare your answer to the previous part and your answer to the last part of the previous problem. Anything troublesome? Solution. So, Stencil is certain to eventually fall off the cliff into the sea-but his expected lifespan is infinite! This sounds almost like a contradiction, but both answers are correct
Recitation 23 5 There is a doubleroot at 1, so the homogenous solution has the form: Xn = a + bn There’s an inhomogenous term, so we also need to find a particular solution. Since this term is a constant, we should try a particular solution of the form Xn = c and then try Xn = c+dn and then Xn = c+dn +en2 and so forth. As it turns out, the first two possibilities don’t work, but the third does. Substituting in this guess gives: Xn+1 = 2Xn − Xn−1 − 2 2 2 c + d(n + 1) + e(n + 1)2 = 2(c + dn + en ) − (c + d(n − 1) + e(n − 1) ) − 2 e = −1 All the c and d terms cancel, so Xn = c + dn − n2 is a particular solution for all c and 2 d. For simplicity, let’s take c = d = 0. Thus, our particular solution is Xn = −n . Adding the homogenous and particular solutions gives the general form of the solution: Xn = a + bn − n 2 Substituting in the boundary conditions X0 = 0 and Xw = 0 gives two linear equations: 0 = a 0 = a + bw − w 2 The solution to this system is a = 0 and b = w. Therefore, the solution to the recurrence equation is: Xn = wn − n 2 = n(w − n) (c) Return to the original problem, where Stencil has the Cliff of Doom 1 inch to his left and an infinite plateau to this right: What is his expected lifespan there? Solution. In this case, his expected lifespan is: lim 1(w − 1) = ∞ w→∞ Yes, Stencil is expected to live forever! (d) Compare your answer to the previous part and your answer to the last part of the previous problem. Anything troublesome? Solution. So, Stencil is certain to eventually fall off the cliff into the sea— but his expected lifespan is infinite! This sounds almost like a contradiction, but both answers are correct!
Recitation 2 Here' s an informal explanation The probability that stencil falls from the cliff of Doom on the k-th step is approximately 1/k-3/2. Thus, the probability that he falls eventually is Pr(falls off cliff)2 k3/2 You can verify by integration that this sum converges. The exact sum actually con erges to 1. On the other hand, the expected time until he falls is Ex(hops until fall)a>k √k And you can verify by integration that this sum diverges. So our answers are com patible
Recitation 23 6 Here’s an informal explanation. The probability that Stencil falls from the Cliff of Doom on the kth step is approximately 1/k3/2 . Thus, the probability that he falls eventually is: � 1 ∞ Pr (falls off cliff) ≈ k3/2 k=1 You can verify by integration that this sum converges. The exact sum actually converges to 1. On the other hand, the expected time until he falls is: �∞ ∞ 1 � 1 Ex (hops until fall) ≈ k · = k3/2 √ k k=1 k=1 And you can verify by integration that this sum diverges. So our answers are compatible!