The binomial lattice, from scratch

Every payoff so far has been one fixed sequence of arithmetic, recorded once and replayed for as many random paths as you like. What happens when a contract needs to decide, at every single step, whether exercising right now beats waiting — a decision whose answer can change from one market state to the next?

The whole story

Did you know?

BinomialTree's own doc comment says it plainly: "deliberately not on the adjoint tape... a plain double, O(n²) companion." Every earlier module recorded a fixed sequence of ADouble operations once and replayed it under different markets. Backward induction can't do that — at every node it computes max(continuation, exercise), and which branch wins depends on the very values the tape would need to have already computed to know what to record. A recorded tape assumes the same operations run every time; this algorithm's shape depends on its own numbers.

Two ways to slice the same tree

BinomialTree.Method.CRR (Cox-Ross-Rubinstein) is the textbook parameterization — up-factor u = e^{σ√dt}, down-factor 1/u:

case CRR -> {
  double u = Math.exp(vol * Math.sqrt(dt));
  return new Lattice(u, 1.0 / u, (growth - 1.0 / u) / (u - 1.0 / u), disc);
}

Method.LEISEN_REIMER inverts Black-Scholes' own d1/d2 through a Peizer-Pratt approximation instead, at the cost of needing an odd step count (BinomialTree's constructor bumps an even one up by one). Pricing the same European call (GeneralizedBsm's closed form: 10.450584) at six step counts with both:

steps	CRR error	Leisen-Reimer error
10	−1.97×10⁻¹	−2.57×10⁻³
50	−3.99×10⁻²	−1.32×10⁻⁴
250	−7.99×10⁻³	−5.60×10⁻⁶
500	−4.00×10⁻³	−1.41×10⁻⁶

CRR's error roughly halves every doubling of steps (O(1/n)) and oscillates in sign along the way (+7.04×10⁻² at 25 steps, sandwiched between two negative rows) — the textbook even/odd wobble. Leisen-Reimer's error roughly quarters every doubling (O(1/n²)) and never changes sign: faster convergence, bought by that odd-step-count, vanilla-only restriction.

Backward induction, and the line that breaks the tape

induct() walks backward from the terminal payoff, and every intermediate node runs the same two lines:

double cont = l.disc() * (l.p() * v[j + 1] + (1.0 - l.p()) * v[j]);
if (exercisable) {
  cont = Math.max(cont, early.exerciseValue(nodeSpot(l, i, j)));
}
next[j] = cont;

That Math.max is plain-double arithmetic, not ADouble.max — there's no tape here to record onto. Pricing an American put (S=K=40, σ=20%, T=1y, r=6%) against its European twin, both on the same 2,000-step CRR tree:

schedule	price
European	2.0660
American	2.3194

The 0.2534 gap is the early-exercise premium — value that comes purely from the option to exercise early, which a replayed Monte-Carlo tape has no mechanism to add, because nothing about "stop here if it's better" is a fixed sequence of arithmetic. Whether it's worth anything at all depends on the contract: a no-dividend American call on this same tree prices exactly equal to its European twin (10.446585 both ways, to six decimals) — the textbook result that early exercise is never optimal without a dividend to capture — while adding a 4% dividend yield makes the American call worth 0.0156 more. A Bermudan schedule (exercisable every 50 of those 2,000 steps) prices the put at 2.3126: strictly between the European and American bookends, exactly where you'd expect a "sometimes" to sit between a "never" and an "always."

Did you know?

LatticeGreeks' own doc comment calls itself "the tree engine's answer to the adjoint sweep." Delta and gamma are read straight off the tree's own first two backward-induction slices — nodes the algorithm was already computing on the way to the price, so they cost nothing extra. Vega, rho, and theta get no such shortcut: each one rebuilds the entire O(n²) tree with one parameter bumped up and down, exactly the bump-and-revalue technique 2.1 built a whole page around adjoint AD making unnecessary — alive and well here, because there's no tape to differentiate instead.

Tree Greeks: free, and not-so-free

An 800-step CRR call against the closed form, same market:

Greek	tree	closed form	cost
delta	0.6368	0.6368	free — slice 1
gamma	0.01878	0.01876	free — slice 2
vega	37.512	37.524	2 extra tree rebuilds

Delta and gamma agree with Black-Scholes to four decimals for free; vega is close but visibly noisier, the way a finite-difference estimate always is next to an adjoint one.

Try it yourself

Leisen-Reimer's error roughly quarters every time the step count doubles. Using the 250 → 500 step in the table above (−5.60×10⁻⁶ → −1.41×10⁻⁶, a 4× drop), predict the error at 1,000 steps before running it — you should land somewhere near −3.5×10⁻⁷.

▶️ Run it

mvn -o -q -pl nablatensor-examples exec:java \
  -Dexec.mainClass=com.nablatensor.examples.LatticeConvergenceShowcase

Pure CPU, O(n²) double arithmetic — no engine string to pick, because there's no tape to compile a kernel from.

⚠️ What this doesn't do

Leisen-Reimer only prices vanillas (priceVanilla, not the general price(payoff, schedule) a Bermudan or custom payoff needs) — CRR or Jarrow-Rudd are the only choices once the payoff or schedule gets more interesting than a plain call or put. This page also doesn't derive Bermudan pricing beyond the one number above, or explain how a Monte-Carlo engine that can't look ahead the way a tree does still manages to price early exercise at all — Longstaff-Schwartz regression, and exactly how honest a gap NablaTensor's current implementation of it is, is next.

What's next

→ Deeper: Binomial trees: convergence, early exercise, and tree Greeks has Jarrow-Rudd, the ConvergenceTable Richardson extrapolation this page skipped, and the full pinned-test tolerances. → Next: Bermudan options and the honest gap — where a Monte-Carlo tape gets its own, much more approximate, answer to the same early-exercise question.