Binomial trees, backward induction and early exercise

One binomial step prices a one-period option. Repeating it backwards from expiry prices anything, including options with an early-exercise decision that no closed form handles. Trees survive in production for exactly that reason.

Equation 3.1

The Cox–Ross–Rubinstein parameterisation

Choosing $d = 1/u$ makes the tree recombine, so $n$ steps give $n+1$ terminal nodes rather than $2^n$ paths.

u = e^{\sigma\sqrt{\Delta t}}, \qquad d = \frac{1}{u}, \qquad q = \frac{e^{r\Delta t} - d}{u - d}

$\sigma\sqrt{\Delta t}$: One step’s worth of volatility — the same $\sqrt{t}$ scaling as everywhere else.
$q$: Risk-neutral probability, chosen so the discounted stock is a martingale.

Why recombination matters so much. Up-then-down and down-then-up land on the same price when $d = 1/u$ , so the tree is a lattice rather than a branching tree. That turns an exponential number of paths into a quadratic number of nodes: a hundred steps is $5{,}151$ nodes instead of $10^{30}$ paths. Every practical lattice method depends on this, and it is also why path-dependent payoffs — where up-then-down and down-then-up are genuinely different — need a different technique.

Figure 3.2 · Up then down meets down then up. With u = 1.2 and d = 1/u, the up–down and down–up paths meet at 100. Work from the three right-hand payoffs back to the two middle nodes, then back to today. Recombination saves repeated calculations.

Derivation 3.3

Backward induction with early exercise

Start at expiry, where the value is the payoff, and work back one layer at a time.

$V_T = \text{payoff}(S_T)$
The terminal layer is known exactly.
$V_{\text{cont}} = e^{-r\Delta t}\big[qV_u + (1-q)V_d\big]$
Discounted risk-neutral expectation of the layer above.
$V = \max\big(V_{\text{cont}},\ \text{payoff}(S)\big)$
The American step. Drop it and you have priced a European.

V_0 \text{ after } n \text{ layers}

Example 3.4

A two-step American put

A stock is at $\$100$ , $u = 1.2$ , $d = 1/1.2$ , rates zero, two steps. Price the $\$100$ American put.

Show the worked solutionHide the worked solution

Worked solution

Formula $q = \frac{1 - d}{u - d}, \qquad V = \max(V_{\text{cont}},\ K - S)$
Substitute $d = 0.8333,\ q = \frac{0.1667}{0.3667} = 0.4545$
Solve $\text{Terminal: } S = 144, 100, 69.44 \Rightarrow V = 0,\ 0,\ 30.56$
$\text{Node } S = 83.33:\ V_{\text{cont}} = 0.5455 \times 30.56 = 16.67$
$\text{intrinsic} = 100 - 83.33 = 16.67 \Rightarrow \text{equal, either way}$
$\text{Node } S = 120:\ V_{\text{cont}} = 0$
$V_0 = 0.5455 \times 16.67 = 9.09$
Answer $\$9.09$

Sanity check. With zero rates the European put is worth the same here, because the continuation value never falls below intrinsic. Early exercise starts to bite once rates are positive, since then holding the strike earns interest.

Binomial trees, backward induction and early exercise

After this lesson you should be able to

The Cox–Ross–Rubinstein parameterisation

Backward induction with early exercise

A two-step American put

The rest of this lesson is in Premium