Ada keeps her savings in a credit union box that holds whole coins only, at most N of them. Her wealth w is the number of coins in the box at the start of a period, w \in \{0, 1, \ldots, N\}. Each period her wealth grows by the gross return R (one plus the interest rate: R = 1.05 for 5 %) and she earns her wage y, so she has cash m = R\,w + y (not necessarily whole) to split between consumption c and next period's wealth w' (again a whole number from 0 to N):
A period with consumption c gives her \ln c; the future is discounted by \beta (beta, 0 < \beta < 1), and she plans forever. Her value function V solves the Bellman equation
over the w' in the grid with c > 0. Find it by value function iteration: start with V_0(w) = 0 for every w, and compute V_{k+1} from V_k by the right-hand side, for all w at once. Stop after the first update whose largest change, \max_w |V_{k+1}(w) - V_k(w)|, is below tol.
Write savings_vfi(N, y, R, beta, tol) that returns a tuple (iterations, policy): the number of updates made (including the last one), and the list policy with policy[w] the best w' for each w found in that last update. When several w' come within 1e-9 of the best value, take the smallest.
Examples
Input: N = 10, y = 2, R = 1.05, beta = 0.9, tol = 1e-6
Output: (129, [0, 0, 1, 2, 3, 4, 5, 6, 7, 7, 8])
Explanation: beta * R < 1: she is too impatient for the interest, so she runs her
savings down by about a coin a period.
Input: N = 10, y = 2, R = 1.2, beta = 0.9, tol = 1e-6
Output: (134, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 10])
Explanation: beta * R > 1: she adds a coin each period until the box is full.
Input: N = 6, y = 1, R = 1, beta = 0.5, tol = 0.01
Output: (3, [0, 0, 0, 1, 1, 1, 2])
Constraints
iterationsandpolicyare compared exactly
Goals
- Update a value function on a grid of wealth levels with the Bellman equation
- Stop when the largest change over the grid falls below a tolerance, and count the updates
- Read a saving policy off the last update and see how patience and interest shape it