Probabilistic model checking is a powerful tool for analysing probabilistic systems but it can only be efficiently applied to Markov models. Monte Carlo simulation provides an alternative for the generality of stochastic processes, but becomes infeasible if the value to estimate depends on the occurrence of rare events. To combat this problem, intelligent simulation strategies exist to lower the estimation variance and hence reduce the simulation time. Importance splitting is one such technique, but requires a guiding function typically defined in an ad hoc fashion by an expert in the field. We present an automatic derivation of the importance function from the model description. A prototypical tool was developed and tested on several Markov models, compared to analytically and numerically calculated results and to results of typical ad hoc importance functions, showing the feasibility and efficiency of this approach. The technique is easily adapted to general models like GSMPs.

Rare Event Simulation with fully automated importance splitting / Budde, Carlos E.; D'Argenio, Pedro R.; Hermanns, Holger. - ELETTRONICO. - 9272:(2015), pp. 275-290. (Intervento presentato al convegno 12th European Performance Engineering Workshop, EPEW 2015 tenutosi a esp nel 2015) [10.1007/978-3-319-23267-6_18].

Rare Event Simulation with fully automated importance splitting

Carlos E. Budde;
2015-01-01

Abstract

Probabilistic model checking is a powerful tool for analysing probabilistic systems but it can only be efficiently applied to Markov models. Monte Carlo simulation provides an alternative for the generality of stochastic processes, but becomes infeasible if the value to estimate depends on the occurrence of rare events. To combat this problem, intelligent simulation strategies exist to lower the estimation variance and hence reduce the simulation time. Importance splitting is one such technique, but requires a guiding function typically defined in an ad hoc fashion by an expert in the field. We present an automatic derivation of the importance function from the model description. A prototypical tool was developed and tested on several Markov models, compared to analytically and numerically calculated results and to results of typical ad hoc importance functions, showing the feasibility and efficiency of this approach. The technique is easily adapted to general models like GSMPs.
2015
Proceedings of the 12th European Performance Engineering Workshop, EPEW 2015
Switzerland
Springer Verlag
978-3-319-23266-9
978-3-319-23267-6
Budde, Carlos E.; D'Argenio, Pedro R.; Hermanns, Holger
Rare Event Simulation with fully automated importance splitting / Budde, Carlos E.; D'Argenio, Pedro R.; Hermanns, Holger. - ELETTRONICO. - 9272:(2015), pp. 275-290. (Intervento presentato al convegno 12th European Performance Engineering Workshop, EPEW 2015 tenutosi a esp nel 2015) [10.1007/978-3-319-23267-6_18].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11572/314681
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 11
  • ???jsp.display-item.citation.isi??? 5
social impact