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=0Recitation 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