import matplotlib.pyplot as plt
import numpy as np
import qmcpy as qp
seed = 7

Comparison of multilevel (Quasi-)Monte Carlo for an Asian option problem

Compute the exact value of the Asian option with single level QMC, for an increasing number of time steps:

for level in range(5):
    aco = qp.AsianOption(qp.Sobol(2*2**level, seed=seed), volatility=.2, start_price=100, strike_price=100, interest_rate=.05)
    approx_solution, data = qp.CubQMCSobolG(aco, abs_tol=1e-4).integrate()
    print("Asian Option true value (%d time steps): %.5f (to within 1e-4)"%(2*2**level, approx_solution))
Asian Option true value (2 time steps): 5.63591 (to within 1e-4)
Asian Option true value (4 time steps): 5.73171 (to within 1e-4)
Asian Option true value (8 time steps): 5.75526 (to within 1e-4)
Asian Option true value (16 time steps): 5.76113 (to within 1e-4)
Asian Option true value (32 time steps): 5.76260 (to within 1e-4)

This function compares 4 different algorithms: Multilevel Monte Carlo (CubMCML), Multilevel Quasi-Monte Carlo (CubQMCML), continuation Multilevel Monte Carlo (CubMCMLCont) and Multilevel Quasi-Monte Carlo (CubQMCMLCont):

def eval_option(option_mc, option_qmc, abs_tol):
    stopping_criteria = {
        "MLMC" : qp.CubMCML(option_mc, abs_tol=abs_tol, levels_max=15),
        "continuation MLMC" : qp.CubMCMLCont(option_mc, abs_tol=abs_tol, levels_max=15),
        "MLQMC" : qp.CubQMCML(option_qmc, abs_tol=abs_tol, levels_max=15),
        "continuation MLQMC" : qp.CubQMCMLCont(option_qmc, abs_tol=abs_tol, levels_max=15)
    }

    levels = []
    times = []
    for name, stopper in stopping_criteria.items():
        sol, data = stopper.integrate()
        levels.append(data.levels)
        times.append(data.time_integrate)
        print("\t%-20s solution %-10.4f number of levels %-6d time %.3f"%(name, sol, levels[-1], times[-1]))

    return levels, times

Define the Multilevel Asian options:

option_mc = qp.MLCallOptions(qp.IIDStdUniform(seed=seed), option="asian")
option_qmc = qp.MLCallOptions(qp.Lattice(seed=seed), option="asian")

Run and compare each of the 4 algorithms for the Asian option problem:

eval_option(option_mc, option_qmc, abs_tol=5e-3);
MLMC                 solution 5.7630     number of levels 10     time 13.781
continuation MLMC    solution 5.7583     number of levels 7      time 12.456
MLQMC                solution 5.7613     number of levels 8      time 6.408
continuation MLQMC   solution 5.7592     number of levels 7      time 2.073

Repeat this comparison for a sequence of decreasing tolerances, with 5 different random seeds each. This will allow us to visualize the asymptotic cost complexity of each method.

repetitions = 5
tolerances = 5*np.logspace(-1, -3, num=5)

levels = {}
times = {}
for t in range(len(tolerances)):
    for r in range(repetitions):
        print("tolerance = %10.4e, repetition = %d/%d"%(tolerances[t], r + 1, repetitions))
        levels[t, r], times[t, r] = eval_option(option_mc, option_qmc, tolerances[t])
tolerance = 5.0000e-01, repetition = 1/5
    MLMC                 solution 5.7654     number of levels 3      time 0.007
    continuation MLMC    solution 5.8128     number of levels 3      time 0.011
    MLQMC                solution 5.7229     number of levels 3      time 0.170
    continuation MLQMC   solution 5.7045     number of levels 3      time 0.000
tolerance = 5.0000e-01, repetition = 2/5
    MLMC                 solution 5.9289     number of levels 4      time 0.005
    continuation MLMC    solution 5.7235     number of levels 3      time 0.009
    MLQMC                solution 5.7144     number of levels 3      time 0.208
    continuation MLQMC   solution 5.7164     number of levels 3      time 0.000
tolerance = 5.0000e-01, repetition = 3/5
    MLMC                 solution 5.8284     number of levels 3      time 0.005
    continuation MLMC    solution 5.6069     number of levels 3      time 0.007
    MLQMC                solution 5.7251     number of levels 3      time 0.160
    continuation MLQMC   solution 5.6889     number of levels 3      time 0.000
tolerance = 5.0000e-01, repetition = 4/5
    MLMC                 solution 5.7565     number of levels 4      time 0.005
    continuation MLMC    solution 5.7117     number of levels 3      time 0.007
    MLQMC                solution 5.6831     number of levels 3      time 0.162
    continuation MLQMC   solution 5.7106     number of levels 3      time 0.000
