George drives his car to the theater, which is at the end of a one-way street. There are parking places along the side of the street and a parking garage that costs $5 at the theater. Each parking place is independently occupied or unoccupied with probability 1/2. If George parks n parking places away from the theater, it costs him n cents (in time and shoe leather) to walk the rest of the way. George is myopic and can only see the parking place he is currently passing. If George has not already parked by the time he reaches the nth place, he first decides whether or not he will park if the place is unoccupied, and then observes the place and acts according to his decision. George can never go back and must park in the parking garage if he has not parked before.
(a) Model the above problem as a two-state dynamic programming problem. In the 'driving' state, state 2, there are two possible decisions: park if the current place is unoccupied or drive on whether or not the current place is unoccupied.
(b) Find v∗(n, u), the minimum expected aggregate cost for n stages (i.e., immediately before observation of the nth parking place) starting in state i = 1 or 2; it is sufficient to express v∗(n, u) in terms ofv∗(n - 1). The final costs, in cents, at stage 0 should be v2(0) = 500, v1(0) = 0.
(c) For what values of n is the optimal decision the decision to drive on?
(d) What is the probability that George will park in the garage, assuming that he follows the optimal policy?
Text Book: Stochastic Processes: Theory for Applications By Robert G. Gallager.