# Dynamic Programming Notebook

## Euler Equation is Necessary

**not sufficient**.

What does that mean? Let’s remind oursevles of the euler Equation:

\begin{align} u’(c_{t})=\beta u’(c_{t+1})\label{eq:EE} \end{align}

it says that an optimal sequence of $c$ needs to satisfy this in every *adjacent* period. Suppose we have $u(c) = \ln(c)$. Then this becomes

\begin{align} c_{t+1} = \beta c_t \end{align}

So both of those here are optimal?

Well, both satisfy the Euler Equation (they were constructed with it). But

- They are clearly different - so which one is it?
- What about the transversality condition? No capital left at the end of the game?

## Deterministic Growth Model Dynamic Program

(This is my version of the example at Sargent and Stachurski’s quant-econ website. Please observe the license file at the root of that repository.)

In this notebook we’ll implement the deterministic growth model as a dynamic programming problem. We will assume log utility to get a closed form solution.
Remember that the problem is defined as
\begin{align}
V(k) &= \max_{0<k’<f(k)} \ln(f(k) - k’) + \beta V(k’)

f(k) & = k^\alpha

k_0 & \text{ given}
\end{align}

## Representing a function on $\mathbb{R}$ in a computer

- The first thing to realise is that we cannot represent $V(k),k\in \mathbb{R}$ on a computer. However, we can get an arbitrarily good approximation to $\mathbb{R}$.
- We will approximate $k$ at a finite number of points $K={k_1,\dots,k_n}$, called a
*grid*. - In other words, we will compute $V(k)$ above only at the list of points in $K$.
- There is a slight complication that arises from the $\max$ operator:
- Ideally, we would like to choose $c$ out of the
**continuous**interval $[0,f(k)]$, and not be restricted to the grid $K$. - In order to achieve this, we must find a way to represent $V(k)$ for values off the grid.
- In other words, we will know a list of values $V(k_1),\dots,V(k_n)$, but will most of the time need a value $V(x),x\in (k_i,k_{i+1})$ when we perform the operation $\max_{0<k’<f(k)}$.
- We will
*linearly interpolate*such a value $x$, which is similar to*connecting the dots*.

- Ideally, we would like to choose $c$ out of the

## Fire up **R**

Next, because of our log assumption, we know that there is a closed form solution here. It is characterized by 2 constants $c_1,c_2$. We know the true solution to the value function, denoted $V^*$:

We will now apply the bellman operator to the functional in the above definition. The operator takes a current guess $V^i$ and returns the next iterate $V^{i+1}$. We define the operator as
\begin{align} T(V)(k) =& \max_{0<k’<f(k)} \ln(f(k) - k’) + \beta V(k’)

V^{i+1}(k) =& \max_{0<k’<f(k)} \ln(f(k) - k’) + \beta V^{i}(k’)
\end{align}

Now we can start the value function iteration:

### Let’s run this now!

Ok that seems to work. What about a random starting value?