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 RRecitation 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