Option Pricing I: Binomial Trees
Price European and American options with a Cox-Ross-Rubinstein tree, check every result against put-call parity and no-arbitrage bounds, and watch the tree converge to Black-Scholes.
A contract whose value depends on a price you do not know yet
An option is a contract that gives its holder a right but not an obligation. A call option gives the right to buy an asset (the underlying, here a stock) at a fixed price, the strike K, on or before a fixed date, the expiry T. A put gives the right to sell at the strike. If the stock ends at S_T, a call pays max(S_T - K, 0) at expiry: you exercise only if buying at K beats the market price. A put pays max(K - S_T, 0). A European option can be exercised only at expiry; an American option can be exercised at any time up to expiry.
The pricing question is: what is a fair price today for a payoff that depends on a future stock price? An obvious answer is "the expected payoff, discounted", and it is wrong in an instructive way, because it depends on a probability that nobody agrees on. The correct answer avoids that probability entirely, and the binomial tree is the cleanest place to see how. It also gives a working pricer for American options, which have no closed-form formula.
This lesson builds the Cox-Ross-Rubinstein (CRR) tree from one step to a thousand, prices European and American calls and puts, and checks every number against relations that must hold regardless of the model. It uses the geometric Brownian motion model of the stock from Returns, Volatility and Risk Metrics. As everywhere in this course, it is engineering education: the parameters are illustrative and nothing here is a view on any real instrument.
One step: price by replication, not by guessing probabilities
Take a stock at 100 today that will be either 110 or 90 in a year, and a call with strike 100 expiring then. It pays 10 if the stock goes up and 0 if it goes down. Cash in a bank account grows at the risk-free rate r = 5% per year, compounded continuously: one unit today becomes exp(0.05), about 1.0513, in a year.
Instead of guessing how likely "up" is, build a portfolio that pays exactly what the call pays, in both outcomes. Hold delta shares and borrow some cash. The shares must make up the difference between the two payoffs, so delta = (10 - 0) / (110 - 90) = 0.5. In the up state half a share is worth 55, so you must owe 45 at expiry to be left with 10; in the down state half a share is worth 45, and repaying 45 leaves 0. Borrowing 45 repayable in a year means receiving 45 / exp(0.05) today. That portfolio, called the replicating portfolio, pays exactly what the call pays, so the call must cost what the portfolio costs. If it cost more, you could sell the call, buy the portfolio and pocket the difference with no risk; that is an arbitrage, a riskless profit, and pricing theory assumes it cannot persist.
#include <algorithm>
#include <cmath>
#include <print>
int main() {
// One period of one year. The stock is 100 today and will be 110 or 90.
const double s0 = 100, s_up = 110, s_down = 90, strike = 100, rate = 0.05;
const double growth = std::exp(rate); // 1 unit of cash today is worth this in a year
const double c_up = std::max(s_up - strike, 0.0); // call payoff if up: 10
const double c_down = std::max(s_down - strike, 0.0); // call payoff if down: 0
// Replication: hold `delta` shares and borrow so that the portfolio pays
// exactly c_up in the up state and c_down in the down state.
const double delta = (c_up - c_down) / (s_up - s_down);
const double debt = delta * s_up - c_up; // repaid at expiry in either state
std::println("shares held: {:.4f}", delta);
std::println("debt at expiry: {:.4f}", debt);
std::println("pays if up: {:.4f}", delta * s_up - debt);
std::println("pays if down: {:.4f}", delta * s_down - debt);
std::println("borrowed today: {:.4f}", debt / growth);
std::println("cost today: {:.4f}", delta * s0 - debt / growth);
// The same number as a discounted expectation under the risk-neutral probability.
const double q = (s0 * growth - s_down) / (s_up - s_down);
std::println("risk-neutral q: {:.4f}", q);
std::println("discounted E_q: {:.4f}", (q * c_up + (1 - q) * c_down) / growth);
// What the price is NOT: the discounted payoff under a guessed real probability.
for (double p_real : {0.5, 0.9}) {
std::println("naive, p = {:.1f}: {:.4f}", p_real,
(p_real * c_up + (1 - p_real) * c_down) / growth);
}
}Press Run to compile and run this example.
shares held: 0.5000
debt at expiry: 45.0000
pays if up: 10.0000
pays if down: 0.0000
borrowed today: 42.8053
cost today: 7.1947
risk-neutral q: 0.7564
discounted E_q: 7.1947
naive, p = 0.5: 4.7561
naive, p = 0.9: 8.5611The price is 7.1947, and no probability of "up" was used. The same number comes out of a formula that looks like an expectation: define q = (S0 * exp(r) - S_down) / (S_up - S_down) and discount the q-weighted payoff. q is called the risk-neutral probability. It is the probability under which the stock is expected to grow exactly at the risk-free rate, and it is a computing device, not a forecast. The last two lines show what goes wrong with a guessed real-world probability: 0.5 gives 4.76 and 0.9 gives 8.56, and neither can be right because the replicating portfolio already pins the price at 7.19.
This is the central idea of derivative pricing: if a payoff can be replicated by trading the underlying and cash, its price is the cost of the replication, which equals the discounted expected payoff under the risk-neutral probability.
Put-call parity: a check that needs no model
Before building trees, here is a relation every European pricer must satisfy. Consider two portfolios on a stock that pays no dividends:
- A: one European call with strike
K, plus cashK * exp(-r * T)(which grows to exactlyKat expiry); - B: one European put with the same strike and expiry, plus one share.
At expiry, if S_T > K, A is worth (S_T - K) + K = S_T and B is worth 0 + S_T. If S_T <= K, A is worth 0 + K and B is worth (K - S_T) + S_T = K. They pay the same in every state, so they cost the same today:
C + K * exp(-r * T) = P + S, or C - P = S - K * exp(-r * T).
That is put-call parity. It assumes nothing about volatility or the distribution of prices, so it is the ideal test for a pricer: compute C and P independently and check that their difference matches. It also gives bounds. Since P >= 0, C >= S - K * exp(-r * T); a call can never be worth more than the share it lets you buy, so C <= S. For the put, max(K * exp(-r * T) - S, 0) <= P <= K * exp(-r * T).
The Cox-Ross-Rubinstein tree
One step with two outcomes is a toy. Split the time to expiry into n steps of length dt = T / n and let the stock move up by a factor u or down by a factor d at every step. Cox, Ross and Rubinstein (1979) chose
u = exp(sigma * sqrt(dt)), d = 1 / u, p = (exp(r * dt) - d) / (u - d).
Each choice has a reason:
u = exp(sigma * sqrt(dt))makes the variance of the log-price over a step approximatelysigma^2 * dt, the same as geometric Brownian motion with volatilitysigma. Asngrows, the tree's distribution oflog(S_T)approaches the normal distribution of that model.d = 1 / umakes the tree recombine: up then down lands on the same price as down then up. Afteristeps there arei + 1distinct prices instead of2^i, which is what makes the method practical.pis the one-step risk-neutral probability from the previous section: the stock's expected growth over a step equals the bank's,p * u + (1 - p) * d = exp(r * dt).
For p to be a probability, 0 < p < 1, which is the same as the no-arbitrage condition d < exp(r * dt) < u. If the bank grew faster than the stock's best case, everyone would short the stock and buy bonds; if the stock's worst case beat the bank, the reverse.
Pricing works backward. At expiry the price after j up-moves out of n is S * u^j * d^(n - j) = S * u^(2j - n), and the option is worth its payoff there. One step earlier, each node is worth the discounted risk-neutral average of its two successors: V = (p * V_up + (1 - p) * V_down) / exp(r * dt). Repeat until one node is left; that is today's price. The work is n + (n - 1) + ... + 1 = n(n + 1) / 2 node updates, O(n^2) time. Each step needs only the previous step's values, and node j reads only positions j and j + 1, so a single array of n + 1 values can be overwritten in place: O(n) memory.
#include <algorithm>
#include <cmath>
#include <print>
#include <vector>
enum class Kind { Call, Put };
double payoff(Kind kind, double spot, double strike) {
return kind == Kind::Call ? std::max(spot - strike, 0.0)
: std::max(strike - spot, 0.0);
}
// European option on a non-dividend stock, Cox-Ross-Rubinstein tree with n steps.
// rate: continuously compounded per year; vol: per year; expiry: in years.
double crr_european(Kind kind, double spot, double strike, double rate, double vol,
double expiry, int n) {
const double dt = expiry / n;
const double u = std::exp(vol * std::sqrt(dt)), d = 1.0 / u;
const double growth = std::exp(rate * dt);
const double p = (growth - d) / (u - d); // risk-neutral probability of "up"
// Leaves: after n steps with j up-moves the price is spot * u^j * d^(n-j).
std::vector<double> v(n + 1);
for (int j = 0; j <= n; ++j)
v[j] = payoff(kind, spot * std::pow(u, 2 * j - n), strike);
// Backward induction, reusing one array: O(n^2) time, O(n) memory.
for (int step = n - 1; step >= 0; --step)
for (int j = 0; j <= step; ++j) v[j] = (p * v[j + 1] + (1 - p) * v[j]) / growth;
return v[0];
}
int main() {
const double s = 100, k = 100, r = 0.05, vol = 0.20, t = 1.0;
const int n = 500;
const double dt = t / n, u = std::exp(vol * std::sqrt(dt));
std::println("n = {}: u = {:.6f}, d = {:.6f}, p = {:.6f}", n, u, 1 / u,
(std::exp(r * dt) - 1 / u) / (u - 1 / u));
double call = crr_european(Kind::Call, s, k, r, vol, t, n);
double put = crr_european(Kind::Put, s, k, r, vol, t, n);
std::println("call: {:.4f}", call);
std::println("put: {:.4f}", put);
// Put-call parity: C - P = S - K * exp(-rT) for European options, no dividends.
std::println("C - P: {:.6f}", call - put);
std::println("S - K e^-rT: {:.6f}", s - k * std::exp(-r * t));
}Press Run to compile and run this example.
n = 500: u = 1.008984, d = 0.991096, p = 0.503354
call: 10.4466
put: 5.5695
C - P: 4.877058
S - K e^-rT: 4.877058With 500 steps, the call is 10.4466 and the put 5.5695, and C - P matches S - K * exp(-r * T) to all six printed digits. Parity holds this precisely in the tree because the tree is itself arbitrage-free: it is not an approximation that gets checked, it is an identity the arithmetic must preserve, so a mismatch beyond rounding means a bug (a wrong discount factor, an off-by-one in the leaf prices, a p computed from the wrong r).
American options: compare holding with exercising at every node
An American option adds one decision at each node: exercise now and receive the payoff, or hold and keep the right. Backward induction handles it with one extra line: the node's value is max(hold, exercise_now).
#include <algorithm>
#include <cmath>
#include <print>
#include <vector>
enum class Kind { Call, Put };
enum class Style { European, American };
double payoff(Kind kind, double spot, double strike) {
return kind == Kind::Call ? std::max(spot - strike, 0.0)
: std::max(strike - spot, 0.0);
}
double crr_price(Kind kind, Style style, double spot, double strike, double rate,
double vol, double expiry, int n) {
const double dt = expiry / n;
const double u = std::exp(vol * std::sqrt(dt)), d = 1.0 / u;
const double growth = std::exp(rate * dt);
const double p = (growth - d) / (u - d);
std::vector<double> v(n + 1);
for (int j = 0; j <= n; ++j)
v[j] = payoff(kind, spot * std::pow(u, 2 * j - n), strike);
for (int step = n - 1; step >= 0; --step) {
for (int j = 0; j <= step; ++j) {
double hold = (p * v[j + 1] + (1 - p) * v[j]) / growth;
if (style == Style::American) {
// The holder may exercise now: take the better of the two.
double exercise = payoff(kind, spot * std::pow(u, 2 * j - step), strike);
hold = std::max(hold, exercise);
}
v[j] = hold;
}
}
return v[0];
}
void compare(const char* label, double s, double k, double r, double vol, double t,
int n) {
std::println("{} (S={}, K={}, r={}, vol={}, T={:.4f}, n={})", label, s, k, r, vol,
t, n);
for (Kind kind : {Kind::Call, Kind::Put}) {
double eu = crr_price(kind, Style::European, s, k, r, vol, t, n);
double am = crr_price(kind, Style::American, s, k, r, vol, t, n);
std::println(" {:<4} European {:>8.4f} American {:>8.4f}",
kind == Kind::Call ? "call" : "put", eu, am);
}
}
int main() {
compare("five-step tree", 50, 50, 0.10, 0.40, 5.0 / 12, 5);
compare("fine tree", 50, 50, 0.10, 0.40, 5.0 / 12, 1000);
compare("deep in the money", 100, 150, 0.05, 0.20, 1.0, 1000);
}Press Run to compile and run this example.
five-step tree (S=50, K=50, r=0.1, vol=0.4, T=0.4167, n=5)
call European 6.3595 American 6.3595
put European 4.3190 American 4.4885
fine tree (S=50, K=50, r=0.1, vol=0.4, T=0.4167, n=1000)
call European 6.1152 American 6.1152
put European 4.0747 American 4.2836
deep in the money (S=100, K=150, r=0.05, vol=0.2, T=1.0000, n=1000)
call European 0.3585 American 0.3585
put European 43.0429 American 50.0000Three results, each with a reason:
- The American put is worth more than the European put (4.4885 against 4.3190 with five steps, 4.2836 against 4.0747 with a thousand). When the stock is low, exercising receives
Know, and cash now earns interest; waiting risks the stock recovering. At some nodes the interest outweighs the remaining optionality, and the right to exercise there has value. - The American call equals the European call on a stock without dividends. Exercising a call early pays
S - K, but holding it is worth at leastS - K * exp(-r * T), which is larger wheneverr > 0. Early exercise throws away interest on the strike and the remaining protection, so it is never optimal (Merton, 1973). With dividends this changes: exercising just before a dividend can be worth it. - Deep in the money, the American put is worth exactly its exercise value. With the stock at 100 and the strike at 150, holding the European put is worth 43.04 because the 150 arrives only in a year; the American holder exercises today and takes 50.
Here is the five-step tree for the first case. Each node shows the stock price (black) and the American put's value; red nodes are the ones where exercising immediately is worth more than holding. The last column is the payoff at expiry. Higher stock prices are drawn higher, so the program flips SVG's downward y-axis.
#include <algorithm>
#include <cmath>
#include <print>
#include <vector>
int main() {
// American put, five steps: S = 50, K = 50, r = 10%, vol = 40%, T = 5 months.
const double spot = 50, strike = 50, rate = 0.10, vol = 0.40, expiry = 5.0 / 12;
const int n = 5;
const double dt = expiry / n, u = std::exp(vol * std::sqrt(dt)), d = 1 / u;
const double growth = std::exp(rate * dt), p = (growth - d) / (u - d);
auto price = [&](int step, int j) { return spot * std::pow(u, 2 * j - step); };
// value[step][j] and whether exercising there beats holding.
std::vector<std::vector<double>> value(n + 1);
std::vector<std::vector<bool>> exercise(n + 1);
for (int j = 0; j <= n; ++j) {
value[n].push_back(std::max(strike - price(n, j), 0.0));
exercise[n].push_back(false); // at expiry there is nothing left to compare
}
for (int step = n - 1; step >= 0; --step)
for (int j = 0; j <= step; ++j) {
const auto& next = value[step + 1];
double hold = (p * next[j + 1] + (1 - p) * next[j]) / growth;
double now = std::max(strike - price(step, j), 0.0);
value[step].push_back(std::max(hold, now));
exercise[step].push_back(now > hold);
}
// Higher stock prices are drawn higher: SVG's y axis points down, so subtract.
auto x = [](int step) { return 30.0 + 72.0 * step; };
auto y = [](int step, int j) { return 120.0 - 19.0 * (2 * j - step); };
std::println(R"(<svg viewBox="0 0 420 240" font-size="8" fill="#1f2937">)");
for (int step = 0; step < n; ++step)
for (int j = 0; j <= step; ++j)
for (int up = 0; up <= 1; ++up)
std::println(R"(<line x1="{}" y1="{}" x2="{}" y2="{}" )"
R"(stroke="#9ca3af"/>)",
x(step), y(step, j), x(step + 1), y(step + 1, j + up));
for (int step = 0; step <= n; ++step)
for (int j = 0; j <= step; ++j) {
const char* color = exercise[step][j] ? "#dc2626" : "#2563eb";
std::println(R"(<circle cx="{}" cy="{}" r="3" fill="{}"/>)", x(step),
y(step, j), color);
std::println(R"(<text x="{}" y="{}">{:.2f}</text>)", x(step) + 4,
y(step, j) - 4, price(step, j));
std::println(R"(<text x="{}" y="{}" fill="{}">{:.2f}</text>)", x(step) + 4,
y(step, j) + 9, color, value[step][j]);
}
std::println(R"(<text x="10" y="232">stock price</text>)");
std::println(R"(<text x="80" y="232" fill="#2563eb">put value, hold</text>)");
std::println(R"(<text x="170" y="232" fill="#dc2626">)"
R"(put value, exercise now</text>)");
std::println("</svg>");
}Press Run to compile and run this example.
The red nodes lie along the bottom of the tree, at stock prices of 35.36, 39.69 and 31.50: when the put is far enough in the money, there is an early-exercise boundary below which holding is a mistake. At the root, the put is worth 4.49 against 4.32 for the European version, and the difference comes entirely from those three nodes and their effect on the nodes before them.
Convergence: how many steps are enough
The tree is a discretization, so it has an error that shrinks as n grows. For a European call the limit is the Black-Scholes price, which the next lesson derives and implements; here we borrow its formula as a reference. For S = K = 100, r = 5%, sigma = 20%, T = 1 year, it gives 10.4506 (checked independently by numerical integration of the lognormal payoff, which gives the same value to ten digits).
#include <algorithm>
#include <cmath>
#include <print>
#include <vector>
long long g_node_updates = 0; // counts the work of backward induction
// European call, Cox-Ross-Rubinstein tree with n steps.
double crr_call(double spot, double strike, double rate, double vol, double expiry,
int n) {
const double dt = expiry / n;
const double u = std::exp(vol * std::sqrt(dt)), d = 1.0 / u;
const double growth = std::exp(rate * dt);
const double p = (growth - d) / (u - d);
std::vector<double> v(n + 1);
for (int j = 0; j <= n; ++j)
v[j] = std::max(spot * std::pow(u, 2 * j - n) - strike, 0.0);
for (int step = n - 1; step >= 0; --step)
for (int j = 0; j <= step; ++j) {
v[j] = (p * v[j + 1] + (1 - p) * v[j]) / growth;
++g_node_updates;
}
return v[0];
}
double norm_cdf(double x) { return 0.5 * std::erfc(-x / std::sqrt(2.0)); }
// Black-Scholes call price: the limit of the tree as n grows (lesson 9).
double bs_call(double s, double k, double r, double vol, double t) {
double d1 = (std::log(s / k) + (r + 0.5 * vol * vol) * t) / (vol * std::sqrt(t));
double d2 = d1 - vol * std::sqrt(t);
return s * norm_cdf(d1) - k * std::exp(-r * t) * norm_cdf(d2);
}
int main() {
const double s = 100, k = 100, r = 0.05, vol = 0.20, t = 1.0;
const double exact = bs_call(s, k, r, vol, t);
std::println("Black-Scholes: {:.4f}", exact);
std::println("{:>5} {:>8} {:>8} {:>11}", "n", "tree", "error", "updates");
for (int n : {10, 11, 50, 51, 100, 101, 500, 501, 1000, 1001}) {
g_node_updates = 0;
double price = crr_call(s, k, r, vol, t, n);
std::println("{:>5} {:>8.4f} {:>8.4f} {:>11}", n, price, price - exact,
g_node_updates);
}
}Press Run to compile and run this example.
Black-Scholes: 10.4506
n tree error updates
10 10.2534 -0.1972 55
11 10.6112 0.1606 66
50 10.4107 -0.0399 1275
51 10.4850 0.0344 1326
100 10.4306 -0.0200 5050
101 10.4680 0.0174 5151
500 10.4466 -0.0040 125250
501 10.4541 0.0035 125751
1000 10.4486 -0.0020 500500
1001 10.4523 0.0018 501501Three things to read from this table:
- The error shrinks roughly like
1 / n: doublingnfrom 500 to 1000 halves it, from 0.0040 to 0.0020. At that rate, an error below 0.00005 (four correct decimals) needs about 40,000 steps. - The error oscillates. Even
nlands below the true price and oddnabove, for this at-the-money option. The reason is where the strike falls between the leaf prices: with evennthere is a leaf exactly atS = 100 = K, which pays zero, and the payoff kink sits on a node; with oddnit sits between two nodes. The error is therefore not monotone inn, and comparingn = 100withn = 101says little about convergence. - The
updatescolumn isn(n + 1) / 2exactly, the O(n^2) cost: 1000 steps take 500,500 node updates, about 100 times the work of 100 steps, for an error only 10 times smaller.
Because the error alternates in sign, the average of the results for n and n + 1 is much more accurate than either; the "Try it" section asks you to check that.