IDEAS home Printed from https://ideas.repec.org/p/hal/journl/hal-01214840.html
   My bibliography  Save this paper

Coupling Importance Sampling and Multilevel Monte Carlo using Sample Average Approximation

Author

Listed:
  • Ahmed Kebaier

    (LAGA - Laboratoire Analyse, Géométrie et Applications - UP8 - Université Paris 8 Vincennes-Saint-Denis - UP13 - Université Paris 13 - Institut Galilée - CNRS - Centre National de la Recherche Scientifique)

  • Jérôme Lelong

    (DAO - Données, Apprentissage et Optimisation - LJK - Laboratoire Jean Kuntzmann - Grenoble INP - Institut polytechnique de Grenoble - Grenoble Institute of Technology - Inria - Institut National de Recherche en Informatique et en Automatique - CNRS - Centre National de la Recherche Scientifique - UGA [2016-2019] - Université Grenoble Alpes [2016-2019])

Abstract

In this work, we propose a smart idea to couple importance sampling and Multilevel Monte Carlo (MLMC). We advocate a per level approach with as many importance sampling parameters as the number of levels, which enables us to compute the different levels independently. The search for parameters is carried out using sample average approximation, which basically consists in applying deterministic optimisation techniques to a Monte Carlo approximation rather than resorting to stochastic approximation. Our innovative estimator leads to a robust and efficient procedure reducing both the discretization error (the bias) and the variance for a given computational effort. In the setting of discretized diffusions, we prove that our estimator satisfies a strong law of large numbers and a central limit theorem with optimal limiting variance, in the sense that this is the variance achieved by the best importance sampling measure (among the class of changes we consider), which is however non tractable. Finally, we illustrate the efficiency of our method on several numerical challenges coming from quantitative finance and show that it outperforms the standard MLMC estimator.

