IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v49y2001i6p900-912.html
   My bibliography  Save this article

Importance Sampling and the Cyclic Approach

Author

Listed:
  • Sandeep Juneja

    (Department of Mechanical Engineering, Indian Institute of Technology, Delhi, Hauz Khas, New Delhi 110016, India)

Abstract

The method of importance sampling is widely used for efficient rare-event simulation of stochastic systems. This method involves simulating the system under a new distribution that accentuates the probability along the most likely paths to the rare event. Traditionally, insights from large deviations theory are used to identify the distribution emphasizing these most likely paths. In this paper we develop an intuitive cyclic approach for selecting such a distribution. The key idea is to select a distribution under which the event of interest is no longer rare and the probability of occurrence of a cycle in any sample path remains equal to the original probability of that cycle. We show that only an exponentially twisted distribution can satisfy this equiprobable cycle condition. Using this approach we provide an elementary derivation of the asymptotically optimal change of measure for level crossing probability for Markov-additive processes. To demonstrate its ease of use for more complex stochastic systems, we apply it to determine the asymptotically optimal change of measure for estimating buffer overflow probability of a single-server queue subject to server interruptions.

Suggested Citation

  • Sandeep Juneja, 2001. "Importance Sampling and the Cyclic Approach," Operations Research, INFORMS, vol. 49(6), pages 900-912, December.
    • Handle: RePEc:inm:oropre:v:49:y:2001:i:6:p:900-912
    DOI: 10.1287/opre.49.6.900.10016
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.49.6.900.10016
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.49.6.900.10016?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. Sandeep Juneja & Perwez Shahabuddin, 2001. "Fast Simulation of Markov Chains with Small Transition Probabilities," Management Science, INFORMS, vol. 47(4), pages 547-562, April.
    2. Asmussen, S. & Binswanger, K., 1997. "Simulation of Ruin Probabilities for Subexponential Claims," ASTIN Bulletin, Cambridge University Press, vol. 27(2), pages 297-318, November.
    Full references (including those not matched with items on IDEAS)

    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. Fabian Dickmann & Nikolaus Schweizer, 2014. "Faster Comparison of Stopping Times by Nested Conditional Monte Carlo," Papers 1402.0243, arXiv.org.
    2. Albrecher Hansjörg & Kantor Josef, 2002. "Simulation of ruin probabilities for risk processes of Markovian type," Monte Carlo Methods and Applications, De Gruyter, vol. 8(2), pages 111-128, December.
    3. Pierre L’Ecuyer & Bruno Tuffin, 2011. "Approximating zero-variance importance sampling in a reliability setting," Annals of Operations Research, Springer, vol. 189(1), pages 277-297, September.
    4. Dassios, Angelos & Jang, Jiwook & Zhao, Hongbiao, 2015. "A risk model with renewal shot-noise Cox process," Insurance: Mathematics and Economics, Elsevier, vol. 65(C), pages 55-65.
    5. Luis Rincón & David J. Santana, 2022. "Ruin Probability for Finite Erlang Mixture Claims Via Recurrence Sequences," Methodology and Computing in Applied Probability, Springer, vol. 24(3), pages 2213-2236, September.
    6. Kaynar, Bahar & Ridder, Ad, 2010. "The cross-entropy method with patching for rare-event simulation of large Markov chains," European Journal of Operational Research, Elsevier, vol. 207(3), pages 1380-1397, December.
    7. Yuguang Fan & Philip S. Griffin & Ross Maller & Alexander Szimayer & Tiandong Wang, 2017. "The Effects of Largest Claim and Excess of Loss Reinsurance on a Company’s Ruin Time and Valuation," Risks, MDPI, vol. 5(1), pages 1-27, January.
    8. Ad Ridder, 2004. "Importance Sampling Simulations of Markovian Reliability Systems using Cross Entropy," Tinbergen Institute Discussion Papers 04-018/4, Tinbergen Institute.
    9. Martire, Antonio Luciano, 2022. "Volterra integral equations: An approach based on Lipschitz-continuity," Applied Mathematics and Computation, Elsevier, vol. 435(C).
    10. Hélène Cossette & Etienne Marceau & Quang Huy Nguyen & Christian Y. Robert, 2019. "Tail Approximations for Sums of Dependent Regularly Varying Random Variables Under Archimedean Copula Models," Methodology and Computing in Applied Probability, Springer, vol. 21(2), pages 461-490, June.
    11. Søren Asmussen & Dominik Kortschak, 2015. "Error Rates and Improved Algorithms for Rare Event Simulation with Heavy Weibull Tails," Methodology and Computing in Applied Probability, Springer, vol. 17(2), pages 441-461, June.
    12. Zdravko I. Botev & Robert Salomone & Daniel Mackinlay, 2019. "Fast and accurate computation of the distribution of sums of dependent log-normals," Annals of Operations Research, Springer, vol. 280(1), pages 19-46, September.
    13. Paulsen, Jostein & Kasozi, Juma & Steigen, Andreas, 2005. "A numerical method to find the probability of ultimate ruin in the classical risk model with stochastic return on investments," Insurance: Mathematics and Economics, Elsevier, vol. 36(3), pages 399-420, June.
    14. David J. Santana & Juan González-Hernández & Luis Rincón, 2017. "Approximation of the Ultimate Ruin Probability in the Classical Risk Model Using Erlang Mixtures," Methodology and Computing in Applied Probability, Springer, vol. 19(3), pages 775-798, September.
    15. Bahar Kaynar & Ad Ridder, 2009. "The Cross-Entropy Method with Patching for Rare-Event Simulation of Large Markov Chains," Tinbergen Institute Discussion Papers 09-084/4, Tinbergen Institute.
    16. Tamturk, Muhsin & Utev, Sergey, 2018. "Ruin probability via Quantum Mechanics Approach," Insurance: Mathematics and Economics, Elsevier, vol. 79(C), pages 69-74.
    17. Karthyek R. A. Murthy & Sandeep Juneja & Jose Blanchet, 2012. "State-independent Importance Sampling for Random Walks with Regularly Varying Increments," Papers 1206.3390, arXiv.org, revised Sep 2014.
    18. Søren Asmussen & Reuven Y. Rubinstein, 1999. "Sensitivity Analysis of Insurance Risk Models via Simulation," Management Science, INFORMS, vol. 45(8), pages 1125-1141, August.
    19. Coulibaly, Ibrahim & Lefèvre, Claude, 2008. "On a simple quasi-Monte Carlo approach for classical ultimate ruin probabilities," Insurance: Mathematics and Economics, Elsevier, vol. 42(3), pages 935-942, June.
    20. Nam Kyoo Boots & Perwez Shahabuddin, 2001. "Simulating Tail Probabilities in GI/GI.1 Queues and Insurance Risk Processes with Subexponentail Distributions," Tinbergen Institute Discussion Papers 01-012/4, Tinbergen Institute.

    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:oropre:v:49:y:2001:i:6:p:900-912. 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.