A Variance Reduction Technique for the Failure Probability Estimation

Abstract

We develop a variance reduction technique to estimate a small failure probability in an unreliable system with repairs. Since the probability of failure is considered to be small, it is natural to use the rare event simulation techniques in order to decrease the variance of the the estimator. For degradation process we proposed a combined method based on two approaches designed to rare events simulation: the standard conditional Monte Carlo method and the splitting technique.

Keywords

• Conditional Monte Carlo
• variance reduction
• failure probability
• splitting method

Introduction

In this work, we consider a variance reduction technique based on conditional Monte-Carlo method, which is based on the expression of desired quantity as conditional expectation given some auxiliary random variable. This method is highly e ective when we need to estimate a small probability of a rare event [ 8,7 ] and allows to considerable reduce variance of the estimate by the appropriate selection of an auxiliary variable.

In this work we apply a special case of this method based on an improved algorithm for rare event simulation suggested [ 1 ] for variance reduction when we deal with heavy-tailed distributions.

In this work we describe conditional Monte-Carlo method and illustrate it by an application to estimation a degradation process containing a few steps, in which a maintenance repair is applied to prevent a failure.

This problem has been addressed in [ 2 ], where we applied a standard splitting method to speed-up estimation of the failure probability. This model is highly motivated, and calculation of the failure probability and related stationary characteristics is critically important to evaluate quality of service and reliability of the system. It is worth mentioning that analytic methods as a rule are unavailable in the case of non-Markov processes and an e ective simulation only remains an e ective tool for the required estimating.

In this research, we present some simulation results to demonstrate an efciency of the variance reduction approach from [ 1 ] applied to the setting described above.

Now we shortly describe the model of the degradation process from [ 2 ], which is a random process X := fX(t); t 0g with a nite state space

E = f0; 1; : : : ; L; : : : ; M; : : : ; K; F g describing the degradation stages of the system.

As it is illustrated in Fig. 1 the process starts in state X(0) = 0 and crosses K 1 intermediate degradation states. When the process reaches the state M (it happens with probability 1), the following two scenarios are possible: i) the process X visits state K, where repair is performed during random time UK , then the process returns to stage L; ii) an instantaneous failure occurs if during a random time V (with given distribution) the process is still at some intermediate stage j 2 fM; : : : ; K 1g. As a result, the process X jumps to a complete failure state F . Then the system again is ready for work after a repair random time UF , with a given distribution. After repair, the process returns to initial state 0. We emphasize that structure of the degradation process is very convenient to application of the splitting method to speed-up estimation of the failure probability by simulation. For more details on the accelerated estimation of rare events by splitting method see [ 3,4,5,6 ].

Besides, in the work [ 2 ], we heavily exploit di erent regenerative structures of the degradation process. In particular, we have used the regeneration instants when the process hits the state M . Upon reaching state M , a failure may happen during random period V ; otherwise, a preventive repair occurs during time K 1 SM;K = X Ti; i=M where Ti is a random length of the i stage of degradation, with a given distribution. (Note that in general distribution of Ti may depend on the stage number i.)

As a result, we obtain two types of regeneration cycles of the degradation process X. Denote by YF the length of the regeneration cycle with a failure, and let YNF be the length of cycle with no failure. Thus (unconditional) regeneration cycle length Y is

Y = YF IfV SM;Kg + YNF IfSM;K<V g: where IA denotes indicator function. The variable Y plays an important role in the analysis of degradation process [ 2 ]. The main task is to nd the probability of instantaneous failure on the cycle pF = P(SM;K

V ): 2

Conditional Monte Carlo for the failure probability estimation In this section we restrict ourselves to the particular case of homogeneous degradation process when random variables Ti; i = 1; :::; K 1, which are identically distributed with the distribution function FT . In this framework one can apply an alternative approach, known as Conditional Monte Carlo.

In a nutshell, the target probability is expressed as a conditional expectation with respect to some auxiliary random variable. This method always leads to variance reduction [ 8,7 ]. Unfortunately, it is often impossible, or at least very di cult, to nd a suitable conditioning quantity. Hopefully, in our setting it turns out to be possible by the following approach suggested by [ 1 ]. To apply this approach, we write the target probability as pF = (K

M )E F T (max(V

SM;K 1; RM;K 1)) ; where F T = 1

F and Given the two sequences of samples

RM;K = max(TM ; :::; TK 1);

SM;K = TM + ::: + TK 1: fT (i) = (T M(i); :::; T K(i) 1); i = 1; :::; N g; (1) (2) (3) (4) (5) fV (i); i = 1; :::; N g; we are able to de ne the required estimator of pF as follows It has been shown in [ 1 ] that such an estimator has a bounded relative error (under some limitations on initial distributions). 3

