cake_eating_problem.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Cake Eating I: Introduction to Optimal Saving"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Contents\n",
    "\n",
    "- [Cake Eating I: Introduction to Optimal Saving](#Cake-Eating-I:-Introduction-to-Optimal-Saving)  \n",
    "  - [Overview](#Overview)  \n",
    "  - [The Model](#The-Model)  \n",
    "  - [The Value Function](#The-Value-Function)  \n",
    "  - [The Optimal Policy](#The-Optimal-Policy)  \n",
    "  - [The Euler Equation](#The-Euler-Equation)  \n",
    "  - [Exercises](#Exercises)  \n",
    "  - [Solutions](#Solutions)  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Overview\n",
    "\n",
    "In this lecture we introduce a simple “cake eating” problem.\n",
    "\n",
    "The intertemporal problem is: how much to enjoy today and how much to leave\n",
    "for the future?\n",
    "\n",
    "Although the topic sounds trivial, this kind of trade-off between current\n",
    "and future utility is at the heart of many savings and consumption problems.\n",
    "\n",
    "Once we master the ideas in this simple environment, we will apply them to\n",
    "progressively more challenging—and useful—problems.\n",
    "\n",
    "The main tool we will use to solve the cake eating problem is dynamic programming.\n",
    "\n",
    "Readers might find it helpful to review the following lectures before reading this one:\n",
    "\n",
    "- The [shortest paths lecture](https://python-programming.quantecon.org/short_path.html)  \n",
    "- The [basic McCall model](https://python-programming.quantecon.org/mccall_model.html)  \n",
    "- The [McCall model with separation](https://python-programming.quantecon.org/mccall_model_with_separation.html)  \n",
    "- The [McCall model with separation and a continuous wage distribution](https://python-programming.quantecon.org/mccall_fitted_vfi.html)  \n",
    "\n",
    "\n",
    "In what follows, we require the following imports:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Model\n",
    "\n",
    "We consider an infinite time horizon $ t=0, 1, 2, 3.. $\n",
    "\n",
    "At $ t=0 $ the agent is given a complete cake with size $ \\bar x $.\n",
    "\n",
    "Let $ x_t $ denote the size of the cake at the beginning of each period,\n",
    "so that, in particular, $ x_0=\\bar x $.\n",
    "\n",
    "We choose how much of the cake to eat in any given period $ t $.\n",
    "\n",
    "After choosing to consume $ c_t $ of the cake in period $ t $ there is\n",
    "\n",
    "$$\n",
    "x_{t+1} = x_t - c_t\n",
    "$$\n",
    "\n",
    "left in period $ t+1 $.\n",
    "\n",
    "Consuming quantity $ c $ of the cake gives current utility $ u(c) $.\n",
    "\n",
    "We adopt the CRRA utility function\n",
    "\n",
    "\n",
    "<a id='equation-crra-utility'></a>\n",
    "$$\n",
    "u(c) = \\frac{c^{1-\\gamma}}{1-\\gamma} \\qquad (\\gamma \\gt 0, \\, \\gamma \\neq 1) \\tag{1}\n",
    "$$\n",
    "\n",
    "In Python this is"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "def u(c, γ):\n",
    "\n",
    "    return c**(1 - γ) / (1 - γ)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Future cake consumption utility is discounted according to $ \\beta\\in(0, 1) $.\n",
    "\n",
    "In particular, consumption of $ c $ units $ t $ periods hence has present value $ \\beta^t u(c) $\n",
    "\n",
    "The agent’s problem can be written as\n",
    "\n",
    "\n",
    "<a id='equation-cake-objective'></a>\n",
    "$$\n",
    "\\max_{\\{c_t\\}} \\sum_{t=0}^\\infty \\beta^t u(c_t) \\tag{2}\n",
    "$$\n",
    "\n",
    "subject to\n",
    "\n",
    "\n",
    "<a id='equation-cake-feasible'></a>\n",
    "$$\n",
    "x_{t+1} = x_t - c_t\n",
    "\\quad \\text{and} \\quad\n",
    "0\\leq c_t\\leq x_t \\tag{3}\n",
    "$$\n",
    "\n",
    "for all $ t $.\n",
    "\n",
    "A consumption path $ \\{c_t\\} $ satisfying [(3)](#equation-cake-feasible) where\n",
    "$ x_0 = \\bar x $ is called **feasible**.\n",
    "\n",
    "In this problem, the following terminology is standard:\n",
    "\n",
    "- $ x_t $ is called the **state variable**  \n",
    "- $ c_t $ is called the **control variable** or the **action**  \n",
    "- $ \\beta $ and $ \\gamma $ are **parameters**  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Trade-Off\n",
    "\n",
    "The key trade-off in the cake-eating problem is this:\n",
    "\n",
    "- Delaying consumption is costly because of the discount factor.  \n",
    "- But delaying some consumption is also attractive because $ u $ is concave.  \n",
    "\n",
    "\n",
    "The concavity of $ u $ implies that the consumer gains value from\n",
    "*consumption smoothing*, which means spreading consumption out over time.\n",
    "\n",
    "This is because concavity implies diminishing marginal utility—a progressively smaller gain in utility for each additional spoonful of cake consumed within one period."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Intuition\n",
    "\n",
    "The reasoning given above suggests that the discount factor $ \\beta $ and the curvature parameter $ \\gamma $ will play a key role in determining the rate of consumption.\n",
    "\n",
    "Here’s an educated guess as to what impact these parameters will have.\n",
    "\n",
    "First, higher $ \\beta $ implies less discounting, and hence the agent is more patient, which should reduce the rate of consumption.\n",
    "\n",
    "Second, higher $ \\gamma $ implies that marginal utility $ u'(c) =\n",
    "c^{-\\gamma} $ falls faster with $ c $.\n",
    "\n",
    "This suggests more smoothing, and hence a lower rate of consumption.\n",
    "\n",
    "In summary, we expect the rate of consumption to be *decreasing in both\n",
    "parameters*.\n",
    "\n",
    "Let’s see if this is true."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Value Function\n",
    "\n",
    "The first step of our dynamic programming treatment is to obtain the Bellman\n",
    "equation.\n",
    "\n",
    "The next step is to use it to calculate the solution."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The Bellman Equation\n",
    "\n",
    "To this end, we let $ v(x) $ be maximum lifetime utility attainable from\n",
    "the current time when $ x $ units of cake are left.\n",
    "\n",
    "That is,\n",
    "\n",
    "\n",
    "<a id='equation-value-fun'></a>\n",
    "$$\n",
    "v(x) = \\max \\sum_{t=0}^{\\infty} \\beta^t u(c_t) \\tag{4}\n",
    "$$\n",
    "\n",
    "where the maximization is over all paths $ \\{ c_t \\} $ that are feasible\n",
    "from $ x_0 = x $.\n",
    "\n",
    "At this point, we do not have an expression for $ v $, but we can still\n",
    "make inferences about it.\n",
    "\n",
    "For example, as was the case with the [McCall model](https://python-programming.quantecon.org/mccall_model.html), the\n",
    "value function will satisfy a version of the *Bellman equation*.\n",
    "\n",
    "In the present case, this equation states that $ v $ satisfies\n",
    "\n",
    "\n",
    "<a id='equation-bellman-cep'></a>\n",
    "$$\n",
    "v(x) = \\max_{0\\leq c \\leq x} \\{u(c) + \\beta v(x-c)\\}\n",
    "\\quad \\text{for any given } x \\geq 0. \\tag{5}\n",
    "$$\n",
    "\n",
    "The intuition here is essentially the same it was for the McCall model.\n",
    "\n",
    "Choosing $ c $ optimally means trading off current vs future rewards.\n",
    "\n",
    "Current rewards from choice $ c $ are just $ u(c) $.\n",
    "\n",
    "Future rewards given current cake size $ x $, measured from next period and\n",
    "assuming optimal behavior, are $ v(x-c) $.\n",
    "\n",
    "These are the two terms on the right hand side of [(5)](#equation-bellman-cep), after\n",
    "suitable discounting.\n",
    "\n",
    "If $ c $ is chosen optimally using this trade off strategy, then we obtain maximal lifetime rewards from our current state $ x $.\n",
    "\n",
    "Hence, $ v(x) $ equals the right hand side of [(5)](#equation-bellman-cep), as claimed."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### An Analytical Solution\n",
    "\n",
    "It has been shown that, with $ u $ as the CRRA utility function in\n",
    "[(1)](#equation-crra-utility), the function\n",
    "\n",
    "\n",
    "<a id='equation-crra-vstar'></a>\n",
    "$$\n",
    "v^*(x_t) = \\left( 1-\\beta^{1/\\gamma} \\right)^{-\\gamma}u(x_t) \\tag{6}\n",
    "$$\n",
    "\n",
    "solves the Bellman equation and hence is equal to the value function.\n",
    "\n",
    "You are asked to confirm that this is true in the exercises below.\n",
    "\n",
    "The solution [(6)](#equation-crra-vstar) depends heavily on the CRRA utility function.\n",
    "\n",
    "In fact, if we move away from CRRA utility, usually there is no analytical\n",
    "solution at all.\n",
    "\n",
    "In other words, beyond CRRA utility, we know that the value function still\n",
    "satisfies the Bellman equation, but we do not have a way of writing it\n",
    "explicitly, as a function of the state variable and the parameters.\n",
    "\n",
    "We will deal with that situation numerically when the time comes.\n",
    "\n",
    "Here is a Python representation of the value function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "def v_star(x, β, γ):\n",
    "\n",
    "    return (1 - β**(1 / γ))**(-γ) * u(x, γ)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And here’s a figure showing the function for fixed parameters:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "β, γ = 0.95, 1.2\n",
    "x_grid = np.linspace(0.1, 5, 100)\n",
    "\n",
    "fig, ax = plt.subplots()\n",
    "\n",
    "ax.plot(x_grid, v_star(x_grid, β, γ), label='value function')\n",
    "\n",
    "ax.set_xlabel('$x$', fontsize=12)\n",
    "ax.legend(fontsize=12)\n",
    "\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Optimal Policy\n",
    "\n",
    "Now that we have the value function, it is straightforward to calculate the\n",
    "optimal action at each state.\n",
    "\n",
    "We should choose consumption to maximize the\n",
    "right hand side of the Bellman equation [(5)](#equation-bellman-cep).\n",
    "\n",
    "$$\n",
    "c^* = \\arg \\max_{c} \\{u(c) + \\beta v(x - c)\\}\n",
    "$$\n",
    "\n",
    "We can think of this optimal choice as a function of the state $ x $, in\n",
    "which case we call it the **optimal policy**.\n",
    "\n",
    "We denote the optimal policy by $ \\sigma^* $, so that\n",
    "\n",
    "$$\n",
    "\\sigma^*(x) := \\arg \\max_{c} \\{u(c) + \\beta v(x - c)\\}\n",
    "\\quad \\text{for all } x\n",
    "$$\n",
    "\n",
    "If we plug the analytical expression [(6)](#equation-crra-vstar) for the value function\n",
    "into the right hand side and compute the optimum, we find that\n",
    "\n",
    "\n",
    "<a id='equation-crra-opt-pol'></a>\n",
    "$$\n",
    "\\sigma^*(x) = \\left( 1-\\beta^{1/\\gamma} \\right) x \\tag{7}\n",
    "$$\n",
    "\n",
    "Now let’s recall our intuition on the impact of parameters.\n",
    "\n",
    "We guessed that the consumption rate would be decreasing in both parameters.\n",
    "\n",
    "This is in fact the case, as can be seen from [(7)](#equation-crra-opt-pol).\n",
    "\n",
    "Here’s some plots that illustrate."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "def c_star(x, β, γ):\n",
    "\n",
    "    return (1 - β ** (1/γ)) * x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Continuing with the values for $ \\beta $ and $ \\gamma $ used above, the\n",
    "plot is"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "fig, ax = plt.subplots()\n",
    "ax.plot(x_grid, c_star(x_grid, β, γ), label='default parameters')\n",
    "ax.plot(x_grid, c_star(x_grid, β + 0.02, γ), label=r'higher $\\beta$')\n",
    "ax.plot(x_grid, c_star(x_grid, β, γ + 0.2), label=r'higher $\\gamma$')\n",
    "ax.set_ylabel(r'$\\sigma(x)$')\n",
    "ax.set_xlabel('$x$')\n",
    "ax.legend()\n",
    "\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Euler Equation\n",
    "\n",
    "In the discussion above we have provided a complete solution to the cake\n",
    "eating problem in the case of CRRA utility.\n",
    "\n",
    "There is in fact another way to solve for the optimal policy, based on the\n",
    "so-called **Euler equation**.\n",
    "\n",
    "Although we already have a complete solution, now is a good time to study the\n",
    "Euler equation.\n",
    "\n",
    "This is because, for more difficult problems, this equation\n",
    "provides key insights that are hard to obtain by other methods."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Statement and Implications\n",
    "\n",
    "The Euler equation for the present problem can be stated as\n",
    "\n",
    "\n",
    "<a id='equation-euler-cep'></a>\n",
    "$$\n",
    "u^{\\prime} (c^*_{t})=\\beta u^{\\prime}(c^*_{t+1}) \\tag{8}\n",
    "$$\n",
    "\n",
    "This is necessary condition for the optimal path.\n",
    "\n",
    "It says that, along the optimal path, marginal rewards are equalized across time, after appropriate discounting.\n",
    "\n",
    "This makes sense: optimality is obtained by smoothing consumption up to the\n",
    "point where no marginal gains remain.\n",
    "\n",
    "We can also state the Euler equation in terms of the policy function.\n",
    "\n",
    "A **feasible consumption policy** is a map $ x \\mapsto \\sigma(x) $\n",
    "satisfying $ 0 \\leq \\sigma(x) \\leq x $.\n",
    "\n",
    "The last restriction says that we cannot consume more than the remaining\n",
    "quantity of cake.\n",
    "\n",
    "A feasible consumption policy $ \\sigma $ is said to **satisfy the Euler equation** if, for\n",
    "all $ x > 0 $,\n",
    "\n",
    "\n",
    "<a id='equation-euler-pol'></a>\n",
    "$$\n",
    "u^{\\prime}( \\sigma(x) )\n",
    "= \\beta u^{\\prime} (\\sigma(x - \\sigma(x))) \\tag{9}\n",
    "$$\n",
    "\n",
    "Evidently [(9)](#equation-euler-pol) is just the policy equivalent of [(8)](#equation-euler-cep).\n",
    "\n",
    "It turns out that a feasible policy is optimal if and\n",
    "only if it satisfies the Euler equation.\n",
    "\n",
    "In the exercises, you are asked to verify that the optimal policy\n",
    "[(7)](#equation-crra-opt-pol) does indeed satisfy this functional equation.\n",
    "\n",
    ">**Note**\n",
    ">\n",
    ">A **functional equation** is an equation where the unknown object is a function.\n",
    "\n",
    "For a proof of sufficiency of the Euler equation in a very general setting,\n",
    "see proposition 2.2 of [[MST20]](https://python-programming.quantecon.org/zreferences.html#ma2020income).\n",
    "\n",
    "The following arguments focus on necessity, explaining why an optimal path or\n",
    "policy should satisfy the Euler equation."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Derivation I: A Perturbation Approach\n",
    "\n",
    "Let’s write $ c $ as a shorthand for consumption path $ \\{c_t\\}_{t=0}^\\infty $.\n",
    "\n",
    "The overall cake-eating maximization problem can be written as\n",
    "\n",
    "$$\n",
    "\\max_{c \\in F} U(c)\n",
    "\\quad \\text{where } U(c) := \\sum_{t=0}^\\infty \\beta^t u(c_t)\n",
    "$$\n",
    "\n",
    "and $ F $ is the set of feasible consumption paths.\n",
    "\n",
    "We know that differentiable functions have a zero gradient at a maximizer.\n",
    "\n",
    "So the optimal path $ c^* := \\{c^*_t\\}_{t=0}^\\infty $ must satisfy\n",
    "$ U'(c^*) = 0 $.\n",
    "\n",
    ">**Note**\n",
    ">\n",
    ">If you want to know exactly how the derivative $ U'(c^*) $ is\n",
    "defined, given that the argument $ c^* $ is a vector of infinite\n",
    "length, you can start by learning about [Gateaux derivatives](https://en.wikipedia.org/wiki/Gateaux_derivative). However, such\n",
    "knowledge is not assumed in what follows.\n",
    "\n",
    "In other words, the rate of change in $ U $ must be zero for any\n",
    "infinitesimally small (and feasible) perturbation away from the optimal path.\n",
    "\n",
    "So consider a feasible perturbation that reduces consumption at time $ t $ to\n",
    "$ c^*_t - h $\n",
    "and increases it in the next period to $ c^*_{t+1} + h $.\n",
    "\n",
    "Consumption does not change in any other period.\n",
    "\n",
    "We call this perturbed path $ c^h $.\n",
    "\n",
    "By the preceding argument about zero gradients, we have\n",
    "\n",
    "$$\n",
    "\\lim_{h \\to 0} \\frac{U(c^h) - U(c^*)}{h} = U'(c^*) = 0\n",
    "$$\n",
    "\n",
    "Recalling that consumption only changes at $ t $ and $ t+1 $, this\n",
    "becomes\n",
    "\n",
    "$$\n",
    "\\lim_{h \\to 0}\n",
    "\\frac{\\beta^t u(c^*_t - h) + \\beta^{t+1} u(c^*_{t+1} + h)\n",
    "      - \\beta^t u(c^*_t) - \\beta^{t+1} u(c^*_{t+1}) }{h} = 0\n",
    "$$\n",
    "\n",
    "After rearranging, the same expression can be written as\n",
    "\n",
    "$$\n",
    "\\lim_{h \\to 0}\n",
    "    \\frac{u(c^*_t - h) - u(c^*_t) }{h}\n",
    "+ \\lim_{h \\to 0}\n",
    "    \\frac{ \\beta u(c^*_{t+1} + h) - u(c^*_{t+1}) }{h} = 0\n",
    "$$\n",
    "\n",
    "or, taking the limit,\n",
    "\n",
    "$$\n",
    "- u'(c^*_t) + \\beta u'(c^*_{t+1}) = 0\n",
    "$$\n",
    "\n",
    "This is just the Euler equation."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Derivation II: Using the Bellman Equation\n",
    "\n",
    "Another way to derive the Euler equation is to use the Bellman equation [(5)](#equation-bellman-cep).\n",
    "\n",
    "Taking the derivative on the right hand side of the Bellman equation with\n",
    "respect to $ c $ and setting it to zero, we get\n",
    "\n",
    "\n",
    "<a id='equation-bellman-foc'></a>\n",
    "$$\n",
    "u^{\\prime}(c)=\\beta v^{\\prime}(x - c) \\tag{10}\n",
    "$$\n",
    "\n",
    "To obtain $ v^{\\prime}(x - c) $, we set\n",
    "$ g(c,x) = u(c) + \\beta v(x - c) $, so that, at the optimal choice of\n",
    "consumption,\n",
    "\n",
    "\n",
    "<a id='equation-bellman-equality'></a>\n",
    "$$\n",
    "v(x) = g(c,x) \\tag{11}\n",
    "$$\n",
    "\n",
    "Differentiating both sides while acknowledging that the maximizing consumption will depend\n",
    "on $ x $, we get\n",
    "\n",
    "$$\n",
    "v' (x) =\n",
    "\\frac{\\partial }{\\partial c} g(c,x) \\frac{\\partial c}{\\partial x}\n",
    " + \\frac{\\partial }{\\partial x} g(c,x)\n",
    "$$\n",
    "\n",
    "When $ g(c,x) $ is maximized at $ c $, we have $ \\frac{\\partial }{\\partial c} g(c,x) = 0 $.\n",
    "\n",
    "Hence the derivative simplifies to\n",
    "\n",
    "\n",
    "<a id='equation-bellman-envelope'></a>\n",
    "$$\n",
    "v' (x) =\n",
    "\\frac{\\partial g(c,x)}{\\partial x}\n",
    "= \\frac{\\partial }{\\partial x} \\beta v(x - c)\n",
    "= \\beta v^{\\prime}(x - c) \\tag{12}\n",
    "$$\n",
    "\n",
    "(This argument is an example of the [Envelope Theorem](https://en.wikipedia.org/wiki/Envelope_theorem).)\n",
    "\n",
    "But now an application of [(10)](#equation-bellman-foc) gives\n",
    "\n",
    "\n",
    "<a id='equation-bellman-v-prime'></a>\n",
    "$$\n",
    "u^{\\prime}(c) = v^{\\prime}(x) \\tag{13}\n",
    "$$\n",
    "\n",
    "Thus, the derivative of the value function is equal to marginal utility.\n",
    "\n",
    "Combining this fact with [(12)](#equation-bellman-envelope) recovers the Euler equation."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercises"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 1\n",
    "\n",
    "How does one obtain the expressions for the value function and optimal policy\n",
    "given in [(6)](#equation-crra-vstar) and [(7)](#equation-crra-opt-pol) respectively?\n",
    "\n",
    "The first step is to make a guess of the functional form for the consumption\n",
    "policy.\n",
    "\n",
    "So suppose that we do not know the solutions and start with a guess that the\n",
    "optimal policy is linear.\n",
    "\n",
    "In other words, we conjecture that there exists a positive $ \\theta $ such that setting $ c_t^*=\\theta x_t $ for all $ t $ produces an optimal path.\n",
    "\n",
    "Starting from this conjecture, try to obtain the solutions [(6)](#equation-crra-vstar) and [(7)](#equation-crra-opt-pol).\n",
    "\n",
    "In doing so, you will need to use the definition of the value function and the\n",
    "Bellman equation."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Solutions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 1\n",
    "\n",
    "We start with the conjecture $ c_t^*=\\theta x_t $, which leads to a path\n",
    "for the state variable (cake size) given by\n",
    "\n",
    "$$\n",
    "x_{t+1}=x_t(1-\\theta)\n",
    "$$\n",
    "\n",
    "Then $ x_t = x_{0}(1-\\theta)^t $ and hence\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "v(x_0)\n",
    "   & = \\sum_{t=0}^{\\infty} \\beta^t u(\\theta x_t)\\\\\n",
    "   & = \\sum_{t=0}^{\\infty} \\beta^t u(\\theta x_0 (1-\\theta)^t ) \\\\\n",
    "   & = \\sum_{t=0}^{\\infty} \\theta^{1-\\gamma} \\beta^t (1-\\theta)^{t(1-\\gamma)} u(x_0) \\\\\n",
    "   & = \\frac{\\theta^{1-\\gamma}}{1-\\beta(1-\\theta)^{1-\\gamma}}u(x_{0})\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "From the Bellman equation, then,\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "    v(x) & = \\max_{0\\leq c\\leq x}\n",
    "        \\left\\{\n",
    "            u(c) +\n",
    "            \\beta\\frac{\\theta^{1-\\gamma}}{1-\\beta(1-\\theta)^{1-\\gamma}}\\cdot u(x-c)\n",
    "        \\right\\} \\\\\n",
    "         & = \\max_{0\\leq c\\leq x}\n",
    "            \\left\\{\n",
    "                \\frac{c^{1-\\gamma}}{1-\\gamma} +\n",
    "                \\beta\\frac{\\theta^{1-\\gamma}}\n",
    "                {1-\\beta(1-\\theta)^{1-\\gamma}}\n",
    "                \\cdot\\frac{(x-c)^{1-\\gamma}}{1-\\gamma}\n",
    "            \\right\\}\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "From the first order condition, we obtain\n",
    "\n",
    "$$\n",
    "c^{-\\gamma} + \\beta\\frac{\\theta^{1-\\gamma}}{1-\\beta(1-\\theta)^{1-\\gamma}}\\cdot(x-c)^{-\\gamma}(-1) = 0\n",
    "$$\n",
    "\n",
    "or\n",
    "\n",
    "$$\n",
    "c^{-\\gamma} = \\beta\\frac{\\theta^{1-\\gamma}}{1-\\beta(1-\\theta)^{1-\\gamma}}\\cdot(x-c)^{-\\gamma}\n",
    "$$\n",
    "\n",
    "With $ c = \\theta x $ we get\n",
    "\n",
    "$$\n",
    "\\left(\\theta x\\right)^{-\\gamma} =  \\beta\\frac{\\theta^{1-\\gamma}}{1-\\beta(1-\\theta)^{1-\\gamma}}\\cdot(x(1-\\theta))^{-\n",
    "\\gamma}\n",
    "$$\n",
    "\n",
    "Some rearrangement produces\n",
    "\n",
    "$$\n",
    "\\theta = 1-\\beta^{\\frac{1}{\\gamma}}\n",
    "$$\n",
    "\n",
    "This confirms our earlier expression for the optimal policy:\n",
    "\n",
    "$$\n",
    "c_t^* = \\left(1-\\beta^{\\frac{1}{\\gamma}}\\right)x_t\n",
    "$$\n",
    "\n",
    "Substituting $ \\theta $ into the value function above gives\n",
    "\n",
    "$$\n",
    "v^*(x_t) = \\frac{\\left(1-\\beta^{\\frac{1}{\\gamma}}\\right)^{1-\\gamma}}\n",
    "{1-\\beta\\left(\\beta^{\\frac{{1-\\gamma}}{\\gamma}}\\right)} u(x_t) \\\\\n",
    "$$\n",
    "\n",
    "Rearranging gives\n",
    "\n",
    "$$\n",
    "v^*(x_t) = \\left(1-\\beta^\\frac{1}{\\gamma}\\right)^{-\\gamma}u(x_t)\n",
    "$$\n",
    "\n",
    "Our claims are now verified."
   ]
  }
 ],
 "metadata": {
  "date": 1591697892.5263233,
  "filename": "cake_eating_problem.rst",
  "kernelspec": {
   "display_name": "Python",
   "language": "python3",
   "name": "python3"
  },
  "title": "Cake Eating I: Introduction to Optimal Saving"
 },
 "nbformat": 4,
 "nbformat_minor": 2
}