A Coin-Flip Tree That Becomes Black-Scholes

Take an at-the-money call with $S_0 = K = 100$, $\sigma = 20\%$, $r = 5\%$ and one year to expiry. Chop the year into $n$ coin flips, and let each flip multiply the stock by $u$ or by $d$. With three flips there are $2^3 = 8$ paths, and you could price the call by listing all eight. A year of trading days is 252 flips, which is $2^{252} \approx 7.2 \times 10^{75}$ paths. Checking a trillion paths a second, that list would take about $2 \times 10^{56}$ years.

The way out is that the order of the flips doesn't change the price. Up then down lands at $S_0 ud$, and so does down then up. A tree where different paths meet like this is called recombining. After $n$ flips the stock can only be at $S_0 u^k d^{n-k}$ for $k = 0, 1, \dots, n$ ups, so there are $n + 1$ end prices where there were $2^n$ end paths.

With $u = 1.1224$ and $d = 1/u = 0.8909$ (the section after next explains where these come from), the three-flip tree has four final prices: 70.72, 89.09, 112.24 and 141.40. The paths HHT, HTH and THH all end at 112.24. The whole lattice has $1 + 2 + 3 + 4 = 10$ nodes. At 252 flips it has $253 \cdot 254 / 2 = 32{,}131$ nodes, which a laptop gets through in well under a millisecond.

Folding only helps if the thing you're pricing also forgets the path. A European call does: its payoff $(S_n - K)^+$ looks at the final price and nothing else. The next section shows that its value at every earlier time forgets the path as well.