3. Worksheet 3MATH 56A: STOCHASTIC PROCESSESWORKSHEET3. Worksheet 3The purpose of this worksheet is to practice the iteration algorithm, plot a convex valuefunction and determine the optimal stopping time.We have a simple random walk with states 0, 1, 2, 3, 4, 5 where the endpoints are absorbing.The payoff function is:f = (0, 5, 5, 10, 4, 0)(1) Plot the function f(x) and connects the dots.•• ••••(2) Find the value function v(x). This is the convex hull of the graph of f (x).•• ••••v = (0, 5, 7.5, 10, 5, 0)(3) Find the superharmonicu1(x) =(0 if x is absorbingmax f (y) if x is transientu1= (0, 10, 10, 10, 10, 0)(4) Find u2, u3, · · · The general formula is, for x transient,un+1(x) = max(f (x),Xp(x, y)un(y))For random walk this becomes:un+1(x) = maxf(x),un(x − 1) + un(x + 1)2If I call the second term ave(un) then:ave(u1) = (0, 5, 10, 10, 5, 0)u2= max(f, ave(u1)) = (0, 5, 10, 10, 5, 0)ave(u2) = (0, 5, 7.5, 7.5, 5, 0)1u3= max(f, ave(u2)) = (0, 5, 7.5, 10, 5, 0)ave(u3) = (0, 3.25, 7.5, 6.25, 5, 0)u4= max(f, ave(u3)) = (0, 5, 7.5, 10, 5, 0)(5) Show that unconverges to v as n → ∞.What I intended to ask in this problem is: Show that unconverges.Since u4= u3, the formula will give us un= u3for all n ≥ 3. So, the sequenceconverges to u3. The theorem is that the limit is v(x) = lim un(x).The proof of this, in this case, is as follows.First or all,v(x) ≤ u3(x).The intuitive reason for this is that each unis an optimistic estimate for the valuefunction and therefore greater or equal to the true value function v.Since v(x) ≥ f (x), the value function satisfiesv(x) = max(f (x),v(x − 1) + v(x + 1)2) ≥ max(f (x),f(x − 1) + f(x + 1)2) = u3(x)So,v(x) ≥ u3(x) ≥ v(x) ⇒ v(x) =
View Full Document
Unlocking...