tolerance = 5.0000e-01, repetition = 5/5
    MLMC                 solution 5.6210     number of levels 3      time 0.004
    continuation MLMC    solution 5.5126     number of levels 3      time 0.007
    MLQMC                solution 5.7067     number of levels 3      time 0.168
    continuation MLQMC   solution 5.7053     number of levels 3      time 0.000
tolerance = 1.5811e-01, repetition = 1/5
    MLMC                 solution 5.8072     number of levels 6      time 0.021
    continuation MLMC    solution 5.7373     number of levels 4      time 0.017
    MLQMC                solution 5.7424     number of levels 4      time 0.287
    continuation MLQMC   solution 5.7085     number of levels 3      time 0.022
tolerance = 1.5811e-01, repetition = 2/5
    MLMC                 solution 5.7893     number of levels 7      time 0.034
    continuation MLMC    solution 5.7419     number of levels 4      time 0.037
    MLQMC                solution 5.7329     number of levels 4      time 0.313
    continuation MLQMC   solution 5.6862     number of levels 3      time 0.030
tolerance = 1.5811e-01, repetition = 3/5
    MLMC                 solution 5.7959     number of levels 5      time 0.025
    continuation MLMC    solution 5.6990     number of levels 4      time 0.030
    MLQMC                solution 5.7409     number of levels 4      time 0.423
    continuation MLQMC   solution 5.6983     number of levels 3      time 0.017
tolerance = 1.5811e-01, repetition = 4/5
    MLMC                 solution 5.8389     number of levels 5      time 0.015
    continuation MLMC    solution 5.8064     number of levels 5      time 0.024
    MLQMC                solution 5.7378     number of levels 4      time 0.311
    continuation MLQMC   solution 5.7063     number of levels 3      time 0.025
tolerance = 1.5811e-01, repetition = 5/5
    MLMC                 solution 5.7334     number of levels 4      time 0.018
    continuation MLMC    solution 5.8528     number of levels 4      time 0.020
    MLQMC                solution 5.7278     number of levels 4      time 0.312
    continuation MLQMC   solution 5.7241     number of levels 4      time 0.106
tolerance = 5.0000e-02, repetition = 1/5
    MLMC                 solution 5.7680     number of levels 7      time 0.147
    continuation MLMC    solution 5.7065     number of levels 4      time 0.123
    MLQMC                solution 5.7489     number of levels 5      time 0.505
    continuation MLQMC   solution 5.7307     number of levels 4      time 0.032
tolerance = 5.0000e-02, repetition = 2/5
    MLMC                 solution 5.7418     number of levels 7      time 0.159
    continuation MLMC    solution 5.7268     number of levels 4      time 0.078
    MLQMC                solution 5.7456     number of levels 5      time 0.493
    continuation MLQMC   solution 5.7492     number of levels 5      time 0.156
tolerance = 5.0000e-02, repetition = 3/5
    MLMC                 solution 5.7405     number of levels 6      time 0.151
    continuation MLMC    solution 5.7331     number of levels 4      time 0.113
    MLQMC                solution 5.7449     number of levels 5      time 0.476
    continuation MLQMC   solution 5.7472     number of levels 5      time 0.109
tolerance = 5.0000e-02, repetition = 4/5
    MLMC                 solution 5.7673     number of levels 7      time 0.134
    continuation MLMC    solution 5.7357     number of levels 5      time 0.147
    MLQMC                solution 5.7462     number of levels 5      time 0.435
    continuation MLQMC   solution 5.7324     number of levels 4      time 0.061
tolerance = 5.0000e-02, repetition = 5/5
    MLMC                 solution 5.7583     number of levels 7      time 0.114
    continuation MLMC    solution 5.7191     number of levels 4      time 0.076
    MLQMC                solution 5.7464     number of levels 5      time 0.423
    continuation MLQMC   solution 5.7308     number of levels 4      time 0.025
tolerance = 1.5811e-02, repetition = 1/5
    MLMC                 solution 5.7618     number of levels 8      time 1.363
    continuation MLMC    solution 5.7516     number of levels 6      time 1.279
    MLQMC                solution 5.7553     number of levels 6      time 1.293
    continuation MLQMC   solution 5.7479     number of levels 5      time 0.163
tolerance = 1.5811e-02, repetition = 2/5
    MLMC                 solution 5.7630     number of levels 8      time 1.104
    continuation MLMC    solution 5.7576     number of levels 6      time 1.034
    MLQMC                solution 5.7563     number of levels 6      time 1.037
    continuation MLQMC   solution 5.7553     number of levels 6      time 0.318
