Tilley's Bundling Algorithm
This Demonstration shows Tilley's bundling algorithm  that uses Monte Carlo simulation to approximate the value of an American option on a single underlying asset. The graph shows the simulated geometric Brownian motion (GBM) paths (gray lines), the "transition zone" (dashed lines), and the "sharp boundary" (red dots), which is the algorithm's approximation for the optimal exercise boundary (black line). Whenever a GBM path falls below the "sharp boundary", the early-exercise is considered optimal and the option is instantly exercised. The early-exercise events at each time step are illustrated by the abrupt cut of those GBM paths that fall bellow the red dots. For each GMB path, the intrinsic value of the option at the time of exercise is discounted, and Monte Carlo integration helps to approximate the American put at .[more]
Use the controls to set the option's parameters. Observe how the selected number of time steps, bundles, and paths per bundle affect the approximation for the option's value and the early-exercise boundary location. The "seed" control generates new pseudorandom GBM paths.[less]
Tilley's bundling algorithm  is a Monte Carlo simulation approach  for pricing American options. It generates pseudorandom paths that follow GBM and estimates the option’s continuation value by using backwards induction and a bundling technique. At one time step prior to maturity, paths whose stock prices are similar are grouped together to obtain an estimate of the one-period-ahead option value. Proceeding recursively from the option’s expiration date, an optimal exercise policy is obtained. The red dots represent Tilley's "sharp boundary", which is the algorithm's approximation of . The (actual) early-exercise boundary derives from Mathematica's built-in function FinancialDerivative. While the stock price moves above , the early-exercise is not optimal because the option's holding value is greater than its intrinsic value.
Tilley's "sharp boundary" lies within a "transition zone", which is determined by the dashed lines in the graph: • between the zone's upper limit and the "sharp boundary", the possibility of early-exercise is significantly low, • between the "sharp boundary" and the zone's lower limit, the possibility of early-exercise is significantly high, • outside the "transition zone", the early-exercise possibilities are considered 0% and 100%, respectively.
The "alpha" coefficient derives from , where is the number of paths per bundle, and is the total number of paths. • indicates that the simulation algorithm uses a single bundle that includes all paths, • indicates that every single path is treated as a separate bundle, • indicates that the number of bundles equals the number of paths per bundle. Tilley demonstrated that if , the algorithm still provides good approximations for American options, even if the simulation algorithm uses the upper limit of the "transition zone" as the early-exercise boundary.
 J. Tilley, "Valuing American Options in a Path Simulation Model," Transactions of the Society of Actuaries, 45, 1993 pp. 83–104.
 M. Fu, S. Laprise, D. Madan, Y. Su, and R. Wu, "Pricing American Options: A Comparison of Monte Carlo Simulation Approaches," Journal of Computational Finance, 4, 2001 pp. 39–88.