```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.63592 (to within 1e-4)
Asian Option true value (4 time steps): 5.73170 (to within 1e-4)
Asian Option true value (8 time steps): 5.75524 (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.76263 (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.IIDStdGaussian(seed=seed), option="asian")
option_qmc = qp.MLCallOptions(qp.Sobol(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.7603     number of levels 10     time 10.585
continuation MLMC    solution 5.7603     number of levels 7      time 9.039
MLQMC                solution 5.7610     number of levels 8      time 16.371
continuation MLQMC   solution 5.7594     number of levels 7      time 13.881
```

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.7521     number of levels 3      time 0.004
continuation MLMC    solution 5.5187     number of levels 3      time 0.007
MLQMC                solution 5.7014     number of levels 3      time 1.652
continuation MLQMC   solution 5.7063     number of levels 3      time 1.633
tolerance = 5.0000e-01, repetition = 2/5
MLMC                 solution 5.7906     number of levels 3      time 0.003
continuation MLMC    solution 5.7875     number of levels 4      time 0.009
MLQMC                solution 5.7046     number of levels 3      time 1.588
continuation MLQMC   solution 5.7036     number of levels 3      time 1.612
tolerance = 5.0000e-01, repetition = 3/5
MLMC                 solution 5.8712     number of levels 3      time 0.003
continuation MLMC    solution 5.9401     number of levels 3      time 0.006
MLQMC                solution 5.7033     number of levels 3      time 1.584
continuation MLQMC   solution 5.7044     number of levels 3      time 1.623
tolerance = 5.0000e-01, repetition = 4/5
MLMC                 solution 5.7485     number of levels 3      time 0.004
continuation MLMC    solution 5.5995     number of levels 3      time 0.006
MLQMC                solution 5.6995     number of levels 3      time 1.680
continuation MLQMC   solution 5.7002     number of levels 3      time 1.599
tolerance = 5.0000e-01, repetition = 5/5
MLMC                 solution 5.7223     number of levels 3      time 0.004
continuation MLMC    solution 5.6094     number of levels 4      time 0.008
MLQMC                solution 5.7066     number of levels 3      time 1.605
continuation MLQMC   solution 5.7035     number of levels 3      time 1.604
tolerance = 1.5811e-01, repetition = 1/5
MLMC                 solution 5.7618     number of levels 5      time 0.015
continuation MLMC    solution 5.6843     number of levels 4      time 0.017
MLQMC                solution 5.7326     number of levels 4      time 2.099
continuation MLQMC   solution 5.7069     number of levels 3      time 1.602
tolerance = 1.5811e-01, repetition = 2/5
MLMC                 solution 5.8008     number of levels 5      time 0.015
continuation MLMC    solution 5.7693     number of levels 4      time 0.012
MLQMC                solution 5.7383     number of levels 4      time 2.150
continuation MLQMC   solution 5.7086     number of levels 3      time 1.615
tolerance = 1.5811e-01, repetition = 3/5
MLMC                 solution 5.7496     number of levels 5      time 0.017
continuation MLMC    solution 5.7117     number of levels 3      time 0.010
MLQMC                solution 5.7295     number of levels 4      time 2.124
continuation MLQMC   solution 5.7052     number of levels 3      time 1.642
tolerance = 1.5811e-01, repetition = 4/5
MLMC                 solution 5.7646     number of levels 7      time 0.036
continuation MLMC    solution 5.7288     number of levels 3      time 0.012
MLQMC                solution 5.7386     number of levels 4      time 2.169
continuation MLQMC   solution 5.7053     number of levels 3      time 1.672
tolerance = 1.5811e-01, repetition = 5/5
MLMC                 solution 5.7692     number of levels 6      time 0.021
continuation MLMC    solution 5.6359     number of levels 4      time 0.013
MLQMC                solution 5.7292     number of levels 4      time 2.112
continuation MLQMC   solution 5.7028     number of levels 3      time 1.600
tolerance = 5.0000e-02, repetition = 1/5
MLMC                 solution 5.7515     number of levels 7      time 0.102
continuation MLMC    solution 5.7475     number of levels 5      time 0.076
MLQMC                solution 5.7482     number of levels 5      time 3.622
continuation MLQMC   solution 5.7313     number of levels 4      time 2.639
tolerance = 5.0000e-02, repetition = 2/5
MLMC                 solution 5.7625     number of levels 7      time 0.096
continuation MLMC    solution 5.7410     number of levels 4      time 0.076
MLQMC                solution 5.7487     number of levels 5      time 3.577
continuation MLQMC   solution 5.7376     number of levels 4      time 2.675
tolerance = 5.0000e-02, repetition = 3/5
MLMC                 solution 5.7480     number of levels 7      time 0.107
continuation MLMC    solution 5.7364     number of levels 4      time 0.073
MLQMC                solution 5.7463     number of levels 5      time 3.736
continuation MLQMC   solution 5.7303     number of levels 4      time 2.659
tolerance = 5.0000e-02, repetition = 4/5
MLMC                 solution 5.7554     number of levels 8      time 0.125
continuation MLMC    solution 5.7706     number of levels 5      time 0.083
MLQMC                solution 5.7468     number of levels 5      time 3.220
continuation MLQMC   solution 5.7370     number of levels 4      time 2.685
tolerance = 5.0000e-02, repetition = 5/5
MLMC                 solution 5.7667     number of levels 7      time 0.122
continuation MLMC    solution 5.7391     number of levels 5      time 0.079
MLQMC                solution 5.7515     number of levels 5      time 3.306
continuation MLQMC   solution 5.7304     number of levels 4      time 2.684
tolerance = 1.5811e-02, repetition = 1/5
MLMC                 solution 5.7619     number of levels 8      time 0.910
continuation MLMC    solution 5.7617     number of levels 6      time 0.768
MLQMC                solution 5.7551     number of levels 6      time 6.871
continuation MLQMC   solution 5.7554     number of levels 6      time 5.854
tolerance = 1.5811e-02, repetition = 2/5
MLMC                 solution 5.7620     number of levels 8      time 0.851
continuation MLMC    solution 5.7523     number of levels 6      time 0.756
MLQMC                solution 5.7596     number of levels 7      time 7.719
continuation MLQMC   solution 5.7484     number of levels 5      time 5.233
tolerance = 1.5811e-02, repetition = 3/5
MLMC                 solution 5.7639     number of levels 8      time 0.871
continuation MLMC    solution 5.7532     number of levels 6      time 0.764
MLQMC                solution 5.7590     number of levels 7      time 7.129
continuation MLQMC   solution 5.7466     number of levels 5      time 6.468
tolerance = 1.5811e-02, repetition = 4/5
MLMC                 solution 5.7624     number of levels 8      time 1.235
continuation MLMC    solution 5.7606     number of levels 6      time 0.944
MLQMC                solution 5.7577     number of levels 7      time 10.808
continuation MLQMC   solution 5.7470     number of levels 5      time 5.181
tolerance = 1.5811e-02, repetition = 5/5
MLMC                 solution 5.7588     number of levels 8      time 0.972
continuation MLMC    solution 5.7537     number of levels 6      time 0.771
MLQMC                solution 5.7559     number of levels 6      time 6.907
continuation MLQMC   solution 5.7455     number of levels 5      time 5.156
tolerance = 5.0000e-03, repetition = 1/5
MLMC                 solution 5.7646     number of levels 10     time 10.215
continuation MLMC    solution 5.7601     number of levels 7      time 8.469
MLQMC                solution 5.7612     number of levels 8      time 18.159
continuation MLQMC   solution 5.7585     number of levels 7      time 12.753
tolerance = 5.0000e-03, repetition = 2/5
MLMC                 solution 5.7614     number of levels 10     time 10.177
continuation MLMC    solution 5.7577     number of levels 7      time 9.154
MLQMC                solution 5.7612     number of levels 8      time 16.621
continuation MLQMC   solution 5.7589     number of levels 7      time 12.675
tolerance = 5.0000e-03, repetition = 3/5
MLMC                 solution 5.7623     number of levels 10     time 12.058
continuation MLMC    solution 5.7596     number of levels 7      time 8.492
MLQMC                solution 5.7612     number of levels 8      time 16.919
continuation MLQMC   solution 5.7586     number of levels 7      time 12.588
tolerance = 5.0000e-03, repetition = 4/5
MLMC                 solution 5.7622     number of levels 10     time 10.062
continuation MLMC    solution 5.7586     number of levels 7      time 8.409
MLQMC                solution 5.7613     number of levels 8      time 19.131
continuation MLQMC   solution 5.7591     number of levels 7      time 13.764
tolerance = 5.0000e-03, repetition = 5/5
MLMC                 solution 5.7619     number of levels 10     time 10.264
continuation MLMC    solution 5.7564     number of levels 7      time 8.826
MLQMC                solution 5.7609     number of levels 8      time 16.201
continuation MLQMC   solution 5.7590     number of levels 7      time 14.010
```

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();
```
```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();
```