Binomial trees

A stock that can only go up or down

Black–Scholes is a formula; a binomial tree is a procedure, and it can price things the formula cannot. Cut the time to expiry into small steps. In each step the stock moves up by a factor u or down by a factor d, nothing else. After n steps there are n + 1 possible prices. The payoffs are known at expiry, and each earlier node is worth the discounted average of the two nodes it leads to, so you can fill the tree backwards to the present.

# One step: a stock at 100 goes to 110 or 90. What is a call with strike 100 worth?
import math

spot, strike, rate, dt = 100, 100, 0.05, 1.0
u, d = 1.10, 0.90
p = (math.exp(rate * dt) - d) / (u - d)             # the probability that makes the stock grow at the rate
up_value, down_value = max(spot * u - strike, 0), max(spot * d - strike, 0)
price = math.exp(-rate * dt) * (p * up_value + (1 - p) * down_value)
print(round(p, 4), round(up_value, 4), down_value)   # 0.7564 10.0 0
print(round(price, 4))                               # 7.1947

The probability is not a forecast

The number p is chosen so that the stock, on average, grows at the risk-free rate: p * u + (1 - p) * d = exp(rate * dt), which gives p = (exp(rate * dt) - d) / (u - d). It is the risk-neutral probability: a device that makes a replicating portfolio worth its discounted expectation, not a belief about where the stock will go. To match the observed volatility, the Cox–Ross–Rubinstein (CRR) tree uses u = exp(sigma * sqrt(dt)) and d = 1 / u, so an up move followed by a down move returns to the same price and the tree recombines: n steps need only n + 1 nodes at the end.

# The CRR parameters and the prices at expiry of a 3-step tree
import math

def crr_parameters(rate, sigma, t, steps):
    dt = t / steps
    u = math.exp(sigma * math.sqrt(dt))
    d = 1 / u
    p = (math.exp(rate * dt) - d) / (u - d)
    return u, d, p

def terminal_prices(spot, u, d, steps):
    return [spot * u ** j * d ** (steps - j) for j in range(steps + 1)]

u, d, p = crr_parameters(0.05, 0.2, 1, 3)
print(round(u, 4), round(d, 4), round(p, 4))                     # 1.1224 0.8909 0.5438
print([round(price, 2) for price in terminal_prices(100, u, d, 3)])

Working backwards

At expiry each node is just the payoff, max(S - K, 0) for a call. One column earlier, each value is exp(-rate * dt) * (p * value_up + (1 - p) * value_down), and the column shrinks by one node. After n such sweeps a single value remains, the price today. In Python a column is a list, and one sweep is a list comprehension over neighbouring pairs. As the number of steps grows the price converges to the Black–Scholes price, and the tree reproduces what the formula says.

# The tree price of a European call approaches the Black-Scholes price as steps grow
import math

def norm_cdf(x):
    return 0.5 * (1 + math.erf(x / math.sqrt(2)))

def bs_call(spot, strike, rate, sigma, t):
    d1 = (math.log(spot / strike) + (rate + 0.5 * sigma ** 2) * t) / (sigma * math.sqrt(t))
    return spot * norm_cdf(d1) - strike * math.exp(-rate * t) * norm_cdf(d1 - sigma * math.sqrt(t))

def european_call_tree(spot, strike, rate, sigma, t, steps):
    dt = t / steps
    u = math.exp(sigma * math.sqrt(dt))
    d = 1 / u
    p = (math.exp(rate * dt) - d) / (u - d)
    disc = math.exp(-rate * dt)
    values = [max(spot * u ** j * d ** (steps - j) - strike, 0) for j in range(steps + 1)]
    for _ in range(steps):
        values = [disc * (p * values[j + 1] + (1 - p) * values[j]) for j in range(len(values) - 1)]
    return values[0]

print("Black-Scholes", round(bs_call(100, 100, 0.05, 0.2, 1), 4))
for steps in (1, 5, 25, 100, 400):
    print(steps, round(european_call_tree(100, 100, 0.05, 0.2, 1, steps), 4))

Early exercise

The real strength of the tree is the option the formula cannot price: an American option may be exercised at any time. At every node the holder compares two values, the discounted expectation of holding and the payoff from exercising now, and takes the larger. This one extra max at each node is the whole change to the algorithm. For a call on a stock without dividends early exercise never pays, but for a put it can: a deep in-the-money put is worth more as cash today, so the American put costs more than the European one.

# An American put against a European put: the early-exercise premium
import math

def tree(spot, strike, rate, sigma, t, steps, american):
    dt = t / steps
    u = math.exp(sigma * math.sqrt(dt))
    d = 1 / u
    p = (math.exp(rate * dt) - d) / (u - d)
    disc = math.exp(-rate * dt)
    values = [max(strike - spot * u ** j * d ** (steps - j), 0) for j in range(steps + 1)]
    for i in range(steps - 1, -1, -1):
        values = [disc * (p * values[j + 1] + (1 - p) * values[j]) for j in range(i + 1)]
        if american:
            values = [max(values[j], strike - spot * u ** j * d ** (i - j)) for j in range(i + 1)]
    return values[0]

for spot in (80, 100, 120):
    european = tree(spot, 100, 0.05, 0.2, 1, 200, False)
    american = tree(spot, 100, 0.05, 0.2, 1, 200, True)
    print(spot, round(european, 4), round(american, 4), "premium", round(american - european, 4))

• Each step the stock goes up by u or down by d; the CRR choice u = exp(sigma * sqrt(dt)), d = 1 / u makes the tree recombine, so n steps have n + 1 end nodes.
• Price backwards: payoffs at expiry, then exp(-rate * dt) * (p * up + (1 - p) * down) per node; p is the risk-neutral probability, not a forecast.
• Many steps converge to Black–Scholes; an American option adds one max(continuation, exercise) per node, which is why trees exist.

Next up: finite-difference methods, pricing by solving the option's partial differential equation on a grid.

Lab · what's graded

• Set the up and down moves with crr_parameters25 pts
• List the prices at expiry with terminal_prices25 pts
• Work backwards through the tree with european_call_tree25 pts
• Allow early exercise with american_put_tree25 pts