Multilevel Monte Carlo for Option Pricing

Prices Asian and barrier call options with multilevel Monte Carlo, and measures what the method actually buys you against standard Monte Carlo. The estimators, the experiments behind every figure, and the write-up in report.pdf are all here.

Authors

This was a joint project for MATH-414 Stochastic Simulation at EPFL (autumn semester 2024, Prof. Fabio Nobile).

Giorgio Milani	giorgio.milani@epfl.ch
Philipp Weder	philipp.weder@epfl.ch
Margot Coste-Sarguet	margot.coste-sarguet@epfl.ch

We worked on all of it together — the estimators, the experiments and report.pdf — and contributed equally. The authors are listed in the order used in the report.

What is implemented

• Path simulation — Euler-Maruyama for geometric Brownian motion (mlmc/core/sde.py), compiled with numba.
• Payoffs — Asian (average-price) and barrier (up-and-out) call options (mlmc/core/options.py).
• Estimators (mlmc/core/estimators.py) — standard Monte Carlo, the two-level estimator, and the multilevel estimator, with coarse and fine paths driven by the same Brownian increments.
• Level selection (mlmc/core/helpers.py) — a pilot run fits the bias and variance decay rates, which feed the complexity theorem to choose the number of levels and the samples per level.
• Variance reduction — importance sampling by a drift shift, for high strike prices, where finishing in the money is a rare event.

What we found

• For the Asian option, multilevel Monte Carlo reaches a given accuracy for roughly two orders of magnitude less computational cost than standard Monte Carlo, and the gap widens as the target accuracy tightens.
• For the barrier option, the advantage largely disappears. The payoff is discontinuous, so coupled coarse and fine paths often land on opposite sides of the barrier and their difference shrinks only slowly from level to level. The fitted variance decay rate falls below the cost growth rate, which is exactly the regime in which the theory promises little, and the two cost curves nearly coincide.
• Importance sampling cuts the variance substantially at high strikes, even with an unoptimised choice of dominating distribution. At a strike twice the initial price, standard Monte Carlo sees no payoff at all in 50,000 paths and returns exactly zero, with an estimated variance of zero.

The barrier result is the interesting one: it is a case where the method does not deliver, reported with the reason why rather than left out.

Asian option — cost	Barrier option — cost

Normalized cost against target accuracy, multilevel versus standard Monte Carlo. For the Asian option the multilevel curve pulls away from standard Monte Carlo and tracks the predicted O(eps^-2 |log eps|^2); for the barrier option the two run almost parallel. Both from a pilot run of 50,000 samples, over 6 and 8 levels respectively.

Bias E_l and difference variance V_l by level for the Asian option, against the fitted rates from the pilot run. The decay of V_l is what makes the method pay off.

Variance of the two-level estimator relative to standard Monte Carlo at equal cost, over the number of coarse samples.

Installation

1. Clone the project and navigate to the project directory.
2. Create a new python environment, cf. docs, and activate it.
3. Install the required packages using

   pip install -r requirements.txt
   

4. Install the package using

   pip install .
   

   or using

   pip install --editable .
   

   if you want to edit the project.

To reproduce the exact environment the committed figures were produced in, use requirements-lock.txt instead of requirements.txt.

Running the experiments

Run every command below from the project root. Each experiment is a pair: a script that runs the simulation and writes a CSV under data/, then a plotting script that reads it and writes a PDF under plots/.

All scripts take command line arguments; for help on any of them, call

python scripts/<script>.py --help

The plotting scripts take two extra flags: --usetex to typeset labels with LaTeX, and --png to also write a 150 dpi PNG into docs/figures/.

Standard Monte Carlo convergence (report section IV.A)

Vary the number of samples:

python scripts/nsamp_variation.py
python scripts/plot_nsamp_variation.py

Vary the time step size h:

python scripts/h_variation.py
python scripts/plot_h_variation.py

Two-level estimator (report section IV.B)

python scripts/two_level.py
python scripts/plot_two_level.py

Multilevel estimator, Asian option (report section IV.C)

python scripts/multi_level_asian.py
python scripts/plot_multi_level_asian.py

Note that the default accuracies go down to eps = 1e-5, and the reference run this is compared against is a standard Monte Carlo estimate at the same accuracy. That is the point of the experiment, but it is also why it is expensive: at eps = 1e-5 the reference alone needs about 64 million paths of 320 steps, which is a few hundred gigabytes of memory, and it will be killed on an ordinary machine. The three coarsest accuracies reproduce the shape of the result in a couple of minutes:

python scripts/multi_level_asian.py --eps 1e-4 5e-4 1e-3
python scripts/plot_multi_level_asian.py

Multilevel estimator, barrier option (report section V)

python scripts/multi_level_barrier.py
python scripts/plot_multi_level_barrier.py

Importance sampling at high strikes (report section VI)

This one prints its results and writes no data file:

python scripts/higher_strike.py

Tests

pip install pytest
pytest

The suite runs in a couple of seconds and checks the mathematical claims: a European call priced on these paths against the closed-form Black-Scholes price, the two-level estimator against standard Monte Carlo, the level coupling, the variance decay and pilot level selection, and the importance-sampling variance reduction. The long multilevel sweeps above are not part of it.

References

See REFERENCES.md for the papers the method follows.

License

This project is licensed under the MIT License.