IDEAS home Printed from https://ideas.repec.org/a/inm/ormnsc/v66y2020i3p1421-1439.html
   My bibliography  Save this article

Randomized Dimension Reduction for Monte Carlo Simulations

Author

Listed:
  • Nabil Kahalé

    (ESCP Europe, LabEx ReFi, 75011 Paris, France)

Abstract

We present a new unbiased algorithm that estimates the expected value of f ( U ) via Monte Carlo simulation, where U is a vector of d independent random variables, and f is a function of d variables. We assume that f does not equally depend on all its arguments. Under certain conditions, we prove that, for the same computational cost, the variance of our estimator is lower than the variance of the standard Monte Carlo estimator by a factor of order d . Our method can be used to obtain a low-variance unbiased estimator for the expectation of a function of the state of a Markov chain at a given time step. We study applications to volatility forecasting and time-varying queues. Numerical experiments show that our algorithm dramatically improves on the standard Monte Carlo method for large values of d and is highly resilient to discontinuities.

Suggested Citation

  • Nabil Kahalé, 2020. "Randomized Dimension Reduction for Monte Carlo Simulations," Management Science, INFORMS, vol. 66(3), pages 1421-1439, March.
    • Handle: RePEc:inm:ormnsc:v:66:y:2020:i:3:p:1421-1439
    DOI: 10.1287/mnsc.2018.3250
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/mnsc.2018.3250
    Download Restriction: no
    File URL: https://libkey.io/10.1287/mnsc.2018.3250?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. Zdravko I. Botev & Pierre L'Ecuyer & Gerardo Rubino & Richard Simard & Bruno Tuffin, 2013. "Static Network Reliability Estimation via Generalized Splitting," INFORMS Journal on Computing, INFORMS, vol. 25(1), pages 56-71, February.
    2. Xiaoqun Wang & Ken Seng Tan, 2013. "Pricing and Hedging with Discontinuous Functions: Quasi-Monte Carlo Methods and Dimension Reduction," Management Science, INFORMS, vol. 59(2), pages 376-389, July.
    3. Imry Rosenbaum & Jeremy Staum, 2017. "Multilevel Monte Carlo Metamodeling," Operations Research, INFORMS, vol. 65(4), pages 1062-1077, August.
    4. Pierre L'Ecuyer & Christian Lécot & Bruno Tuffin, 2008. "A Randomized Quasi-Monte Carlo Simulation Method for Markov Chains," Operations Research, INFORMS, vol. 56(4), pages 958-975, August.
    5. Liu, Ruixue & Owen, Art B., 2006. "Estimating Mean Dimensionality of Analysis of Variance Decompositions," Journal of the American Statistical Association, American Statistical Association, vol. 101, pages 712-721, June.
    6. Xiaoqun Wang, 2006. "On the Effects of Dimension Reduction Techniques on Some High-Dimensional Problems in Finance," Operations Research, INFORMS, vol. 54(6), pages 1063-1078, December.
    7. Zohar Feldman & Avishai Mandelbaum & William A. Massey & Ward Whitt, 2008. "Staffing of Time-Varying Queues to Achieve Time-Stable Performance," Management Science, INFORMS, vol. 54(2), pages 324-338, February.
    8. Paul Glasserman & Philip Heidelberger & Perwez Shahabuddin, 1999. "Asymptotically Optimal Importance Sampling and Stratification for Pricing Path‐Dependent Options," Mathematical Finance, Wiley Blackwell, vol. 9(2), pages 117-152, April.
    9. Pierre L'Ecuyer & Christiane Lemieux, 2000. "Variance Reduction via Lattice Rules," Management Science, INFORMS, vol. 46(9), pages 1214-1235, September.
    10. Kai Nagel & Peter Wagner & Richard Woesler, 2003. "Still Flowing: Approaches to Traffic Flow and Traffic Jam Modeling," Operations Research, INFORMS, vol. 51(5), pages 681-710, October.
    11. Peter W. Glynn & Ward Whitt, 1992. "The Asymptotic Efficiency of Simulation Estimators," Operations Research, INFORMS, vol. 40(3), pages 505-520, June.
    12. Xiaoqun Wang & Ian H. Sloan, 2011. "Quasi-Monte Carlo Methods in Financial Engineering: An Equivalence Principle and Dimension Reduction," Operations Research, INFORMS, vol. 59(1), pages 80-95, February.
    13. Fredrik Åkesson & John P. Lehoczky, 2000. "Path Generation for Quasi-Monte Carlo Simulation of Mortgage-Backed Securities," Management Science, INFORMS, vol. 46(9), pages 1171-1187, September.
    14. Michael B. Giles, 2008. "Multilevel Monte Carlo Path Simulation," Operations Research, INFORMS, vol. 56(3), pages 607-617, June.
    15. Chang-Han Rhee & Peter W. Glynn, 2015. "Unbiased Estimation with Square Root Convergence for SDE Models," Operations Research, INFORMS, vol. 63(5), pages 1026-1043, October.
    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. Nabil Kahale, 2023. "Simulating Gaussian vectors via randomized dimension reduction and PCA," Papers 2304.07377, arXiv.org.

    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. 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.
    2. Xiaoqun Wang, 2016. "Handling Discontinuities in Financial Engineering: Good Path Simulation and Smoothing," Operations Research, INFORMS, vol. 64(2), pages 297-314, April.
    3. Xiaoqun Wang & Ken Seng Tan, 2013. "Pricing and Hedging with Discontinuous Functions: Quasi-Monte Carlo Methods and Dimension Reduction," Management Science, INFORMS, vol. 59(2), pages 376-389, July.
    4. Borgonovo, Emanuele & Rabitti, Giovanni, 2023. "Screening: From tornado diagrams to effective dimensions," European Journal of Operational Research, Elsevier, vol. 304(3), pages 1200-1211.
    5. Xiaoqun Wang & Ian H. Sloan, 2011. "Quasi-Monte Carlo Methods in Financial Engineering: An Equivalence Principle and Dimension Reduction," Operations Research, INFORMS, vol. 59(1), pages 80-95, February.
    6. Dingeç, Kemal Dinçer & Hörmann, Wolfgang, 2013. "Control variates and conditional Monte Carlo for basket and Asian options," Insurance: Mathematics and Economics, Elsevier, vol. 52(3), pages 421-434.
    7. Cui, Zhenyu & Fu, Michael C. & Peng, Yijie & Zhu, Lingjiong, 2020. "Optimal unbiased estimation for expected cumulative discounted cost," European Journal of Operational Research, Elsevier, vol. 286(2), pages 604-618.
    8. Ye Xiao & Xiaoqun Wang, 2019. "Enhancing Quasi-Monte Carlo Simulation by Minimizing Effective Dimension for Derivative Pricing," Computational Economics, Springer;Society for Computational Economics, vol. 54(1), pages 343-366, June.
    9. Zhijian He & Xiaoqun Wang, 2021. "An Integrated Quasi-Monte Carlo Method for Handling High Dimensional Problems with Discontinuities in Financial Engineering," Computational Economics, Springer;Society for Computational Economics, vol. 57(2), pages 693-718, February.
    10. Nabil Kahale, 2018. "General multilevel Monte Carlo methods for pricing discretely monitored Asian options," Papers 1805.09427, arXiv.org, revised Sep 2018.
    11. Borgonovo, Emanuele & Plischke, Elmar, 2016. "Sensitivity analysis: A review of recent advances," European Journal of Operational Research, Elsevier, vol. 248(3), pages 869-887.
    12. Xiaoqun Wang, 2009. "Dimension Reduction Techniques in Quasi-Monte Carlo Methods for Option Pricing," INFORMS Journal on Computing, INFORMS, vol. 21(3), pages 488-504, August.
    13. Matti Vihola & Jouni Helske & Jordan Franks, 2020. "Importance sampling type estimators based on approximate marginal Markov chain Monte Carlo," Scandinavian Journal of Statistics, Danish Society for Theoretical Statistics;Finnish Statistical Society;Norwegian Statistical Association;Swedish Statistical Association, vol. 47(4), pages 1339-1376, December.
    14. H. Heitsch & H. Leövey & W. Römisch, 2016. "Are Quasi-Monte Carlo algorithms efficient for two-stage stochastic programs?," Computational Optimization and Applications, Springer, vol. 65(3), pages 567-603, December.
    15. Wei Fang & Zhenru Wang & Michael B. Giles & Chris H. Jackson & Nicky J. Welton & Christophe Andrieu & Howard Thom, 2022. "Multilevel and Quasi Monte Carlo Methods for the Calculation of the Expected Value of Partial Perfect Information," Medical Decision Making, , vol. 42(2), pages 168-181, February.
    16. 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.
    17. Genin, Adrien & Tankov, Peter, 2020. "Optimal importance sampling for Lévy processes," Stochastic Processes and their Applications, Elsevier, vol. 130(1), pages 20-46.
    18. Jan Baldeaux, 2011. "Exact Simulation of the 3/2 Model," Papers 1105.3297, arXiv.org, revised May 2011.
    19. Andersson, Patrik & Kohatsu-Higa, Arturo & Yuasa, Tomooki, 2020. "Second order probabilistic parametrix method for unbiased simulation of stochastic differential equations," Stochastic Processes and their Applications, Elsevier, vol. 130(9), pages 5543-5574.
    20. Adrien Genin & Peter Tankov, 2016. "Optimal importance sampling for L\'evy Processes," Papers 1608.04621, arXiv.org.

    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:inm:ormnsc:v:66:y:2020:i:3:p:1421-1439. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.