Python setup and fundamentals ¶
Alfred Galichon (NYU) ¶
'math+econ+code' masterclass series: fundamentals of research in python ¶
With python code examples ¶
© 2018–2026 by Alfred Galichon. Past and present support from NSF grant DMS-1716489, ERC grant CoG-866274 are acknowledged, as well as inputs from contributors listed here.
If you reuse material from this masterclass, please cite as:
Alfred Galichon, 'math+econ+code' masterclass series. https://www.math-econ-code.org/
Learning objectives¶
Get a working Python environment running in one of three ways, cloud (Google Colab), local (Miniforge), or an editor (VS Code), and know which to pick.
Read and write basic Python: numbers, types, variables, booleans, and control flow.
Recognize the cell-and-kernel model of Jupyter, and the failure modes that come with out-of-order execution.
Adopt the two conventions this series uses throughout: axis-annotated names, so that the identity of an array is recoverable from its name; and verification by a second, independent route, with the tolerance stated in the output.
Price a stream of cash flows three ways, by a loop, by a closed form, and as an inner product against a vector of discount factors, and recognize the discount factor as the first dual variable of the series.
Solve $x^2 = 2$ by Newton's method, and verify its quadratic rate of convergence numerically rather than taking it on faith.
References¶
[V] VanderPlas, J. (2023). Python Data Science Handbook (2nd ed.). O'Reilly, Chapter 1. Online at https://jakevdp.github.io/PythonDataScienceHandbook/.
[QE] Sargent, T. J. and Stachurski, J. QuantEcon Python Lectures, "Python by Example." https://python-programming.quantecon.org/.
[M] McKinney, W. (2022). Python for Data Analysis (3rd ed.). O'Reilly. Online at https://wesmckinney.com/book/.
[L] Luenberger, D. G. (1997). Investment Science. Oxford University Press, Chapters 2–3 (present value, internal rate of return, duration).
[G] Galichon, A. (2016). Optimal Transport Methods in Economics. Princeton University Press: for the primal–dual language adopted throughout the 'math+econ+code' series.
[Conda] conda / Miniforge documentation. https://github.com/conda-forge/miniforge and https://docs.conda.io/.
[Colab] Google Colaboratory. https://colab.research.google.com/.
[VSC] Visual Studio Code: Jupyter notebooks. https://code.visualstudio.com/docs/datascience/jupyter-notebooks.
1. Motivation and scope¶
This series, fundamentals of research in python, is the toolbox lecture course for the rest of the 'math+econ+code' masterclasses. The subject-matter series, dynamic programming (dp), optimal transport (ot), linear programming (lp), discrete choice (dc), equilibrium and matching (et), all assume that you can set up an environment, vectorize a computation, assemble a sparse operator, call a solver, read its dual variables, and check the answer. Those are the skills built here, in that order, over eleven lectures.
Why Python, and not something else?
Ecosystem. Quantitative economics today is computational, and Python sits at the center of the open-source scientific stack: NumPy and SciPy for numerical work, pandas for data, statsmodels and scikit-learn for estimation and machine learning, TensorFlow / PyTorch / JAX for differentiable programming. Each of these libraries assumes the others; together they cover the workflow from raw data to publishable result.
Reproducibility. A modern empirical paper is a computational artifact: code, data, and prose that another researcher can clone, re-run, and check. Python pairs naturally with Git, GitHub, and Colab: a stack we set up properly in fd05.
Community. The QuantEcon project (Sargent and Stachurski), the textbooks of McKinney and VanderPlas, and the broader scientific Python community provide a continuously updated body of high-quality, freely available material. You will use these resources for the rest of your career.
The alternatives, R, MATLAB, Julia, Stata, each have strengths, and you should expect to encounter them. But Python is the lingua franca, and it is what we use throughout.
This first lecture has two purposes. Sections 2–4 get a working environment in front of you. Sections 5–13 are the language itself, ending with two worked examples, pricing a bond and Newton's method, that already contain, in miniature, the two habits this series is built on: every number gets checked by a second route, and prices are dual variables.
2. Three ways to run these notebooks¶
No economics and no algorithms in this section: just enough setup that Section 5 starts cleanly. Pick one of three paths. All three run every notebook in the series.
| Path | Best for | Setup cost | Notes |
|---|---|---|---|
| A. Google Colab | getting going briefly, Chromebooks, no admin rights | none | notebooks run on Google's servers; needs a Google account and a network |
| B. Local (Miniforge) | doing real work, running offline, reproducibility | ~10 min once | the environment you will actually use for research |
| C. VS Code + Jupyter | people who like an editor and integrated Git | ~15 min once | uses a local Python (Path B) underneath |
If you are unsure, start with Colab (Path A) to follow today's lecture, and set up a local environment (Path B) before fd04, which is the first lecture needing packages Colab does not ship, and where running offline and managing versions starts to matter.
2.1 Path A: Google Colab (fastest start)¶
- Open https://colab.research.google.com and sign in with a Google account.
- File → Upload notebook (or File → Open notebook → GitHub and paste the course repository URL) to open a course
.ipynb. - Run a cell with Shift+Enter. The first run spins up a fresh virtual machine; NumPy, pandas, and matplotlib are pre-installed.
Two things to know about Colab:
- State is temporary. The virtual machine is discarded after a period of inactivity; anything not saved to Google Drive or downloaded is lost. Use File → Save a copy in Drive.
- Installing extra packages is done per session with a shell escape, e.g.
!pip install yfinance. You will re-run it each time the machine resets. A few later notebooks (fd04,fd07,fd10) use packages that are not pre-installed; each such notebook says so at the top.
2.2 Path B: Local install with Miniforge (recommended)¶
The cleanest local setup uses Miniforge, a minimal conda installer that defaults to the community conda-forge channel. (Full Anaconda works too; Miniforge is lighter and avoids licensing questions for institutional use.)
Step 1: install Miniforge. Download the installer for your operating system from github.com/conda-forge/miniforge and run it. On Windows, use the Miniforge Prompt it installs; on macOS and Linux, restart your shell afterward.
Step 2: create a per-course environment. Never install into the base environment: keep one environment per project so versions do not collide:
conda create -n mec python=3.12 numpy scipy pandas matplotlib seaborn jupyterlab
conda activate mec
Step 3: add the packages used in the second half of the series:
conda install scikit-learn requests beautifulsoup4 numba pytest
Step 4: launch JupyterLab from inside the activated environment:
jupyter lab
We return to environments, requirements.txt and environment.yml lockfiles, and reproducibility properly in fd07. For now, the four commands above are all you need.
Why a named environment? A month from now you will have three projects with incompatible NumPy pins. One conda environment per project is the single habit that prevents "it worked yesterday" from ever happening to you.
2.3 Path C: VS Code + the Jupyter extension¶
If you prefer an editor with integrated Git and a debugger:
- Install VS Code and, from the Extensions panel, the Python and Jupyter extensions (both by Microsoft).
- Install a local Python first: do Path B through Step 3, so that you have the
mecenvironment. - Open a
.ipynbin VS Code. Click Select Kernel (top right) and choose themecenvironment. Run cells with Shift+Enter.
VS Code gives you the notebook plus real editor features, multi-file search, Git diffs, refactoring, that JupyterLab lacks. Its Git integration previews the workflow we build by hand in fd05.
2.4 Getting the notebooks¶
The notebooks of this series, and of the other 'math+econ+code' series, are distributed from www.math-econ-code.org and from the associated GitHub organization, github.com/math-econ-code. Download the .ipynb files (or the zipped folder), save them somewhere you will find again, and open them in JupyterLab, VS Code, or Colab as described above.
Notebooks are revised between sessions, so check for updated versions as the course proceeds. From fd05 onward, where we teach Git and GitHub from first principles, you will be able to git clone the repository once and git pull updates thereafter, which is both faster and more reliable than re-downloading.
3. A brief overview of cells and kernels¶
A notebook is a sequence of cells: markdown cells (text and mathematics) and code cells, which are executed by a kernel: a Python process that holds state between cells. Three rules avoid common errors:
- Execution order is what matters, not top-to-bottom position. The number in
[ ]to the left of a code cell records the order in which it actually ran. - Variables persist across cells, and a stale value left over from an earlier run can silently poison a later cell.
- Restart & Run All before you trust a notebook. If it does not run cleanly top-to-bottom in a fresh kernel, it is not reproducible, and reproducibility is the whole point.
Run the cell below; then, for practice, use Kernel → Restart Kernel and Run All Cells in JupyterLab (or the equivalent in your tool) and watch the execution counters reset.
print("Hello, class.")
Hello, class.
If the string is echoed below the cell, your kernel is alive and the rest of the notebook will work.
4. Verifying your environment¶
Two diagnostics. The first confirms your Python version; the second reports which scientific packages are installed and which lecture first needs each of them.
You do not need every package to start, fd01 through fd03 use only the Python standard library, but this tells you what to install before the library-heavy lectures. Note that the output stored in this notebook reflects the machine on which it was executed; yours will differ, and that is expected.
The second cell reads each package's installation metadata with importlib.metadata.version rather than importing the package and reading its __version__. The difference matters more than it looks: importing TensorFlow merely to learn its version number takes several seconds and initializes a good deal of machinery, whereas reading the metadata is instantaneous and has no side effects. Asking the cheapest question that answers your question is a habit worth forming early.
It also exposes a distinction that causes real confusion: the name you import and the name of the distribution that installs it are not always the same. You import bs4, but you install beautifulsoup4; and TensorFlow ships under tensorflow, tensorflow-cpu, or tensorflow-intel depending on the platform, which is why the cell tries several names before declaring it missing. When an install "succeeds" and the import still fails, or the reverse, as here, this mismatch is the usual culprit.
import sys
print("Python", sys.version.split()[0])
assert sys.version_info >= (3, 10), "This series assumes Python 3.10+ — please upgrade."
print("Kernel is alive.")
Python 3.12.3 Kernel is alive.
from importlib.metadata import version, PackageNotFoundError
# (what we call it, distribution names to try, first lecture of this series that needs it)
needed = [
("numpy", ("numpy",), "fd04"),
("scipy", ("scipy",), "fd09"),
("tensorflow", ("tensorflow", "tensorflow-cpu", "tensorflow-intel"), "fd10"),
("sklearn", ("scikit-learn",), "fd11"),
("pandas", ("pandas",), "fd06"),
("matplotlib", ("matplotlib",), "fd06"),
("seaborn", ("seaborn",), "fd06"),
("requests", ("requests",), "fd07"),
("bs4", ("beautifulsoup4",), "fd07"),
("numba", ("numba",), "fd04"),
("pytest", ("pytest",), "fd04"),
]
def installed_version(candidates):
# return the version of the first distribution that is installed, else None
for name in candidates:
try:
return version(name)
except PackageNotFoundError:
continue
return None
missing = []
print(f"{'package':14s}{'version':14s}first needed by")
print("-" * 46)
for name, candidates, first in needed:
found = installed_version(candidates)
if found is None:
missing.append(candidates[0])
print(f"{name:14s}{'MISSING':14s}{first} <- install before this lecture")
else:
print(f"{name:14s}{found:14s}{first}")
print("-" * 46)
print(f"{len(needed) - len(missing)} of {len(needed)} present." +
(f" To install: conda install {' '.join(missing)}" if missing else ""))
package version first needed by ---------------------------------------------- numpy 1.26.4 fd04 scipy 1.16.0 fd09 tensorflow 2.19.0 fd10 sklearn 1.5.1 fd11 pandas 2.2.3 fd06 matplotlib 3.9.2 fd06 seaborn 0.13.2 fd06 requests 2.32.5 fd07 bs4 4.12.3 fd07 numba 0.60.0 fd04 pytest 8.4.2 fd04 ---------------------------------------------- 11 of 11 present.
If a package shows MISSING, install it into your active environment: conda install <name> locally, or !pip install <name> in a Colab cell, and re-run the cell. A MISSING next to a lecture you have not reached yet does not require action today.
Troubleshooting the first session.
| Symptom | Likely cause | Fix |
|---|---|---|
ModuleNotFoundError: No module named 'numpy' |
wrong or empty environment selected | activate mec (Path B), or pick the mec kernel in VS Code; on Colab, !pip install numpy |
| Notebook "runs" but the values look wrong | out-of-order execution | Restart & Run All |
jupyter: command not found |
environment not activated | conda activate mec, then jupyter lab |
| Kernel keeps dying on a large cell | out of memory (often on Colab) | restart the kernel; reduce sample sizes; use a local machine for heavy notebooks |
| A cell needs a package you do not have | later lectures add dependencies | install per §2.2 and §4; each notebook lists what it needs at the top |
If a notebook still will not run after Restart & Run All in a correctly activated environment, that is a bug worth reporting: note the notebook, the cell, and the full error text.
5. Numbers and expressions¶
Python evaluates arithmetic expressions the way you would expect, with one famous exception that we come to in a moment.
2 + 3, 7 - 4, 6 * 9, 2 ** 10
(5, 3, 54, 1024)
Two division operators, and the difference matters:
7 / 2, 7 // 2, 7 % 2
(3.5, 3, 1)
/ is true division and always returns a float. // is floor division, which drops the remainder. % is the remainder. This trips up almost everyone coming from C, Java, or Python 2.
Python integers have arbitrary precision: they grow as large as you need, with no overflow. This is a property of Python's built-in int; once we move to NumPy in fd08, integers have a fixed bit width and overflow becomes a real concern.
2 ** 100
1267650600228229401496703205376
Floating-point numbers, on the other hand, behave the way they always do, which is to say, not the way you would naively want:
0.1 + 0.2
0.30000000000000004
$0.1 + 0.2 \neq 0.3$ in IEEE 754 binary floating point. This is not a Python bug; it is a fact about how decimal fractions are encoded in binary. The practical consequence is a rule we will follow for the rest of the series: never compare floats with ==. Compare against a tolerance, and state the tolerance in the output.
import math
math.isclose(0.1 + 0.2, 0.3)
True
math.isclose(a, b) defaults to a relative tolerance of $10^{-9}$. From fd08 onward its vectorized counterparts numpy.isclose and numpy.allclose do the same job on arrays.
6. Types and variables¶
Python is dynamically typed: a variable is a name bound to a value, not a declaration of storage. The same name can be re-bound to a value of a different type.
x = 42
print(type(x))
x = "forty-two"
print(type(x))
<class 'int'> <class 'str'>
The five types you will meet in 95% of code:
| Type | Examples | Notes |
|---|---|---|
int |
42, -1, 0, 2**100 |
arbitrary precision |
float |
3.14, 1e-9, math.inf |
IEEE 754 double |
str |
"hello", 'mec', f"x={x}" |
immutable, Unicode |
bool |
True, False |
technically a subclass of int |
NoneType |
None |
the unique sentinel |
Conversion is explicit:
int("3"), float("3.14"), str(42), bool(0), bool(1), bool("")
(3, 3.14, '42', False, True, False)
Naming, and a house convention. Names use snake_case by convention: all lowercase, words joined by underscores: interest_rate, present_value. Constants are written ALL_CAPS, e.g. MAX_ITER. These rules come from PEP 8, Python's official style guide ("PEP" stands for Python Enhancement Proposal). PEP 8 is not enforced by the language, code in any style still runs, but following it makes your code instantly readable to other Python users. We adopt its naming and four-space indentation from the start, and return to automated style checking in fd04.
On top of PEP 8, the 'math+econ+code' series adds one convention of its own, and it is worth learning now, in the lecture where the arrays are one-dimensional and harmless:
Array names record their axes, in order. A quantity indexed by dates $t$ is called
c_t; a matrix indexed by $(x, y)$ is calledmu_x_y; a three-index array with axes $(x, y, x')$ is calledP_x_y_xp. The number of values an index can take isnbt,nbx,nby. A concatenated suffix denotes the row-major flattening of the corresponding array, somu_xy = mu_x_y.reshape(-1).
The point is that the identity of an object should be recoverable from its name. By the time you are assembling a sparse constraint matrix in fd08, or the transition operator of a Markov decision process in the dp series, the difference between P_x_y_xp and P_xp_x_y is the difference between a correct answer and a plausible wrong one, and the name is what tells you which you have. We start using it in §10 below.
interest_rate = 0.05
horizon = 30
final_value = 1000 * (1 + interest_rate) ** horizon
print(f"After {horizon} years at {interest_rate:.0%}, $1000 grows to ${final_value:,.2f}.")
After 30 years at 5%, $1000 grows to $4,321.94.
The string above uses an f-string, the recommended way to interpolate values into text in modern Python. The format specification after the colon controls the display: :.0% formats as a percentage with no decimals, and :,.2f adds thousands separators and two decimals.
7. Booleans, comparisons, and truthiness¶
Comparison operators return a bool:
1 < 2, 2 == 2.0, 2 == "2", "abc" < "abd"
(True, True, False, True)
The third is False because int and str are different types. The fourth is True because strings compare lexicographically.
Logical operators are spelled and, or, not. They short-circuit: False and f() never calls f, which is occasionally useful and occasionally a source of bugs.
(2 < 3) and (3 < 4), (1 == 2) or (3 < 4), not (1 == 1)
(True, True, False)
Truthiness. Python objects can be used directly in a boolean context. The "falsy" values are False, 0, 0.0, "", None, and the empty containers [], (), {}. Everything else is truthy.
bool(0), bool(0.0), bool(""), bool([]), bool("False"), bool([0])
(False, False, False, False, True, True)
The last two are the trap: bool("False") is True, because a non-empty string is truthy regardless of its content; and bool([0]) is True, because a list with one element is non-empty even when that element is itself falsy.
8. Control flow: if / elif / else¶
Indentation defines blocks. There are no braces, and the indentation is part of the syntax, not a style preference. Use four spaces (PEP 8).
def tax(income):
# Toy progressive tax with three brackets.
if income <= 10_000:
return 0.0
elif income <= 50_000:
return 0.15 * (income - 10_000)
else:
return 0.15 * 40_000 + 0.30 * (income - 50_000)
for y in [5_000, 25_000, 80_000]:
print(f"income = ${y:>6,} -> tax = ${tax(y):>8,.2f}")
income = $ 5,000 -> tax = $ 0.00 income = $25,000 -> tax = $2,250.00 income = $80,000 -> tax = $15,000.00
Two remarks. First, underscores are legal digit separators: 10_000 is just 10000, and they make magnitudes readable at a glance. Second, we treat functions properly in fd03; for now, def name(args): ... is enough to read along.
Economically, this is a piecewise-linear, convex increasing tax schedule, and its marginal rate, 0, then 15%, then 30%, is the step function you get by differentiating it. Convex piecewise-linear functions and their subgradients are exactly the objects that the linear-programming series (lp01) treats systematically.
9. Control flow: while and for¶
A while loop repeats as long as a condition holds. A for loop iterates over a sequence.
# A while loop: the smallest n such that 2**n > 1_000_000
n = 0
while 2 ** n <= 1_000_000:
n += 1
print(n, 2 ** n)
20 1048576
# A for loop over range(start, stop, step)
total = 0
for k in range(1, 11):
total += k
print(total)
55
range(a, b) produces $a, a+1, \dots, b-1$: the upper end is exclusive, a convention you will get used to. range(a, b, s) steps by $s$, and range(n) is shorthand for range(0, n). Inside a loop, break exits early and continue skips to the next iteration.
The standard drill for if inside for is FizzBuzz: print the integers, replacing multiples of 3 by Fizz, multiples of 5 by Buzz, and multiples of both by FizzBuzz. Note that the test for "both" must come first, because elif branches are evaluated in order.
for i in range(1, 16):
if i % 15 == 0: # multiple of both 3 and 5 — must be tested first
print("FizzBuzz")
elif i % 3 == 0:
print("Fizz")
elif i % 5 == 0:
print("Buzz")
else:
print(i)
1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz
10. Worked example: present value of a cash-flow stream¶
A bond pays a cash flow $c_t$ at the end of each year $t = 1, \dots, T$. At a constant discount rate $r$, its present value is
$$ PV \;=\; \sum_{t=1}^{T} \frac{c_t}{(1+r)^{t}}. \tag{10.1} $$We compute this three times: with a loop (this section), with a closed form (this section), and as an inner product against a vector of prices (§11). Getting the same number from independent routes is the cheapest test available, and it is the habit this series is built on.
Following the naming convention of §6, the cash-flow stream is c_t, one axis, indexed by the date, and the number of dates is nbt. One honest annoyance to flag immediately: the mathematics above indexes dates $t = 1, \dots, T$, while Python indexes lists from 0. We handle it here with enumerate(c_t, start=1), which walks the list while counting from 1.
# 5-year bond: 10% coupon on $1000 of face value, principal repaid at maturity
c_t = [100, 100, 100, 100, 100 + 1000]
nbt = len(c_t)
r = 0.05
pv_loop = 0.0
for t, c in enumerate(c_t, start=1):
pv_loop += c / (1 + r) ** t
print(f"nbt = {nbt} dates, discount rate r = {r:.2%}")
print(f"PV via loop = ${pv_loop:.6f}")
nbt = 5 dates, discount rate r = 5.00% PV via loop = $1216.473834
For a bond with a constant coupon $c$ and face value $F$ repaid at maturity $T$, summing the geometric series in (10.1) gives the closed form
$$ PV \;=\; c \cdot \frac{1 - (1+r)^{-T}}{r} \;+\; \frac{F}{(1+r)^{T}}. \tag{10.2} $$This is a genuinely independent route to the same number: (10.1) adds $T$ terms one at a time, while (10.2) evaluates a formula obtained analytically. If they disagree, one of the two is wrong, and that is information.
c, F, T = 100, 1000, nbt
pv_formula = c * (1 - (1 + r) ** -T) / r + F / (1 + r) ** T
print(f"PV via formula = ${pv_formula:.6f}")
gap = abs(pv_loop - pv_formula)
tol = 1e-10
print(f"|loop - formula| = {gap:.2e} (tolerance {tol:.0e})")
assert gap < tol, "the two routes disagree — one of them is wrong"
print("check passed.")
PV via formula = $1216.473834 |loop - formula| = 2.27e-13 (tolerance 1e-10) check passed.
The two values agree to about $10^{-13}$, which is a few units in the last place of a double-precision number: the accumulated rounding error of five divisions, and nothing more. Reporting the gap and the tolerance, rather than printing two numbers and eyeballing them, is what we will do after every computation in this series.
Note also that the bond trades below par: at a 5% discount rate a 10% coupon is worth more than its face value, so $PV > F$. It is worth pausing on the sign of that comparison before moving on: a check on the economics is as valuable as a check on the arithmetic.
This is, deliberately, a slow way to price one bond. In fd08 the same calculation collapses to a single line, runs on vectors of cash flows in microseconds, and scales to portfolios of millions of bonds. The loop is the honest version; vectorization is the fast one. We will always see both.
11. Discount factors are prices: the first dual object of the series¶
Rewrite (10.1) by naming the discount factors. Let
$$ p_t \;=\; \frac{1}{(1+r)^{t}}, \qquad t = 1, \dots, T, $$so that
$$ PV \;=\; \sum_{t=1}^{T} p_t \, c_t \;=\; \langle p, c \rangle. \tag{11.1} $$Read economically, $p_t$ is the price today of one dollar delivered at date $t$: an Arrow–Debreu state price, with dates playing the role of states. Present value is then not a formula but a valuation: the inner product of a price vector with a quantity vector. The cash flow $c$ is the primal object, a quantity, in dollars per date; the price $p$ is the dual object, a value, in today's dollars per date-$t$ dollar. The two live in dual spaces, and $\langle p, c\rangle$ is the pairing between them.
This is the pattern the whole 'math+econ+code' series is organized around, and it is worth naming on day one:
Quantities, masses $\mu_{xy}$, flows, occupation measures, are primal. Values, prices, potentials, value functions, are dual. The number we care about is their pairing, and the economics lives in the dual variable.
In this lecture the price vector is exogenous: we assumed a flat rate $r$ and wrote down $p_t$. From the dp series onward it stops being exogenous and becomes a multiplier. In dp01, the value function is the multiplier on the mass-balance constraint of a dynamic program, and the discount factor $\beta^t$ is exactly the price of a date-$t$ dollar in that dual problem; in lp01, prices are the dual variables of a linear program, and complementary slackness, written $0 \le \rho \perp \mu \ge 0$ in this series, determines which activities carry positive mass. Present value is the simplest possible instance of that structure: no optimization yet, but already the pairing.
The code below computes the price vector explicitly and takes the inner product. It is the third independent route to the same number.
# The price vector: p_t[i] is the price today of one dollar delivered at date i+1
p_t = [(1 + r) ** -(t + 1) for t in range(nbt)]
pv_prices = sum(p * c for p, c in zip(p_t, c_t))
print(f"{'date t':>7}{'price p_t':>13}{'cash flow c_t':>16}{'value p_t c_t':>16}")
print("-" * 52)
for t in range(nbt):
print(f"{t + 1:>7}{p_t[t]:>13.6f}{c_t[t]:>16.2f}{p_t[t] * c_t[t]:>16.6f}")
print("-" * 52)
print(f"PV via prices = ${pv_prices:.6f}")
gap = max(abs(pv_prices - pv_loop), abs(pv_prices - pv_formula))
tol = 1e-10
print(f"max gap across the three routes = {gap:.2e} (tolerance {tol:.0e})")
assert gap < tol
print("check passed: three routes, one number.")
date t price p_t cash flow c_t value p_t c_t
----------------------------------------------------
1 0.952381 100.00 95.238095
2 0.907029 100.00 90.702948
3 0.863838 100.00 86.383760
4 0.822702 100.00 82.270247
5 0.783526 1100.00 861.878783
----------------------------------------------------
PV via prices = $1216.473834
max gap across the three routes = 2.27e-13 (tolerance 1e-10)
check passed: three routes, one number.
Three computations, one number, agreement at the level of machine rounding. The middle column of the table is the relevant object: prices fall geometrically with the date, from $0.952$ for a dollar next year to $0.784$ for a dollar in five years. The far-dated dollar is not worth less because it is smaller; it is worth less because its price is lower. The entire discounted-cash-flow apparatus of finance is that one price vector, and every dynamic program in this masterclass series will produce its own version of it.
A useful sanity check on the economics, not just the arithmetic: the prices are strictly positive and strictly decreasing in $t$ whenever $r > 0$. Positivity is no-arbitrage, a dollar delivered for free cannot have a negative price, and monotonicity is impatience. If a computation ever hands you a negative state price, the model, not the code, is where to look first.
12. Worked example: Newton's method¶
A classical numerical exercise: compute $\sqrt{2}$ by solving $f(x) = x^2 - 2 = 0$. Newton's iteration is
$$ x_{k+1} \;=\; x_k - \frac{f(x_k)}{f'(x_k)} \;=\; x_k - \frac{x_k^2 - 2}{2 x_k} \;=\; \tfrac{1}{2}\!\left(x_k + \frac{2}{x_k}\right), \tag{12.1} $$which is also the Babylonian algorithm, known in essentially this form to Hero of Alexandria. Starting from $x_0 = 1$, six iterations suffice.
x = 1.0
history = [x]
for k in range(6):
x = 0.5 * (x + 2 / x)
history.append(x)
print(f"k = {k}: x = {x:.16f} x^2 - 2 = {x ** 2 - 2:+.2e}")
k = 0: x = 1.5000000000000000 x^2 - 2 = +2.50e-01 k = 1: x = 1.4166666666666665 x^2 - 2 = +6.94e-03 k = 2: x = 1.4142156862745097 x^2 - 2 = +6.01e-06 k = 3: x = 1.4142135623746899 x^2 - 2 = +4.51e-12 k = 4: x = 1.4142135623730949 x^2 - 2 = -4.44e-16 k = 5: x = 1.4142135623730949 x^2 - 2 = -4.44e-16
Six iterations from a deliberately poor initial guess, and we are at machine precision. But "quadratic convergence" is a claim, and claims get checked. Subtracting $\sqrt 2$ from both sides of (12.1) and putting the result over a common denominator gives an exact identity for the error $e_k = x_k - \sqrt 2$:
$$ e_{k+1} \;=\; \frac{e_k^{\,2}}{2 x_k}, \qquad\text{so}\qquad \frac{e_{k+1}}{e_k^{\,2}} \;=\; \frac{1}{2 x_k} \;\longrightarrow\; \frac{1}{2\sqrt 2} \approx 0.353553. \tag{12.2} $$That is a sharp prediction: the ratio is not merely bounded, it equals $1/(2x_k)$ at every step. Checking a predicted rate rather than only a limit is a much stronger test, and it costs nothing.
It also raises the question of what tolerance to check it against, and here a flat tolerance would be wrong. The error $e_{k+1} = x_{k+1} - \sqrt 2$ is computed as the difference of two nearly equal doubles, so it carries an absolute rounding error of order $\varepsilon\sqrt 2$, where $\varepsilon \approx 2.2\times10^{-16}$ is machine epsilon. Dividing by $e_k^2$ magnifies that error, so the ratio can only be measured to within
$$ \text{noise floor}_k \;\approx\; \frac{2\varepsilon\sqrt 2}{e_k^{\,2}}, \tag{12.3} $$which grows as the method converges. The right check is therefore against (12.3), row by row, and the table must stop once the floor exceeds the effect being measured. A verification that ignores its own precision is not a verification.
root = math.sqrt(2)
eps = sys.float_info.epsilon
print(f"{'k':>3}{'e_k':>12}{'e_(k+1)/e_k^2':>17}{'1/(2 x_k)':>13}{'gap':>11}{'noise floor':>14} ok")
print("-" * 75)
for k in range(len(history) - 1):
e_k = history[k] - root
floor = 2 * eps * root / e_k ** 2 # (12.3): precision of the measured ratio
if floor > 1e-3: # below this error, the ratio is no longer measurable
break
ratio = (history[k + 1] - root) / e_k ** 2
predicted = 1 / (2 * history[k])
gap = abs(ratio - predicted)
ok = gap <= floor
print(f"{k:>3}{e_k:>12.2e}{ratio:>17.9f}{predicted:>13.9f}{gap:>11.1e}{floor:>14.1e} {ok}")
assert ok, f"at k={k} the observed rate departs from theory by more than rounding explains"
print("-" * 75)
print(f"check passed: e_(k+1) = e_k^2 / (2 x_k) holds to the rounding floor at every measurable step.")
print(f"limit of 1/(2 x_k) is 1/(2*sqrt(2)) = {1 / (2 * root):.9f}")
k e_k e_(k+1)/e_k^2 1/(2 x_k) gap noise floor ok --------------------------------------------------------------------------- 0 -4.14e-01 0.500000000 0.500000000 8.3e-16 3.7e-15 True 1 8.58e-02 0.333333333 0.333333333 3.2e-14 8.5e-14 True 2 2.45e-03 0.352941176 0.352941176 3.9e-11 1.0e-10 True 3 2.12e-06 0.353522385 0.353552860 3.0e-05 1.4e-04 True --------------------------------------------------------------------------- check passed: e_(k+1) = e_k^2 / (2 x_k) holds to the rounding floor at every measurable step. limit of 1/(2 x_k) is 1/(2*sqrt(2)) = 0.353553391
Every row passes, and the last column explains why the table stops where it does: by $k=3$ the error is $2\times10^{-6}$, the predicted next error is around $10^{-12}$, and measuring it costs four digits of precision. One step later there is nothing left to measure. The gap column tracking the noise floor, rather than staying flat, is itself the evidence that the only discrepancy is floating-point rounding.
The ratio reproduces $1/(2x_k)$ to the precision available, and $1/(2x_k) \to 1/(2\sqrt2)$. The number of correct digits roughly doubles at each step, which is what "quadratic" means operationally.
Three remarks worth carrying forward. First, this is the template for the rest of the series: we did not merely observe convergence, we verified the rate the theory predicts, and we stated the tolerance: derived, not guessed. Second, when a check fails, the bug is as often in the check as in the code: a flat tolerance here would have flagged a perfectly correct implementation, because it ignored the precision of the measurement itself. Third, quadratic convergence is a local property. We started at $x_0 = 1$, comfortably inside the basin of attraction; from $x_0 = 0$ the method fails at once, since $f'(0) = 0$. In fd09 we hand harder root-finding and minimization problems to scipy.optimize, whose robust solvers exist precisely for the cases where the naive iteration misbehaves, and in lp03, interior-point methods for linear programs turn out to be Newton's method applied to a perturbed optimality system. The underlying logic, iterate a map until you stop moving, is what we just did by hand.
13. Five common traps¶
A list to keep on hand; several return in later notebooks.
- Float equality.
0.1 + 0.2 == 0.3isFalse. Usemath.isclose, or, fromfd08,numpy.isclose, and state the tolerance. - Integer versus true division.
7 / 2is3.5;7 // 2is3. In Python 2, which you will occasionally meet in old replication code,/was floor division on integers: a major source of silent bugs in ported programs. - Operator precedence.
2 ** 3 ** 2is2 ** 9 = 512, not8 ** 2 = 64, because**is right-associative. When in doubt, parenthesize. - Out-of-order cell execution. Restart and run all before you submit anything. If your notebook only works in the order you happened to run the cells, it is not reproducible.
isversus==.==compares values;iscompares object identity.1000 == 1000is alwaysTrue, whereas1000 is 1000may beTrueorFalsedepending on the implementation. Use==unless you specifically mean to ask whether two names refer to the same object.
14. Summary¶
We have a running Python environment, Colab, Miniforge, or VS Code, and we know how to verify it, restart it, and diagnose the four things that go wrong in a first session.
We can read and write the core of the language: numbers and their floating-point pathologies, types and dynamic binding, booleans and truthiness, and the two forms of control flow.
Two conventions are now in force for the rest of the series. Names record axes:
c_tis indexed by dates,mu_x_yby $(x,y)$, andnbt,nbxcount them. Numbers get checked twice: we priced the bond by loop, by closed form, and by an inner product, and we verified Newton's convergence rate, not merely its convergence: each time reporting the gap alongside the tolerance we were prepared to accept.The economics of the lecture is in §11. Present value is not a formula but a pairing $\langle p, c\rangle$ between a quantity vector and a price vector, and the discount factor $p_t = (1+r)^{-t}$ is the price today of a dollar delivered at $t$. Positive prices are no-arbitrage; decreasing prices are impatience. This is the first dual variable of the series, and it is exogenous here only because there is no optimization yet: from
dp01onward the same object arrives as a multiplier on a constraint, and reading the multiplier is the economics.
15. Exercises¶
Write your answer in the cell below each prompt. There is no automated grader: check your answer against the expected value where one is given, and, following the practice of §10 and §12, print the gap alongside the tolerance you accept.
Worked solutions are given in §17, at the end of this notebook. Attempt each exercise before reading them: the solutions are written to be instructive rather than merely correct, and several of them make a point that the exercise statement deliberately does not give away.
Exercise 1: Compound interest and the continuous limit. A dollar invested at annual rate $r = 4\%$, compounded $n$ times per year, grows to $(1 + r/n)^{nT}$ after $T$ years, and to $e^{rT}$ in the continuous limit. Compute both for $T = 25$ and $n \in \{1, 12, 365, 10\,000\}$.
The error is known to be $O(1/n)$. Verify that claim rather than asserting it: print $n \times (\text{error})$ alongside the error, and check that this product settles down to a constant.
# your answer here
Exercise 2: The annuity formula (proof, then check). Prove the closed form (10.2) used in §10. Specifically, show that for $r > 0$,
$$ \sum_{t=1}^{T} (1+r)^{-t} \;=\; \frac{1 - (1+r)^{-T}}{r}, $$by summing the geometric series, and deduce (10.2). Show also that the perpetuity limit $T \to \infty$ is $1/r$, and say where the assumption $r>0$ is used.
Then verify the identity numerically: for each $(r, T)$ in $\{0.01, 0.05, 0.20\} \times \{1, 5, 30, 200\}$, compare the sum computed by a loop with the closed form, and report the largest relative gap across all twelve cases together with the tolerance you accept.
# your answer here
Exercise 3: Internal rate of return. For the cash-flow stream c_t = [-1000, 200, 300, 400, 500]: an outflow at $t = 0$ followed by four inflows: the internal rate of return is the rate $r$ at which the present value of the stream is zero. With $g(r) = \sum_{t} c_t (1+r)^{-t}$, we have $g'(r) = -\sum_t t\, c_t (1+r)^{-t-1}$.
Find the IRR by Newton's method starting from $r_0 = 0.05$, and verify it by an independent route: re-solve by bisection on a bracket $[0, 1]$, a method that uses no derivative and cannot converge to the same wrong answer for the same reason, and report the gap between the two roots against a stated tolerance. Check also that $|g(r)|$ is at the level of machine rounding.
Then explain, in a sentence or two, why this stream has exactly one root while a stream whose cash flows change sign several times may have several, and why that makes the IRR a less reliable device for ranking projects than present value. (Hint: written in the variable $z = (1+r)^{-1}$, $g$ is a polynomial, and Descartes' rule of signs applies.)
# your answer here
Exercise 4: Duration as a derivative of the valuation. For the five-year bond of §10, the Macaulay duration is the price-weighted average date of the cash flows,
$$ D \;=\; \frac{1}{PV}\sum_{t=1}^{T} t \, p_t \, c_t, $$and it is related to the sensitivity of value to the discount rate by $\dfrac{dPV}{dr} = -\dfrac{D}{1+r} PV$.
Compute $D$ from the definition. Then verify the relation by finite differences: form $\big(PV(r + h) - PV(r - h)\big) / (2h)$ for $h = 10^{-5}$ and compare it with $-D\,PV/(1+r)$, reporting the relative gap and your tolerance. Interpret $D$: in what units is it measured, and what does it say about which dated dollar dominates the bond's value?
(In fd10 we obtain this same derivative exactly, and at machine precision, by automatic differentiation rather than by finite differences.)
# your answer here
Exercise 5: Leibniz's series for $\pi$. Use
$$ \frac{\pi}{4} \;=\; 1 - \frac{1}{3} + \frac{1}{5} - \frac{1}{7} + \cdots $$to estimate $\pi$ from the first $N$ terms, for $N \in \{10, 10^3, 10^5, 10^7\}$. Report the error at each $N$ and identify the rate at which it decays; how many terms would you need for ten correct digits?
Contrast this with the quadratic convergence measured in §12: what is it about the two problems that makes one converge in six steps and the other in more steps than you would care to run? (In fd08 you will recompute this series with NumPy in one vectorized line, and in fd08 you will estimate $\pi$ by a quite different route, Monte Carlo, whose error decays more slowly still, like $N^{-1/2}$.)
# your answer here
16. Further directions¶
You now have enough Python to write small numerical programs, and two working habits: names that record their axes, and numbers that are checked against a second route with a stated tolerance.
The next notebook, fd02, introduces the containers, lists, tuples, dictionaries, sets, together with the comprehensions, generators, and unpacking idioms that make Python code read as Python rather than as translated C. Dictionaries in particular will become our index maps: the bookkeeping that turns a pair $(x,y)$ into a row of a constraint matrix. From there we move to functions and modules (fd03), to making that code fast and tested (fd04), to Git and the reproducible research compendium (fd05), through data in fd06 and fd07, and then into the scientific stack proper, beginning with NumPy in fd08, where the price vector of §11 becomes an array, the inner product becomes a single call, and the Kronecker identity $\operatorname{vec}_C(AXB) = (A \otimes B^\top)\operatorname{vec}_C(X)$ starts doing real work.
Save your work, restart the kernel, and run all cells top-to-bottom before you move on: if a notebook runs only in the order in which you happened to execute the cells, it is not reproducible.
17. Solutions to the exercises¶
Reference solutions, using only what this lecture introduces: the standard-library math module, loops, and simple functions; no NumPy, which arrives in fd08. Following the practice of the lecture, every numerical answer is checked against a second, independent route, and every check states the tolerance it accepts.
The cells below re-establish the objects they need, so this section can be read as a unit; it does rebind names used earlier in the notebook, which is harmless because nothing after it depends on them.
Solution to Exercise 1: Compound interest and the continuous limit¶
The rate is easy to predict analytically, which makes the check sharper than "the numbers get closer". Writing $(1+r/n)^{nT} = \exp\!\big(nT\log(1+r/n)\big)$ and expanding $\log(1+u) = u - u^2/2 + O(u^3)$ at $u = r/n$,
$$ nT\log\!\Big(1+\frac{r}{n}\Big) \;=\; rT - \frac{r^2 T}{2n} + O(n^{-2}), $$so that
$$ e^{rT} - \Big(1+\frac{r}{n}\Big)^{nT} \;=\; e^{rT}\Big(1 - e^{-r^2T/(2n) + O(n^{-2})}\Big) \;=\; \frac{r^2 T}{2}\,e^{rT}\cdot\frac{1}{n} + O(n^{-2}). $$So $n \times (\text{error})$ should not merely settle down: it should settle down to the specific constant $\tfrac{1}{2}r^2 T e^{rT}$, and that is what we check.
r_ex1, T_ex1 = 0.04, 25
continuous = math.exp(r_ex1 * T_ex1)
predicted_constant = 0.5 * r_ex1 ** 2 * T_ex1 * continuous
print(f"continuous limit e^(rT) = {continuous:.10f}")
print(f"predicted limit of n x error = r^2 T e^(rT) / 2 = {predicted_constant:.6f}\n")
print(f"{'n':>8}{'(1+r/n)^(nT)':>18}{'error':>12}{'n x error':>13}")
print("-" * 51)
for n in (1, 12, 365, 10_000):
discrete = (1 + r_ex1 / n) ** (n * T_ex1)
error = continuous - discrete
print(f"{n:>8}{discrete:>18.10f}{error:>12.2e}{n * error:>13.6f}")
last = n * error
rel_gap, tol = abs(last / predicted_constant - 1), 1e-3
print("-" * 51)
print(f"at n = 10000, |n x error / predicted - 1| = {rel_gap:.2e} (tolerance {tol:.0e})")
assert rel_gap < tol, "the error does not decay at the predicted 1/n rate"
print("check passed: the error is O(1/n), with the predicted constant.")
continuous limit e^(rT) = 2.7182818285
predicted limit of n x error = r^2 T e^(rT) / 2 = 0.054366
n (1+r/n)^(nT) error n x error
---------------------------------------------------
1 2.6658363315 5.24e-02 0.052445
12 2.7137651579 4.52e-03 0.054200
365 2.7181328965 1.49e-04 0.054360
10000 2.7182763918 5.44e-06 0.054366
---------------------------------------------------
at n = 10000, |n x error / predicted - 1| = 9.71e-06 (tolerance 1e-03)
check passed: the error is O(1/n), with the predicted constant.
The product $n \times \text{error}$ converges to $\tfrac12 r^2 T e^{rT} \approx 0.0544$, confirming both the rate and its constant. Economically, the gap between annual and continuous compounding at 4% over 25 years is about five cents on the dollar: small, but not negligible once it is a contract rather than an approximation. Daily compounding ($n = 365$) is already within $1.5\times10^{-4}$ of the continuous limit, which is why continuous time is such a convenient modelling fiction.
Solution to Exercise 2: The annuity formula¶
Claim. For $r > 0$ and $T \in \mathbb{N}$,
$$ A(r,T) \;:=\; \sum_{t=1}^{T} (1+r)^{-t} \;=\; \frac{1 - (1+r)^{-T}}{r}. $$Proof. Set $z = (1+r)^{-1}$, so that $0 < z < 1$ precisely because $r > 0$. The sum is geometric with first term $z$ and ratio $z$:
$$ \sum_{t=1}^{T} z^{t} \;=\; z\,\frac{1 - z^{T}}{1 - z}. $$Now $1 - z = 1 - (1+r)^{-1} = r(1+r)^{-1} = rz$, so $z/(1-z) = 1/r$, and therefore
$$ \sum_{t=1}^{T} z^{t} \;=\; \frac{1 - z^{T}}{r} \;=\; \frac{1 - (1+r)^{-T}}{r}. \qquad \blacksquare $$Where $r>0$ is used. Twice, and in different ways. First, $r \neq 0$ is needed to divide by $r$; at $r = 0$ the identity degenerates and the correct value is $A(0,T) = T$, which is also the limit of the right-hand side as $r \to 0$ by l'Hôpital. Second, $r > 0$ gives $z < 1$, which is what makes the perpetuity limit exist: since $z^T \to 0$,
$$ \lim_{T \to \infty} A(r,T) \;=\; \frac{1}{r}. $$For $-1 < r < 0$ the closed form remains algebraically valid at finite $T$, the geometric sum formula does not require $|z|<1$, but $z > 1$, so the perpetuity diverges: an infinite stream of dollars discounted at a negative rate is worth infinitely much, as it should be.
Deduction of (10.2). A bond paying a constant coupon $c$ at $t = 1,\dots,T$ plus face value $F$ at $T$ has $c_t = c$ for $t<T$ and $c_T = c + F$, so
$$ PV \;=\; c\sum_{t=1}^{T}(1+r)^{-t} + F(1+r)^{-T} \;=\; c\,\frac{1-(1+r)^{-T}}{r} + \frac{F}{(1+r)^{T}}, $$which is (10.2).
def annuity_loop(rate, horizon):
# sum_{t=1}^{horizon} (1+rate)^{-t}, term by term
total = 0.0
for t in range(1, horizon + 1):
total += (1 + rate) ** -t
return total
def annuity_closed(rate, horizon):
return (1 - (1 + rate) ** -horizon) / rate
print(f"{'r':>6}{'T':>6}{'loop':>16}{'closed form':>16}{'rel. gap':>12}")
print("-" * 56)
worst = 0.0
for r_ in (0.01, 0.05, 0.20):
for T_ in (1, 5, 30, 200):
a_loop, a_closed = annuity_loop(r_, T_), annuity_closed(r_, T_)
rel = abs(a_loop - a_closed) / abs(a_closed)
worst = max(worst, rel)
print(f"{r_:>6.2f}{T_:>6}{a_loop:>16.10f}{a_closed:>16.10f}{rel:>12.1e}")
tol = 1e-12
print("-" * 56)
print(f"worst relative gap = {worst:.1e} (tolerance {tol:.0e})")
assert worst < tol, "the closed form does not reproduce the summed series"
print("check passed.")
r T loop closed form rel. gap -------------------------------------------------------- 0.01 1 0.9900990099 0.9900990099 9.0e-16 0.01 5 4.8534312393 4.8534312393 5.5e-16 0.01 30 25.8077082213 25.8077082213 9.6e-16 0.01 200 86.3313619478 86.3313619478 3.3e-16 0.05 1 0.9523809524 0.9523809524 1.2e-15 0.05 5 4.3294766706 4.3294766706 8.2e-16 0.05 30 15.3724510269 15.3724510269 8.1e-16 0.05 200 19.9988434346 19.9988434346 1.6e-15 0.20 1 0.8333333333 0.8333333333 2.7e-16 0.20 5 2.9906121399 2.9906121399 3.0e-16 0.20 30 4.9789363988 4.9789363988 7.1e-16 0.20 200 5.0000000000 5.0000000000 7.1e-16 -------------------------------------------------------- worst relative gap = 1.6e-15 (tolerance 1e-12) check passed.
# The perpetuity limit
print(f"{'r':>6}{'A(r, 200)':>14}{'1/r':>14}{'gap':>10}")
print("-" * 44)
for r_ in (0.01, 0.05, 0.20):
print(f"{r_:>6.2f}{annuity_closed(r_, 200):>14.6f}{1 / r_:>14.6f}"
f"{abs(annuity_closed(r_, 200) - 1 / r_):>10.1e}")
r A(r, 200) 1/r gap -------------------------------------------- 0.01 86.331362 100.000000 1.4e+01 0.05 19.998843 20.000000 1.2e-03 0.20 5.000000 5.000000 8.9e-16
# The degenerate case r -> 0, where A(0, T) = T: which route survives?
print(f"{'r':>10}{'loop':>16}{'closed form':>16}{'error of closed':>18}")
print("-" * 60)
for r_ in (1e-4, 1e-8, 1e-12, 1e-15):
a_loop, a_closed = annuity_loop(r_, 30), annuity_closed(r_, 30)
print(f"{r_:>10.0e}{a_loop:>16.8f}{a_closed:>16.8f}{abs(a_closed - a_loop):>18.2e}")
print("-" * 60)
print("the loop degrades gracefully to A(0, 30) = 30; the closed form does not.")
r loop closed form error of closed
------------------------------------------------------------
1e-04 29.95354956 29.95354956 3.69e-12
1e-08 29.99999535 29.99999517 1.84e-07
1e-12 30.00000000 30.00266702 2.67e-03
1e-15 30.00000000 33.30669074 3.31e+00
------------------------------------------------------------
the loop degrades gracefully to A(0, 30) = 30; the closed form does not.
At $r = 20\%$ a 200-year annuity is worth $5.0000$, indistinguishable from the perpetuity value $1/r = 5$: at that discount rate everything beyond a few decades is worth essentially nothing. At $r = 1\%$ the same annuity is worth $86.33$ against a perpetuity value of $100$, so nearly 14% of the value still lies beyond year 200. The discount rate does not merely scale value; it determines the horizon over which value exists at all, which is precisely the difficulty at the centre of the discounting debate in climate economics.
The last cell makes a numerical point worth more than the identity it illustrates. The two routes are mathematically equal but not numerically interchangeable as $r \to 0$. In the closed form, the numerator $1 - (1+r)^{-T}$ subtracts two numbers that agree to about $\log_{10}(1/rT)$ digits, so the subtraction discards exactly those digits, catastrophic cancellation, and dividing by the small number $r$ then amplifies what remains. The damage is visible in the table: at $r = 10^{-8}$ the closed form has already lost half its digits, at $r = 10^{-12}$ only about four significant digits survive, and at $r = 10^{-15}$ it returns $33.31$ in place of $30$, an 11% error, while the loop is still returning $30.00000000$ throughout.
The lesson recurs throughout numerical work: algebraically equivalent expressions are not numerically equivalent, and the faster, more elegant one is not automatically the one to ship. Here the honest slow loop is the robust route near $r = 0$ and the closed form is the right route everywhere else. Knowing which regime you are in is part of the model, not an implementation detail.
Solution to Exercise 3: Internal rate of return¶
With $c = (-1000, 200, 300, 400, 500)$ at dates $t = 0,\dots,4$, the IRR solves $g(r) = 0$ where
$$ g(r) \;=\; \sum_{t=0}^{4} c_t (1+r)^{-t}, \qquad g'(r) \;=\; -\sum_{t=0}^{4} t\, c_t (1+r)^{-t-1}. $$We solve by Newton from $r_0 = 0.05$, then re-solve by bisection on $[0,1]$. Bisection uses no derivative and converges for a completely different reason, it needs only a sign change and the intermediate value theorem, so agreement between the two is genuine evidence rather than two copies of the same mistake.
c_t = [-1000, 200, 300, 400, 500]
def g(rate):
return sum(c / (1 + rate) ** t for t, c in enumerate(c_t))
def g_prime(rate):
return sum(-t * c / (1 + rate) ** (t + 1) for t, c in enumerate(c_t))
# --- route 1: Newton
r_newton = 0.05
for iteration in range(100):
step = g(r_newton) / g_prime(r_newton)
r_newton -= step
if abs(step) < 1e-14:
break
print(f"Newton: IRR = {r_newton:.12f} after {iteration + 1} iterations")
# --- route 2: bisection on a bracket, derivative-free
lo, hi = 0.0, 1.0
assert g(lo) > 0 > g(hi), "the bracket does not contain a sign change"
for _ in range(200):
mid = 0.5 * (lo + hi)
if g(mid) > 0:
lo = mid
else:
hi = mid
r_bisect = 0.5 * (lo + hi)
print(f"bisection: IRR = {r_bisect:.12f}")
gap, tol = abs(r_newton - r_bisect), 1e-12
print(f"\n|Newton - bisection| = {gap:.2e} (tolerance {tol:.0e})")
assert gap < tol, "two independent methods disagree on the root"
print(f"residual |g(IRR)| = {abs(g(r_newton)):.2e} (machine rounding on a PV of order 1e3)")
print(f"check passed: IRR = {100 * r_newton:.4f}% per period.")
Newton: IRR = 0.128257269002 after 6 iterations bisection: IRR = 0.128257269002 |Newton - bisection| = 1.67e-16 (tolerance 1e-12) residual |g(IRR)| = 8.53e-14 (machine rounding on a PV of order 1e3) check passed: IRR = 12.8257% per period.
Why there is exactly one root here. Substituting $z = (1+r)^{-1}$ turns $g$ into the polynomial
$$ G(z) \;=\; -1000 + 200z + 300z^2 + 400z^3 + 500z^4, $$whose coefficient sequence $(-,+,+,+,+)$ has a single sign change. By Descartes' rule of signs, $G$ has exactly one positive real root $z^\ast$, hence exactly one $r^\ast = 1/z^\ast - 1 > -1$. The economic content of the sign pattern is that this is a conventional project: pay once, receive thereafter.
Why IRR is the weaker ranking device. A stream whose cash flows change sign several times, an investment requiring a costly cleanup at the end, say $(-,+,+,-)$, gives $G$ several sign changes and admits several positive roots, so "the" IRR is not well defined. And even with a unique IRR, ranking two projects by it ignores their scale, since the IRR is invariant to multiplying the whole stream by a positive constant. Present value has neither defect: given the price vector $p$ of §11, $PV = \langle p, c\rangle$ is a single well-defined number, it is additive across projects, and it is exactly the quantity a value-maximizing firm should rank by. The IRR answers "at what discount rate would this break even?", which is a different question from "how much is this worth?".
Solution to Exercise 4: Duration as a derivative of the valuation¶
For the bond of §10, with prices $p_t = (1+r)^{-t}$ and $PV = \sum_t p_t c_t$, the Macaulay duration is the price-weighted average date,
$$ D \;=\; \frac{1}{PV}\sum_{t=1}^{T} t\, p_t\, c_t, $$and it governs the sensitivity of value to the rate. Differentiating $PV = \sum_t c_t (1+r)^{-t}$ term by term,
$$ \frac{dPV}{dr} \;=\; -\sum_{t=1}^{T} t\, c_t (1+r)^{-t-1} \;=\; -\frac{1}{1+r}\sum_{t=1}^{T} t\, p_t c_t \;=\; -\frac{D}{1+r}\,PV, $$which is the stated relation. We compute $D$ from its definition and check the relation against a central finite difference.
c_t = [100, 100, 100, 100, 100 + 1000]
nbt = len(c_t)
r = 0.05
def pv(rate):
return sum(c / (1 + rate) ** (t + 1) for t, c in enumerate(c_t))
p_t = [(1 + r) ** -(t + 1) for t in range(nbt)]
PV = pv(r)
duration = sum((t + 1) * p_t[t] * c_t[t] for t in range(nbt)) / PV
print(f"PV = ${PV:.6f}")
print(f"duration = {duration:.6f} years (maturity is {nbt} years)\n")
print(f"{'date t':>7}{'p_t c_t':>13}{'share of PV':>14}")
print("-" * 34)
for t in range(nbt):
print(f"{t + 1:>7}{p_t[t] * c_t[t]:>13.4f}{p_t[t] * c_t[t] / PV:>14.2%}")
PV = $1216.473834
duration = 4.253499 years (maturity is 5 years)
date t p_t c_t share of PV
----------------------------------
1 95.2381 7.83%
2 90.7029 7.46%
3 86.3838 7.10%
4 82.2702 6.76%
5 861.8788 70.85%
# verify dPV/dr = -D PV / (1+r) against a central difference
h = 1e-5
fd = (pv(r + h) - pv(r - h)) / (2 * h)
analytic = -duration * PV / (1 + r)
rel_gap, tol = abs(fd - analytic) / abs(analytic), 1e-6
print(f"central difference (h = {h:.0e}) = {fd:.6f}")
print(f"-D PV / (1+r) = {analytic:.6f}")
print(f"relative gap = {rel_gap:.2e} (tolerance {tol:.0e})")
assert rel_gap < tol, "the duration relation does not reproduce the numerical derivative"
print("check passed.")
central difference (h = 1e-05) = -4927.876361 -D PV / (1+r) = -4927.876358 relative gap = 5.88e-10 (tolerance 1e-06) check passed.
Interpretation. Duration is measured in years: it is a weighted average of the dates $t$, with weights $p_t c_t / PV$: the share of today's value contributed by each dated dollar. Here $D \approx 4.25$ years against a maturity of 5, and the table explains why: the final payment, coupon plus principal, accounts for about 71% of the bond's value, so the bond behaves like a claim concentrated near year 5 rather than one spread evenly across the five years. Duration answers "when, on average, does this bond actually pay?": weighted by value, not by dollars.
The relation $dPV/dr = -D\,PV/(1+r)$ then says that duration is the interest-rate elasticity of value, up to the factor $1+r$: a bond with twice the duration loses roughly twice as much value for a given rise in rates. This is the basic hedging quantity in fixed income, and it is nothing but a derivative of the pairing $\langle p, c\rangle$ with respect to the parameter governing the price vector.
Note finally what the finite difference cost us. With $h = 10^{-5}$ we recover about nine correct digits: truncation error is $O(h^2)$ and rounding error is $O(\varepsilon/h)$, and their sum is minimized around $h \sim \varepsilon^{1/3} \approx 6\times10^{-6}$: no choice of $h$ does much better. In fd10 the same derivative is obtained by automatic differentiation to full machine precision, at a cost comparable to a single evaluation of $PV$ and with no step size to choose.
Solution to Exercise 5: Leibniz's series for $\pi$¶
$$ \frac{\pi}{4} \;=\; \sum_{k=0}^{\infty} \frac{(-1)^k}{2k+1}. $$For an alternating series whose terms decrease to zero, the truncation error after $N$ terms is bounded by, and here asymptotically equal to half of, the first omitted term. Since that term is $4/(2N+1)$, the error should be about $2/(2N+1) \approx 1/N$, so $N \times \text{error}$ should tend to $1$.
print(f"{'N':>10}{'estimate of pi':>18}{'error':>12}{'N x error':>12}")
print("-" * 52)
for N in (10, 10 ** 3, 10 ** 5, 10 ** 7):
s = 0.0
for k in range(N):
s += (-1) ** k / (2 * k + 1)
pi_est = 4 * s
error = abs(math.pi - pi_est)
print(f"{N:>10}{pi_est:>18.10f}{error:>12.2e}{N * error:>12.6f}")
last_product = N * error
gap, tol = abs(last_product - 1.0), 1e-3
print("-" * 52)
print(f"|N x error - 1| = {gap:.2e} at N = 1e7 (tolerance {tol:.0e})")
assert gap < tol, "the error does not decay at the predicted 1/N rate"
print("check passed: the error is asymptotically 1/N.")
N estimate of pi error N x error
----------------------------------------------------
10 3.0418396189 9.98e-02 0.997530
1000 3.1405926538 1.00e-03 1.000000
100000 3.1415826536 1.00e-05 1.000000
10000000 3.1415925536 1.00e-07 1.000000 ---------------------------------------------------- |N x error - 1| = 1.61e-08 at N = 1e7 (tolerance 1e-03) check passed: the error is asymptotically 1/N.
# how many terms for ten correct digits?
target = 0.5e-10 # error below half a unit in the tenth decimal
terms = 1 / target
rate = 1e7 # terms per second, roughly, in pure Python
print(f"error ~ 1/N, so ten correct digits needs N ~ {terms:.0e} terms.")
print(f"at roughly {rate:.0e} terms per second that is about {terms / rate / 60:.0f} minutes of arithmetic,")
print("for a constant already known to more than 1e5 digits by better methods.")
error ~ 1/N, so ten correct digits needs N ~ 2e+10 terms. at roughly 1e+07 terms per second that is about 33 minutes of arithmetic, for a constant already known to more than 1e5 digits by better methods.
The contrast with §12. Newton's method reached machine precision in six steps; Leibniz needs on the order of $2\times10^{10}$ terms for ten digits. The difference is not effort but information. Newton evaluates the derivative at each step, so the iteration is self-correcting: the map has a fixed point at $\sqrt2$ with zero derivative there, which is exactly the condition for quadratic convergence, and each step squares the error. Leibniz has no such mechanism: it is a fixed sequence of terms, each contributing an amount that decays only like $1/k$, so buying one more digit costs a factor of ten in work, forever.
The practical lesson generalizes well beyond $\pi$. When a computation converges slowly, the productive question is rarely "can I run more iterations?" but "is there a formulation that uses more information per step?" In fd08 you will recompute this same series as a single vectorized NumPy expression, which makes it perhaps fifty times faster and not one digit more accurate: vectorization changes the constant, not the rate. In fd08 you will estimate $\pi$ by Monte Carlo, whose error decays like $N^{-1/2}$: slower still, and yet the method of choice for the high-dimensional integrals of dc01 and the GHK simulator, where no deterministic rule is available at all. Choosing an algorithm means choosing a convergence rate, and that choice dominates every constant factor you can subsequently optimize.