Estimating reliability measures for highly-dependable Markov systems, using balanced likelihood ratios

Over the past several years, importance sampling in conjunction with regenerative simulation has been presented as a promising method for estimating reliability measures in highly dependable Markov systems. Existing methods fail to provide benefits over crude Monte Carlo for analyzing systems that contain important component-redundancies. This paper presents refined importance-sampling techniques that are also based on the regenerative technique. The new methods use an importance-sampling plan that dynamically adjusts the transition probabilities of the embedded Markov chain by attempting to cancel terms of the likelihood ratio within each cycle. Additional improvements are induced by concentrating on events affecting the size of minimum system cuts. These methods have solid theoretical properties and work well in practice, as illustrated by several examples.