Implementation of the splitting method for the degradation process We also treat the degradation process as a regenerative process and consider a modi cation of the splitting method [ 9 ] for speed-up estimation of failure probability pF .

As in the case of the conditional Monte Carlo method, the key problem for splitting is the randomness of the threshold value V . Note that the standard formulation of the problem for the accelerated splitting method implies the presence of a xed threshold V , the excess of which is a rare event.

But, due to the speci c structure of degradation process, the splitting technique is best suited (among the accelerated methods) to simulate regeneration cycles in a degrading system and allows to estimate several characteristics simultaneously in one run of the program. More speci cally, for a complete study of the degradation system behavior, we also need to evaluate the average length of regeneration cycle with and without failure; the mean (unconditional) cycle length; the asymptotic reliability function. The splitting method will handle this, whereas the conditional Monte Carlo method allows us to obtain the only estimate for the probability pF .

Nevertheless, experiments have shown that it is necessary to focus attention on the probability estimation problem, since it has the greatest relative error RE[pbF ] = pV ar[pbF ] :

Since failure is possible only after going to stage M , then we will split the process trajectory after stage M . The moment of splitting occurs at the time of regeneration i which corresponds to the moment of transition to stage M (see Fig.2).

At each level we generate Ri copies of the random variables (r.v.) Ti, M i K 1. So, each original path generates D = RM RK 1 (dependent) subpaths called group of cycles. The dependence is generated by the same pre-history of realizations of SMK before splitting point at each stage.

Thus, we obtain D realizations of SMK for one group of cycles. The cycles belonging to di erent groups are independent by construction. The total number of groups is denoted by RM 1. The total number of the failures in the ith group is

Ai = i D

X j=(i 1) D+1

I(j); i = 1; : : : ; RM 1; where indicator I(j) = 1 for the cycle with failure (I(j) = 0, otherwise), and the groups are i.i.d.

The following convergence follows from the regenerative properties of the sequence fI(j); j 1g:

Further, for the alternative construction of this estimator, we can apply the same algorithm as in section 2 using the formula (6). 4

Conclusions

In this paper, we consider a variance reduction technique developed in [ 1 ], and combine it with simulation technique based on the splitting of the trajectories, to accelerate estimation a small failure probability in a degradation process. We verify this approach by some simulation experiments for Weibull and Pareto Ti with uniform and exponential V .

ACKNOWLEDGEMENTS The study was carried out under state order to the Karelian Research Centre of the Russian Academy of Sciences (Institute of Applied Mathematical Research KarRC RAS) and supported by the Russian Foundation for Basic Research, projects 18-07-00187, 18-07-00147, 18-07-00156.

References

1. Asmussen , S. , Kroese , D.P. : Improved algorithms for rare event simulation with heavy tails . Advances in Applied Probability 38 , 545 { 558 ( 2006 )

2. Borodina , A.V. , Efrosinin , D.V. , Morozov , E.V. : Application of splitting to failure estimation in controllable degradation system . In: Communications in Computer and Information Science . vol. 700 , pp. 217 { 230 . Springer International Publishing ( 2017 ). https://doi.org/10.1007/978-3- 319 -66836-9, http://www.springer. com/gb/book/9783319668352

3. Garvels , M.: PhD Thesis . The splitting method in rare event simulation . The University of Twente, The Netherlands ( 2000 )

4. Glasserman , P. , Heidelberger , P. , Shahabuddin , P. , Zajic , T. : Splitting for rare event simulation: analysis of simple cases . In: Proceedings of the 1996 Winter Simulation Conference . pp. 302 { 308 ( 1996 )

5. Heegaard , P.E.: A survey of speedup simulation techniques . In: Workshop tutorial on Rare Event Simulation. Aachen, Germany . ( 1997 )

6. Heidelberger , P. : Fast simulation of rare events in queueing and reliability models . ACM Trans. Model. Comput. Simul . 5 ( 1 ), 43 {85 (Jan 1995 ). https://doi.org/10.1145/203091.203094, http://doi.acm. org/10 .1145/203091. 203094

7. Kroese , D.P. , Taimre , T. , Botev , Z.I. : Handbook of Monte Carlo Methods . John Wiley & Sons ( 2011 )

8. Ross , S.M. : Simulation. Elsevier ( 2006 )

9. Rubinstein , R.Y., Kroese , D.P. : Simulation and the Monte Carlo method . John Wiley & Sons, Inc., New Jersey ( 2017 )