Case study: pricing on a multi-step binomial tree

From one step to $n$ steps

The inputs are those of case study 2.4.6: stock price $S_0 = 100$, strike $K = 100$, $T = 0.5$ years, rate $r = 0.03$ (continuous) and volatility $\sigma = 0.2$, both yearly decimals. A European option can be exercised only at $T$; that is the kind priced so far.

Split $T$ into $n$ steps of length $\Delta t = \frac{T}{n}$ years. Each step is case study 5.2.5's one-period model with $\Delta t$ in place of $T$: the stock is multiplied by $u$ or by $d$.

An up move followed by a down move ends where a down move followed by an up move does, because $ud = 1$. So the tree recombines: after $i$ steps there are only $i + 1$ nodes, not $2^i$. The node with $j$ up moves has the price $S_0u^jd^{i - j} = S_0u^{2j - i}$.

The tree as a random walk

The log of the price, $\ln(S_i/S_0) = \sigma\sqrt{\Delta t}\,(2U - i)$, is a random walk with steps of $\pm\sigma\sqrt{\Delta t}$ (lesson 5.11.1). Under $q$ the number of up moves is $U \sim \operatorname{Bin}(i, q)$, and the price moves from node to node as a Markov chain (lesson 5.11.2).

With $n = 100$, $q = 0.501768$, and lesson 5.11.1's rules give the log price at $T$ a mean of 0.0050 and a variance of 0.0200. Those are case study 5.6.5's $m = (r - \frac{\sigma^2}{2})T$ and $v^2 = \sigma^2T$: the tree has the lognormal model's mean and spread.

Working backwards

At expiry every final node has a known payoff. One step earlier, each node has two successors, and case study 5.2.5's rule prices it from them. Repeat back to today: this is backward induction.

Two steps by hand

With $n = 2$, $\Delta t = 0.25$: $u = 1.105171$, $d = 0.904837$, $q = 0.512599$ and one step discounts by $e^{-0.0075} = 0.992528$.

Two steps give 5.7309, below Black–Scholes 6.3710, where one step gave 7.7512 above it. The middle final node sits exactly at the strike, so only one of the three final prices pays anything.

Replication at every node

Case study 3.3.4's three-state market needed the call itself: the bond and the stock alone could not copy it. On a tree each step has only two states, up and down. Their $2 \times 2$ payoff matrix has rank 2, so the bond and the stock complete each step (lesson 3.3.2).

At each node, solve case study 5.2.5's $2 \times 2$ system for the shares $\Delta$ and the bonds that pay 1 one step later:

The hedge changes from node to node. After an up move the call is sure to pay and behaves like one share less 100 bonds; after a down move it is worthless.

No new money is ever needed. Today's portfolio is worth exactly 11.2643 after an up move and 0 after a down move, the cost of the next node's portfolio. So the tree's price is the cost of copying the call, and by the law of one price (case study 3.3.4) its value.

Closing in on Black–Scholes

tree_price below runs backward induction for any $n$, a whole column of nodes at a time. For the call:

The price closes in on 6.3710 as $n$ grows, from above for odd $n$ and from below for even $n$. The error times $n$ settles near $\pm 1.4$, so the error shrinks like $\frac{1.4}{n}$: ten times the steps, a tenth of the error. It stays under a cent from $n = 141$ on.

Since the number of up moves is $\operatorname{Bin}(n, q)$ (case study 5.2.5), a European price is also one sum:

For $n = 100$ it gives 6.3570, as backward induction did. An American option, below, has no such sum.

Why the price zigzags

The payoff $\max(S - 100, 0)$ has a kink at the strike, and the tree sees it only through its final nodes. With an even $n$ one final node sits exactly at 100 (for $n = 100$, the nodes nearest the strike are 97.21 and 100). With an odd $n$ two nodes straddle it (for $n = 101$, 98.60 and 101.42). So odd and even trees err on opposite sides.

A common fix averages two neighbours: $\frac{1}{2}(6.3570 + 6.3846) = 6.3708$ for $n = 100$ and 101, within 0.0002 of Black–Scholes.

Try it below. Drag the number of steps from 1 to 100 and watch the price swing around 6.3710. Up to 4 steps, each node shows its stock price and the call's value.

The American put

An American option may be exercised at any time up to $T$. At every node its holder compares the payoff from exercising now with the value of holding on, the backward-induction average. The option is worth the larger.

Take the put with strike 100 on the two-step tree. At expiry it pays 18.1269, 0 and 0. After one down move the stock is 90.4837: holding is worth $0.992528 \times 0.487401 \times 18.1269 = 8.7691$, but exercising pays $100 - 90.4837 = 9.5163$. The holder exercises.

So the two-step American put is worth 4.6036, against 4.2421 for the European. With more steps:

The European column closes in on the Black–Scholes put, $6.3710 - 1.4888 = 4.8822$, by put–call parity (case study 3.3.4). The American price creeps up more slowly; 10,000 steps give 5.0098. The right to exercise early is worth about 13 cents, 2.6% of the European price.