tolerance = 1.5811e-02, repetition = 3/5
    MLMC                 solution 5.7563     number of levels 9      time 1.476
    continuation MLMC    solution 5.7578     number of levels 6      time 1.081
    MLQMC                solution 5.7589     number of levels 7      time 1.409
    continuation MLQMC   solution 5.7566     number of levels 6      time 0.367
tolerance = 1.5811e-02, repetition = 4/5
    MLMC                 solution 5.7648     number of levels 8      time 1.203
    continuation MLMC    solution 5.7546     number of levels 6      time 0.659
    MLQMC                solution 5.7551     number of levels 6      time 0.986
    continuation MLQMC   solution 5.7482     number of levels 5      time 0.170
tolerance = 1.5811e-02, repetition = 5/5
    MLMC                 solution 5.7678     number of levels 8      time 1.490
    continuation MLMC    solution 5.7554     number of levels 6      time 0.581
    MLQMC                solution 5.7561     number of levels 6      time 0.854
    continuation MLQMC   solution 5.7474     number of levels 5      time 0.167
tolerance = 5.0000e-03, repetition = 1/5
    MLMC                 solution 5.7635     number of levels 10     time 15.841
    continuation MLMC    solution 5.7588     number of levels 7      time 8.160
    MLQMC                solution 5.7609     number of levels 8      time 6.344
    continuation MLQMC   solution 5.7590     number of levels 7      time 2.422
tolerance = 5.0000e-03, repetition = 2/5
    MLMC                 solution 5.7624     number of levels 10     time 14.806
    continuation MLMC    solution 5.7577     number of levels 7      time 12.720
    MLQMC                solution 5.7610     number of levels 8      time 5.639
    continuation MLQMC   solution 5.7601     number of levels 7      time 1.524
tolerance = 5.0000e-03, repetition = 3/5
    MLMC                 solution 5.7651     number of levels 10     time 13.543
    continuation MLMC    solution 5.7605     number of levels 7      time 11.780
    MLQMC                solution 5.7610     number of levels 8      time 7.015
    continuation MLQMC   solution 5.7593     number of levels 7      time 3.229
tolerance = 5.0000e-03, repetition = 4/5
    MLMC                 solution 5.7630     number of levels 10     time 12.791
    continuation MLMC    solution 5.7595     number of levels 7      time 11.755
    MLQMC                solution 5.7615     number of levels 8      time 5.914
    continuation MLQMC   solution 5.7594     number of levels 7      time 2.924
tolerance = 5.0000e-03, repetition = 5/5
    MLMC                 solution 5.7611     number of levels 10     time 13.041
    continuation MLMC    solution 5.7587     number of levels 7      time 12.751
    MLQMC                solution 5.7613     number of levels 8      time 6.122
    continuation MLQMC   solution 5.7593     number of levels 7      time 3.543

Compute and plot the asymptotic cost complexity.

avg_time = {}
for method in range(4):
    avg_time[method] = [np.mean([times[t, r][method] for r in range(repetitions)]) for t in range(len(tolerances))]
plt.figure(figsize=(10,7))
plt.plot(tolerances, avg_time[0], label="MLMC")
plt.plot(tolerances, avg_time[1], label="continuation MLMC")
plt.plot(tolerances, avg_time[2], label="MLQMC")
plt.plot(tolerances, avg_time[3], label="continuation MLQMC")
plt.xscale("log")
plt.yscale("log")
plt.xlabel("requested absolute tolerance")
plt.ylabel("average run time in seconds")
plt.legend();
../_images/asian-option-mlqmc_15_0.png
max_levels = {}
for method in range(4):
    levels_rep = np.array([levels[len(tolerances)-1, r][method] for r in range(repetitions)])
    max_levels[method] = [np.count_nonzero(levels_rep == level)/repetitions for level in range(15)]
plt.figure(figsize=(14,10))
plt.subplot(2,2,1); plt.bar(range(15), max_levels[0], label="MLMC old", color="C0"); plt.xlabel("max level"); plt.ylabel("fraction of runs"); plt.ylim(0, 1); plt.legend()
plt.subplot(2,2,2); plt.bar(range(15), max_levels[1], label="MLMC new", color="C1"); plt.xlabel("max level"); plt.ylabel("fraction of runs"); plt.ylim(0, 1); plt.legend()
plt.subplot(2,2,3); plt.bar(range(15), max_levels[2], label="MLQMC old", color="C2"); plt.xlabel("max level"); plt.ylabel("fraction of runs"); plt.ylim(0, 1); plt.legend()
plt.subplot(2,2,4); plt.bar(range(15), max_levels[3], label="MLQMC new", color="C3"); plt.xlabel("max level"); plt.ylabel("fraction of runs"); plt.ylim(0, 1); plt.legend();
../_images/asian-option-mlqmc_17_0.png