Implementing a 100-Step Binomial Tree With Backward Induction

Separate model inputs, terminal payoffs, backward induction, and verification. In this exercise, a 100-step Cox–Ross–Rubinstein tree prices an American put at about

11.00

for

S_0=95

K=100

T=1

r=3\%

, and

\sigma=25\%

. At each node, compare the value of exercising immediately with the value of continuing.

Map a node to the two entries it needs

Set $\Delta t=T/100$ , $u=e^{\sigma\sqrt{\Delta t}}$ , $d=1/u$ , $R=e^{r\Delta t}$ , and $p=(R-d)/(u-d)$ . Order each vector from zero up moves to all up moves. From node $(i,j)$ , the down successor is entry $j$ and the up successor is entry $j+1$ of the next vector. The discounted continuation value is $C_{i,j}=R^{-1}[(1-p)V_{i+1,j}+pV_{i+1,j+1}]$ . The American put uses $V_{i,j}=\max(K-S_{i,j},C_{i,j})$ , with the positive part of $K-S_{100,j}$ at maturity. The continuation value is nonnegative under the assumed probabilities.

Think of the rollback array as belonging to a single time level. At maturity it has 101 entries indexed by the number of up moves. One rollback creates 100 parent values. The first parent uses entries zero and one, the next uses one and two, and so on. At an American node, compare the discounted continuation with intrinsic value calculated using the parent stock price. Doing that comparison at a child's spot tests the wrong exercise decision. As a quick test, the American price should be at least its immediate exercise value and at least the European value computed on the same grid.

Check early exercise against the European value

Here

\Delta t=0.01

years and

p\approx0.49975

. The tree produces an American value of about

10.9965

. The European version is cheaper, with a continuous-model benchmark of

10.6087

. The current exercise value is

100-95=5

, so the initial node chooses continuation. For a local early-exercise check, inspect a low spot near maturity. There the immediate receipt of cash can be worth more than waiting a step for a nearly certain payoff.

Implement the 100-step rollback

import numpy as np

def put_tree(spot, strike, maturity, rate, vol, steps=100, *, american=True):
    dt = maturity / steps
    up = np.exp(vol * np.sqrt(dt))
    down = 1 / up
    gross = np.exp(rate * dt)
    prob_up = (gross - down) / (up - down)
    if not 0 < prob_up < 1:
        raise ValueError("No-arbitrage condition failed for this time step.")

    def spot_layer(level):
        ups = np.arange(level + 1)
        return spot * up**ups * down**(level - ups)

    values = np.maximum(strike - spot_layer(steps), 0.0)
    for level in range(steps - 1, -1, -1):
        continuation = ((1 - prob_up) * values[:-1] + prob_up * values[1:]) / gross
        values = np.maximum(strike - spot_layer(level), continuation) if american else continuation
    return float(values[0])

print(put_tree(95, 100, 1, 0.03, 0.25))
print(put_tree(95, 100, 1, 0.03, 0.25, american=False))

The options pricer gives you a continuous-model European benchmark. Compare it with your European tree on the same inputs.

Implementing a 100-Step Binomial Tree With Backward Induction

Map a node to the two entries it needs

Check early exercise against the European value

Implement the 100-step rollback

Watch a binomial tree approach the Black–Scholes price

References and next steps