For a call on a stock without dividends, the check never chooses early exercise: the American call costs what the European one does. With time $\tau$ left, put–call parity (case study 3.3.4) gives $C = S - Ke^{-r\tau} + P \ge S - Ke^{-r\tau}$ for the European call. For $r > 0$ that is more than the payoff $S - K$, so holding wins.

In the explorer above, choose the put and tick the American box. Nodes where exercising beats holding turn red, all of them low in the tree.

Where to exercise

At each time there is a critical price: below it, exercising beats holding. A low price means a large payoff now and little time for the stock to climb back.

On the 1,000-step tree the boundary lies between the highest node where exercise pays and the next node up. Three months in, that is between 84.37 and 85.13; with under two days left, between 96.49 and 97.35. Today it is about 81 (by the finer tree of the figure): the stock must fall about 19% first.

Longer expiries

The longer the put runs, the more early exercise is worth. A European put gains value with its expiry at first, then loses it: $K$ received far in the future is worth little today. An American holder can take $K - S$ whenever it suits.

The American price keeps rising with $T$, ever more slowly. Case study 6.2.4 values a put that never expires and compares it with this tree.

import math

# The call and put of case study 2.4.6: S = 100, K = 100, T = 0.5, r = 0.03, sigma = 0.2
ARGS = (100, 100, 0.5, 0.03, 0.2)


def expect_value_error(call, why):
    try:
        call()
    except ValueError:
        return
    raise AssertionError(f"expected ValueError: {why}")


def test_one_step():
    """One step prices the call at 7.7512, as in case study 5.2.5"""
    expect_close(binomial_price(*ARGS, 1), 7.751159552620581, what="binomial_price(..., n=1)", rel=1e-9)


def test_two_steps():
    """Two steps price the call at 5.7309"""
    expect_close(binomial_price(*ARGS, 2), 5.730919862093777, what="binomial_price(..., n=2)", rel=1e-9)


def test_hundred_steps():
    """100 steps price the call at 6.3570, about 1.4 cents below Black–Scholes 6.3710"""
    expect_close(binomial_price(*ARGS, 100), 6.356980314193379, what="binomial_price(..., n=100)", rel=1e-9)


def test_put_call_parity():
    """With 50 steps, the European call minus the European put is S − Ke^(−rT) = 1.4888"""
    c = binomial_price(*ARGS, 50, kind="call")
    p = binomial_price(*ARGS, 50, kind="put")
    expect_close(p, 4.85416311717389, what="European put, n=50", rel=1e-9)
    expect_close(c - p, 100 - 100 * math.exp(-0.015), what="call minus put", rel=1e-9)


def test_american_put():
    """The American put is worth 4.6036 with 2 steps and 5.0020 with 100"""
    expect_close(binomial_price(*ARGS, 2, kind="put", american=True), 4.603575924794417, what="American put, n=2", rel=1e-9)
    expect_close(binomial_price(*ARGS, 100, kind="put", american=True), 5.00195775821218, what="American put, n=100", rel=1e-9)


def test_american_call():
    """An American call on a stock without dividends costs the same as the European call"""
    expect_close(binomial_price(*ARGS, 100, kind="call", american=True), 6.356980314193379, what="American call, n=100", rel=1e-9)


def test_deep_in_the_money():
    """An American put with the stock at 70 is worth exactly its payoff, 30"""
    expect_close(binomial_price(70, 100, 0.5, 0.03, 0.2, 100, kind="put", american=True), 30.0, what="American put at S=70", rel=1e-12)


def test_other_inputs():
    """A one-year put with S = 50, K = 55, r = 5% and σ = 30%, 200 steps: 7.3305 European, 7.8127 American"""
    expect_close(binomial_price(50, 55, 1.0, 0.05, 0.3, 200, kind="put"), 7.330473104051195, what="European put", rel=1e-9)
    expect_close(binomial_price(50, 55, 1.0, 0.05, 0.3, 200, kind="put", american=True), 7.812666020148489, what="American put", rel=1e-9)


def test_bad_q():
    """σ = 1% and r = 5% with one step of half a year make q = 2.29, so ValueError"""
    expect_value_error(lambda: binomial_price(100, 100, 0.5, 0.05, 0.01, 1), "q would be 2.2883, not a probability")


def test_zero_volatility():
    """Zero volatility raises ValueError instead of dividing by zero"""
    expect_value_error(lambda: binomial_price(100, 100, 0.5, 0.03, 0.0, 10), "with sigma = 0, u = d = 1")


def test_bad_inputs():
    """n = 0, n = 2.5, a negative stock price or kind="straddle" raise ValueError"""
    expect_value_error(lambda: binomial_price(*ARGS, 0), "n = 0 is not a tree")
    expect_value_error(lambda: binomial_price(*ARGS, 2.5), "n = 2.5 is not a whole number of steps")
    expect_value_error(lambda: binomial_price(-100, 100, 0.5, 0.03, 0.2, 10), "a stock price must be positive")
    expect_value_error(lambda: binomial_price(*ARGS, 10, kind="straddle"), "kind must be call or put")