Homework 3

Due: Tuesday, October 23rd in class

Multi-level and Multi-order Monte Carlo Sampling

Note: Read the lecture notes here and here before doing this assignment.

Description: In this assignment you will consider the same stochastic ODE problem as in Homework 2 . The goal is to apply Multi-level MC (MLMC) and Multi-order MC (MOMC) sampling techniques and compare their performance with the performance of classical Monte Carlo sampling.

Tasks:

1. Consider a failure probability for the statistical error in MLMC or MOMC:

   $$P \Bigl( \varepsilon_{II} \ > \ C_{\alpha} \, \bigl(\sum_{\ell =0}^L \frac{V_{\ell}}{M_{\ell}} \bigr)^{1/2} \ > \ \theta \,\varepsilon_{TOL} \Bigr) \ \le \ \alpha.$$

   Here, \(\varepsilon_{II}\) is the statistical error in either MLMC or MOMC, \(C_{\alpha}\) is the confidence parameter, \(V_{\ell}\) is the variance of the difference \(Q_{\ell} - Q_{\ell-1}\) at level \(\ell\) (setting \(Q_{-1} = 0\)), and \(M_{\ell}\) is the number of samples at level \(\ell\). Find an appropriate confidence parameter \(C_{\alpha}\) for two cases: \(\alpha = 5 \%\) and \(\alpha =0.1 \%\). We will use these two values of \(C_{\alpha}\) and observe their effect on the error later.

2. Download the MATLAB files (in total 7 files) from the subdirectory hw3 in the public Bitbucket repository https://bitbucket.org/motamed/uq2017. It contains the following codes:

   • MLMC codes: mlmc_conv.m and mlmc.m and mlmc_ode.m
   • MOMC codes: momc_conv.m and momc.m and momc_ode.m

   Both methods will call and use the MATLAB file ode_taylor.m, where the deterministic solver (the \(q\) -th order accurate Taylor’s method) is implemented. For the following taks, you will need to modify only the two main codes: mlmc_conv.m and momc_conv.m. Do not modify the other files. Each of these two main files consists of 3 parts: 1) Input parameters; 2) Computations; 3) Plots.

   Consider a set of tolerances \(\varepsilon_{TOL} = 20 \times 10^{-4}, 19 \times 10^{-4}, 18 \times 10^{-4}, \dotsc, 1 \times 10^{-4}\) for all main codes. In the codes this is written as Eps=(20:-1:1)*(1e-4)}. Use the following parameter values:

   • mlmc_conv.m:

     \(q=2\) (a fixed order of accuracy of deterministic solver)

     \(h_0 = 0.5\) (time step for deterministic solver at level \(\ell = 0\))

     \(\beta = 2\) (mesh refinement ratio, with the mesh hierarchy \(h_{\ell} = h_0 \, \beta^{-\ell}\))

     \(\theta = 0.9\) (splitting parameter)

     \(C_{\alpha} =\) the value corresponding to \(\alpha = 5 \%\) obtained in task 1

   • momc_conv.m

     \(h=0.25\) (a fixed time step for deterministic solver)

     \(q_0 = 2\) (order of accuracy of deterministic solver at level \(\ell = 0\))

     \(\beta = 2\) (order increment parameter, with the order hierarchy \(q_{\ell} = q_0 + \beta \ \ell\))

     \(\theta = 0.9\) (splitting parameter)

     \(C_{\alpha} =\) the value corresponding to \(\alpha = 5 \%\) obtained in task 1.

   Generate two figures:

   • Figure 1: plot the total errors in MLMC and MOMC (y-axis) versus tolerances \(\varepsilon_{TOL}\) (x-asis) in the same figure. Use loglog to get a logarithmic scale on both axes. Use different markers/colors for the errors generated by different methods. The plot should have labels on each axis and a legend to describe each error. Use large fonts. Also plot the line \(\varepsilon_{TOL}\) versus \(\varepsilon_{TOL}\). From your figure you should be able to see if the total error generated by both methods remain below \(\varepsilon_{TOL}\) or not. If not, why? Explain.
   • Figure 2: plot the total computational cost of MLMC and MOMC (y-axis) versus tolerances \(\varepsilon_{TOL}\) (x-asis) in the same figure. Use loglog to get a logarithmic scale on both axes. Use different markers/colors for the errors generated by different methods. The plot should have labels on each axis and a legend. Use large fonts. From your figure you should be able to see which method is faster. Comment and discuss on the convergence rate of the computational costs with respect to tolerance \(\varepsilon_{TOL}\) and compare with the results you obtained for MC sampling in Homework 2.

3. Repeat task 2 with \(C_{\alpha} =\) the value corresponding to \(\alpha = 0.1 \%\) obtained in task 1. Describe and explain the change that you may observe compared to task 2.

4. Next, in mlmc_conv.m and momc_conv.m, consider a fixed tolerance \(\varepsilon_{TOL} = 10^{-3}\) and \(C_{\alpha} =\) the value corresponding to \(\alpha = 0.1 \%\).

   A- Numerically play with parameters \(q, h_0, \beta, \theta\)

   in mlmc_conv.m and empirically find a combination of parameters that produces the smallest possible computational cost of MLMC.

   B- Numerically play with parameters \(h, q_0, \beta, \theta\)

   in mlmc_conv.m and empirically find a combination of parameters that produces the smallest possible computational cost of MOMC.

   C- Compare the minimum possible costs of MLMC and MOMC.