Lattices — convergence-lab

Binomial trees

A binomial tree discretises the risk-neutral dynamics of the stock into a recombining lattice of nodes. At each step the stock either moves up by a factor u or down by d, with the up-move probability set so the tree matches the right moments of the log-normal distribution. Working backwards from the terminal payoff, one layer at a time, gives the value at the root — which is the price.

The tree is recombining: an up-then-down move lands on the same node as a down-then-up move. That keeps the layer size at n+1 nodes for n steps, instead of 2^n. The price of that simplicity is that the three binomial parameterisations below differ only in how they choose u, d, and p — and those choices are visible in the convergence, not just the price.

The point of distinguishing them. All three binomials converge to Black–Scholes at first order. What differs is the size of the oscillatory error term and how it depends on where the strike sits relative to the terminal nodes. A case that measures convergence cleanly for one parameterisation can report a misleading order for another, even though the underlying scheme is the same.

Cox–Ross–Rubinstein

The standard choice. Up and down are symmetric inverses, u = 1/d, and the up-probability is set so the tree matches the first two moments of the risk-neutral distribution:

\[u = \exp(\sigma \sqrt{\Delta t}) \qquad d = 1/u \qquad p = \frac{e^{(r-q)\Delta t} - d}{u - d}\]

The symmetry is what makes CRR the textbook default, but it also makes the tree sensitive to strike placement. When the spot equals the strike and the step count is even, S₀ = K lands exactly on the central terminal node. The oscillatory error term that a vanilla payoff normally excites vanishes, and the underlying O(1/n) convergence is exposed cleanly. The test suite uses exactly this configuration — S₀ = K, even steps — for the first-order check, because it is the case where the rate is honest rather than contaminated by node alignment.

Measured order: 1.000, on CRR with S₀ = K across {250, 500, 1000, 2000} steps. The test explicitly notes that Jarrow–Rudd on the same sizes gives an erratic observed order (0.5 to 3.2), not because JR is wrong, but because the strike falls between its drift-shifted nodes and the oscillatory term dominates. Measuring convergence on JR here would report a property of the node alignment, not of the scheme.

Jarrow–Rudd

Equal probabilities, p = 1/2. The drift is absorbed into the node spacing instead of into the probability:

\[u = \exp((r - q - \tfrac{1}{2}\sigma^2)\Delta t + \sigma\sqrt{\Delta t}) \qquad d = \exp((r - q - \tfrac{1}{2}\sigma^2)\Delta t - \sigma\sqrt{\Delta t})\]

This choice makes the tree’s node centres track the forward mean, which is appealing when the strike is far from spot. It also makes the convergence measurement less clean for an at-the-money vanilla, because the strike no longer lands on a node at even steps and the oscillatory error term comes back. The implementation keeps JR available because it is a legitimate parameterisation; the test suite does not use it for the order check, and says so.

Tian

Matches the first three moments of the log-normal distribution exactly, which buys a smaller truncation error at a given step count:

\[v = e^{\sigma^2\Delta t} \qquad u = \tfrac{1}{2} e^{(r-q)\Delta t} v\,(v + 1 + \sqrt{v^2 + 2v - 3}) \qquad d = \tfrac{1}{2} e^{(r-q)\Delta t} v\,(v + 1 - \sqrt{v^2 + 2v - 3})\]

Tian is the most accurate of the three binomials at a fixed n, but it is still first order. The implementation includes it so the tree module covers the moment-matching spectrum from two moments (CRR) to three (Tian), and so the test that all three binomials agree at 4000 steps has something to agree with.

Boyle trinomial

The trinomial tree adds a middle branch. That extra branch is a free parameter, and the usual choice dx = σ√(3Δt) keeps all three transition probabilities positive while giving the same O(1/n) convergence with a smaller constant than the binomial:

\[dx = \sigma\sqrt{3\Delta t} \qquad p_{\uparrow} = \tfrac{1}{2}\big((\sigma^2\Delta t + \nu^2\Delta t^2)/dx^2 + \nu\Delta t/dx\big) \qquad p_{\downarrow} = \tfrac{1}{2}\big((\sigma^2\Delta t + \nu^2\Delta t^2)/dx^2 - \nu\Delta t/dx\big)\]

where ν = r - q - σ²/2.

Why a scratch layer. Unlike the binomial, each trinomial node reads its neighbour above and below in the same sweep. If you update the value array in place, you consume a value that was already overwritten earlier in this step and silently return a wrong price. The implementation keeps a second layer and swaps between them, so a mistake of this kind is impossible rather than merely unlikely. The comment in the source says the same thing.

The trinomial is here for the same reason the three binomials are: the tree module is meant to cover the discretisation options that are actually used, and a reader looking at how these methods compare should be able to see them all side by side. The convergence study plots CRR; the demo prices all four.

American exercise

An American option can be exercised at any node, not only at maturity. On a tree that is handled by taking the maximum of the continuation value and the payoff at every node during the backward induction:

value[k] = disc * (p_up * value[k+1] + (1-p_up) * value[k]);
if (opt.exercise == Exercise::American)
    value[k] = std::fmax(value[k], opt.payoff(s));

That is exactly the discrete obstacle problem the PDE formulation solves variationally, and it is why the tree can price an American contract while forward simulation cannot. The test suite checks that an American put exceeds its European counterpart — the early-exercise premium is positive by construction, and the tree reproduces it.

No closed form for the American put. The test main.cpp prices an American put by the tree and compares it against the European put, explicitly noting that no analytic solution exists for the American case — the lattice is the reference, not a cross-check against a formula.

Guards

A binomial tree has one failure mode that a wrong-but-plausible implementation can hide: if the time step is too large for the volatility, the risk-neutral probability leaves [0,1] and the tree would admit arbitrage. The implementation tests for this and raises rather than returning a number:

if (lp.p_up < 0.0 || lp.p_up > 1.0)
    throw std::runtime_error(
        "binomial: risk-neutral probability outside [0,1] - "
        "time step too large for this volatility; "
        "the tree would admit arbitrage");

The test suite exercises this directly — a market with high rate and low volatility and a two-step tree — and checks that an exception is thrown. The point is the same one that runs through the whole library: a scheme that is wrong should say so, not return a price that looks fine.

Convergence

All four tree methods converge to the closed form at first order in the step count. The differences between them show up in the size of the error and in how stable that error is as the strike moves relative to the nodes:

Method	Order	Notes
Binomial CRR	1	`S₀=K`, even steps — strike on a node, oscillation vanishes
Binomial Jarrow–Rudd	1	Drift in nodes, p=½; order measurement sensitive to strike placement
Binomial Tian	1	Matches 3 moments; smallest constant at fixed `n`
Boyle trinomial	1	Extra branch buys a smaller constant; needs scratch layer

The convergence study plots CRR only, because it is the parameterisation whose order is cleanest to measure. The demo prices all four against the closed form and prints the error of each.

Source

Implementation

include/convergence/lattice.hpp — binomial (CRR, Jarrow–Rudd, Tian), Boyle trinomial, American exercise

View on GitHub →

Tests

tests/test_convergence.cpp — first-order check, agreement across parameterisations, American put, bad-step guard