6. Homework 6 (Chap 4)4.1. 4.3. 4.2. 4.4.6. Homework 6 (Chap 4)p. 98 #4.1, 2, 3, 44.1. We have a simple random walk with absorbing walls on {0, 1, 2, · · · , 10} with payofffunction:x : 0 1 2 3 4 5 6 7 8 9 10f(x) : 0 2 4 3 10 0 6 4 3 3 0Find the optimal stopping time rule and the value function v(x) which gives the expectedpayoff at each state.This one is easy. You use the convex function rule. Interpolating linearly we get:x : 0 1 2 3 4 5 6 7 8 9 10f(x) : 0 2 4 3 10 0 6 4 3 3 0v(x) : 0 2.5 5 7.5 10 8.6 7.2 5.8 4.4 3 0The optimal stopping rule is to stop at x = 4, 9 and continue otherwise (if you can).4.3. (a) Add a cost function of g(x) = .75 at each move.Now, when we have to subtract g(x) at each single gap, 2g(x) at each double gap and3g, 4g, 3g at each triple gap. If the gap were longer we would have to solve the linearrecursion:v(k + 1) =12v(k ) +12v(k + 2) − g(k + 1)For constant g the solution, for a gap of n − 1, isv(k ) = −k(n − k)g(The particular solution is v(k) = k2g. The homogeneous solutions are v(k) = 1, v(k) = k.)This gives:x : 0 1 2 3 4 5 6 7 8 9 10f(x) : 0 2 4 3 10 0 6 4 3 3 0v1(x) : 0 2.5 5 7.5 10 8.6 7.2 5.8 4.4 3 0v2(x) : 0 2 4.666 7.333 10 8 6 4.5 3 3 0v3(x) : 0 2 4 7 10 7.25 6 4 3 3 0v(x) : 0 2 4 6.25 10 7.25 6 4 3 3 0The optimal stopping rule is to continue only at x = 3, 5.(b) a discount rate of α = .95.By iteration we get the following:x : 0 1 2 3 4 5 6 7 8 9 10f(x) : 0 2 4 3 10 0 6 4 3 3 0v(x) : 0 2 4.14 6.71 10 7.6 6 4.55 3.58 3 0The optimal stopping rule is to stop at x = 1, 4, 6, 9. You can get the exact value of the(present) value f unction v(x) by solving the equationv(x) = max(f(x), α(v(x − 1) + v(x + 1))/2)10to getv(2) =1710413, v(3) =2774413andv(7) =1881413, v(8) =1482413(c) with both cost g(x) = .75 and discount rate of α = .95.By iteration we get the following:x : 0 1 2 3 4 5 6 7 8 9 10f(x) : 0 2 4 3 10 0 6 4 3 3 0v(x) : 0 2 4 5.9 10 6.85 6 4 3 3 0The optimal stopping rule is to continue at x = 3, 5 and stop elsewhere. You can get theexact value of the (present) value f unction v(x) by solving the equationv(x) = max(f(x), α(v(x − 1) + v(x + 1))/2 − g(x))So,v(3) = .95(14/2) − .75 = 5.9andv(5) = .95(16/2) − .75 = 6.85are exact.114.2. Now you roll two dice and f(x) is the sum of the two numbers except for f(7) = 0.a) What is your e xpected payoff if you always stop after the first roll?This is justE =Xp(x)f(x) = 210/36 = 35/6 ≈ 5.8333b) What is your optimal payoff?The question itself is a hint. Instead of trying to compute vn(x) we compute the expectedpayoff Enfor vn.E1=Xx6=7p(x)12 = 10Given Enwe can compute En+1byEn+1=Xx6=7p(x) max(f(x), En)which gives:E2= 8.4444E3= 7.4691E4= 7.001E5= 6.806E6= 6.7247Once you realize that the optimal stopping time is to stop when you get more than 7 thenyou can calculate the expected value:E(f(XT)) = 140/21 ≈ 6.66667Since this is more than 6, the strategy is correct.4.4. a) Do it again with cost function g = [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1].Start with E1= 10. And repeat:En+1=Xx6=7p(x) max(f(x), En− g(x))This gives:E2= 7.5E3= 6.3194E4= 5.9977E5= 5.9443E6= 5.9398E7= 5.9394E8= 5.9394So, E = 5.9394. and the optimal strategy is to continue only if you get 2 or 3. You can solvefor E byE = (E − 2)(3/36) + 202/36to get E = 196/33 ≈ 5.939394 (If you get a 4 you should keep it instead of paying 2 andgetting 5.9394 for a net of 3.9394)12b) with discount rate α = .8Start with E1= 10. And repeat:En+1=Xx6=7p(x) max(f(x), .8En)This gives:E2= 7.2222E3= 6.3272E4= 6.1283E5= 6.0949E6= 6.0904E7= E8= 6.0898So, E = 6.0898 and the optimal strategy is to continue only if you get 2,3 or 4. You can getthe exact value for E by solving the equationE = 6(.8E)/36 + 190/36which givesE = 1900/312 ≈ 6.0897(If you get a 5 you should keep it instead of rolling again to get an expected discountedpayoff of 80% of 6.0897 which would be 4.8718)c) both.Start with E1= 10. And repeat:En+1=Xx6=7p(x) max(f(x), .8En− g(x))This gives:E2= 6.5278E3= 5.8796E4= 5.8529E5= E6= 5.8523So, E = 5.8523 and the optimal strategy is to continue only if you get 2. You can get exactanswers by solving for E:E = (.8E − 2)/36 + 208/36This givesE = 2060/352 ≈ 5.8523(With a 2 you s hould pay the fee of 2 and get a net payoff of5.8523 · 0.8 − 2 = 2.6818)• What is your expected payoff if you always stop after the first roll?In all three cases this is the same as before (since you don’t pay to continue and you don’tget discounted)E =Xp(x)f(x) = 210/36 = 35/6 ≈
View Full Document
Unlocking...