Approximating zero-variance importance sampling in a reliability setting

Pierre L’Ecuyer () and Bruno Tuffin ()

Annals of Operations Research, 2011, vol. 189, issue 1, 277-297

Abstract: We consider a class of Markov chain models that includes the highly reliable Markovian systems (HRMS) often used to represent the evolution of multicomponent systems in reliability settings. We are interested in the design of efficient importance sampling (IS) schemes to estimate the reliability of such systems by simulation. For these models, there is in fact a zero-variance IS scheme that can be written exactly in terms of a value function that gives the expected cost-to-go (the exact reliability, in our case) from any state of the chain. This IS scheme is impractical to implement exactly, but it can be approximated by approximating this value function. We examine how this can be effectively used to estimate the reliability of a highly-reliable multicomponent system with Markovian behavior. In our implementation, we start with a simple crude approximation of the value function, we use it in a first-order IS scheme to obtain a better approximation at a few selected states, then we interpolate in between and use this interpolation in our final (second-order) IS scheme. In numerical illustrations, our approach outperforms the popular IS heuristics previously proposed for this class of problems. We also perform an asymptotic analysis in which the HRMS model is parameterized in a standard way by a rarity parameter ε, so that the relative error (or relative variance) of the crude Monte Carlo estimator is unbounded when ε→0. We show that with our approximation, the IS estimator has bounded relative error (BRE) under very mild conditions, and vanishing relative error (VRE), which means that the relative error converges to 0 when ε→0, under slightly stronger conditions. Copyright Springer Science+Business Media, LLC 2011

Keywords: Monte Carlo; Rare events; Importance sampling (search for similar items in EconPapers)
Date: 2011
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10479-009-0532-5 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:189:y:2011:i:1:p:277-297:10.1007/s10479-009-0532-5

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-009-0532-5

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().