Suggested Citation

  • Ahmed Kebaier & Jérôme Lelong, 2018. "Coupling Importance Sampling and Multilevel Monte Carlo using Sample Average Approximation," Post-Print hal-01214840, HAL.
    • Handle: RePEc:hal:journl:hal-01214840
    DOI: 10.1007/s11009-017-9579-y
    Note: View the original document on HAL open archive server: https://hal.science/hal-01214840v4
    as

    Download full text from publisher

    File URL: https://hal.science/hal-01214840v4/document
    Download Restriction: no
    File URL: https://libkey.io/10.1007/s11009-017-9579-y?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Michael B. Giles & Lukasz Szpruch, 2012. "Antithetic multilevel Monte Carlo estimation for multi-dimensional SDEs without L\'{e}vy area simulation," Papers 1202.6283, arXiv.org, revised May 2014.
    2. Lelong, Jérôme, 2008. "Almost sure convergence of randomly truncated stochastic algorithms under verifiable conditions," Statistics & Probability Letters, Elsevier, vol. 78(16), pages 2632-2636, November.
    3. Michael Giles & Desmond Higham & Xuerong Mao, 2009. "Analysing multi-level Monte Carlo for options with non-globally Lipschitz payoff," Finance and Stochastics, Springer, vol. 13(3), pages 403-413, September.
    4. Michael B. Giles, 2008. "Multilevel Monte Carlo Path Simulation," Operations Research, INFORMS, vol. 56(3), pages 607-617, June.
    5. Dereich, Steffen & Heidenreich, Felix, 2011. "A multilevel Monte Carlo algorithm for Lévy-driven stochastic differential equations," Stochastic Processes and their Applications, Elsevier, vol. 121(7), pages 1565-1587, July.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Devang Sinha & Siddhartha P. Chakrabarty, 2022. "Multilevel Monte Carlo and its Applications in Financial Engineering," Papers 2209.14549, arXiv.org.
    2. Jérôme Lelong & Zineb El Filali Ech-Chafiq & Adil Reghai, 2020. "Automatic Control Variates for Option Pricing using Neural Networks," Working Papers hal-02891798, HAL.
    3. Mouna Ben Derouich & Ahmed Kebaier, 2022. "Interpolated Drift Implicit Euler MLMC Method for Barrier Option Pricing and application to CIR and CEV Models," Papers 2210.00779, arXiv.org, revised Sep 2024.
    4. Jérôme Lelong & Zineb El Filali Ech-Chafiq & Adil Reghai, 2021. "Automatic Control Variates for Option Pricing using Neural Networks," Post-Print hal-02891798, HAL.
    5. Devang Sinha & Siddhartha P. Chakrabarty, 2022. "Multilevel Richardson-Romberg and Importance Sampling in Derivative Pricing," Papers 2209.00821, arXiv.org.
    6. Kahalé, Nabil, 2020. "General multilevel Monte Carlo methods for pricing discretely monitored Asian options," European Journal of Operational Research, Elsevier, vol. 287(2), pages 739-748.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Ahmed Kebaier & J'er^ome Lelong, 2015. "Coupling Importance Sampling and Multilevel Monte Carlo using Sample Average Approximation," Papers 1510.03590, arXiv.org, revised Jul 2017.
    2. Ahmed Kebaier & Jérôme Lelong, 2017. "Coupling Importance Sampling and Multilevel Monte Carlo using Sample Average Approximation," Working Papers hal-01214840, HAL.
    3. Michael B. Giles & Abdul-Lateef Haji-Ali & Jonathan Spence, 2023. "Efficient Risk Estimation for the Credit Valuation Adjustment," Papers 2301.05886, arXiv.org, revised May 2024.
    4. Mike Giles & Lukasz Szpruch, 2012. "Multilevel Monte Carlo methods for applications in finance," Papers 1212.1377, arXiv.org.
    5. Michael B. Giles & Kristian Debrabant & Andreas Ro{ss}ler, 2013. "Analysis of multilevel Monte Carlo path simulation using the Milstein discretisation," Papers 1302.4676, arXiv.org, revised Jun 2019.
    6. Ahmed Kebaier & Jérôme Lelong, 2018. "Coupling Importance Sampling and Multilevel Monte Carlo using Sample Average Approximation," Methodology and Computing in Applied Probability, Springer, vol. 20(2), pages 611-641, June.
    7. Michael B. Giles & Abdul-Lateef Haji-Ali, 2022. "Multilevel Path Branching for Digital Options," Papers 2209.03017, arXiv.org, revised Jun 2024.
    8. Devang Sinha & Siddhartha P. Chakrabarty, 2022. "Multilevel Monte Carlo and its Applications in Financial Engineering," Papers 2209.14549, arXiv.org.
    9. Lay Harold A. & Colgin Zane & Reshniak Viktor & Khaliq Abdul Q. M., 2018. "On the implementation of multilevel Monte Carlo simulation of the stochastic volatility and interest rate model using multi-GPU clusters," Monte Carlo Methods and Applications, De Gruyter, vol. 24(4), pages 309-321, December.
    10. Hoel Håkon & von Schwerin Erik & Szepessy Anders & Tempone Raúl, 2014. "Implementation and analysis of an adaptive multilevel Monte Carlo algorithm," Monte Carlo Methods and Applications, De Gruyter, vol. 20(1), pages 1-41, March.
    11. Jorge Ignacio Gonz'alez C'azares & Aleksandar Mijatovi'c & Ger'onimo Uribe Bravo, 2018. "Geometrically Convergent Simulation of the Extrema of L\'{e}vy Processes," Papers 1810.11039, arXiv.org, revised Jun 2021.
    12. Jorge Gonz'alez C'azares & Aleksandar Mijatovi'c, 2020. "Simulation of the drawdown and its duration in L\'{e}vy models via stick-breaking Gaussian approximation," Papers 2011.06618, arXiv.org, revised Mar 2021.
    13. Christian Bayer & Chiheb Ben Hammouda & Raul Tempone, 2020. "Multilevel Monte Carlo with Numerical Smoothing for Robust and Efficient Computation of Probabilities and Densities," Papers 2003.05708, arXiv.org, revised Oct 2023.
    14. Andrei Cozma & Christoph Reisinger, 2017. "Strong convergence rates for Euler approximations to a class of stochastic path-dependent volatility models," Papers 1706.07375, arXiv.org, revised Oct 2018.
    15. Benjamin Jourdain & Mohamed Sbai, 2013. "High order discretization schemes for stochastic volatility models," Post-Print hal-00409861, HAL.
    16. Al Gerbi Anis & Jourdain Benjamin & Clément Emmanuelle, 2016. "Ninomiya–Victoir scheme: Strong convergence, antithetic version and application to multilevel estimators," Monte Carlo Methods and Applications, De Gruyter, vol. 22(3), pages 197-228, September.
    17. Andrei Cozma & Christoph Reisinger, 2017. "Strong order 1/2 convergence of full truncation Euler approximations to the Cox-Ingersoll-Ross process," Papers 1704.07321, arXiv.org, revised Oct 2018.
    18. Nabil Kahale, 2018. "General multilevel Monte Carlo methods for pricing discretely monitored Asian options," Papers 1805.09427, arXiv.org, revised Sep 2018.
    19. Abdul-Lateef Haji-Ali & Jonathan Spence, 2023. "Nested Multilevel Monte Carlo with Biased and Antithetic Sampling," Papers 2308.07835, arXiv.org.
    20. Richard, Alexandre & Tan, Xiaolu & Yang, Fan, 2021. "Discrete-time simulation of Stochastic Volterra equations," Stochastic Processes and their Applications, Elsevier, vol. 141(C), pages 109-138.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:hal:journl:hal-01214840. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: CCSD (email available below). General contact details of provider: https://hal.archives-ouvertes.fr/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.