Hypothesis testing for rare-event simulation: limitations and possibilities

D.P. Reijsbergen; Pieter-Tjerk de Boer; Willem R.W. Scheinhardt

doi:10.1007/978-3-319-47166-2_2

Hypothesis testing for rare-event simulation: limitations and possibilities

D.P. Reijsbergen, Pieter-Tjerk de Boer, Willem R.W. Scheinhardt

Stochastic Operations Research

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Academic › peer-review

3 Citations (Scopus)

5 Downloads (Pure)

Abstract

One of the main applications of probabilistic model checking is to decide whether the probability of a property of interest is above or below a threshold. Using statistical model checking (SMC), this is done using a combination of stochastic simulation and statistical hypothesis testing. When the probability of interest is very small, one may need to resort to rare-event simulation techniques, in particular importance sampling (IS). However, IS simulation does not yield 0/1-outcomes, as assumed by the hypothesis tests commonly used in SMC, but likelihood ratios that are typically close to zero, but which may also take large values. In this paper we consider two possible ways of combining IS and SMC. One involves a classical IS-scheme from the rare-event simulation literature that yields likelihood ratios with bounded support when applied to a certain (nontrivial) class of models. The other involves a particular hypothesis testing scheme that does not require a-priori knowledge about the samples, only that their variance is estimated well.

Original language	English
Title of host publication	Leveraging Applications of Formal Methods, Verification and Validation: Foundational Techniques
Subtitle of host publication	7th International Symposium, ISoLA 2016, Imperial, Corfu, Greece, October 10–14, 2016, Proceedings, Part I
Editors	Tiziana Margaria, Bernhard Steffen
Publisher	Springer
Pages	16-26
Number of pages	11
ISBN (Electronic)	978-3-319-47166-2
ISBN (Print)	978-3-319-47165-5
DOIs	https://doi.org/10.1007/978-3-319-47166-2_2
Publication status	Published - 10 Oct 2016
Event	7th International Symposium on Leveraging Applications of Formal Methods, Verification and Validation, ISoLA 2016 - Corfu, Greece Duration: 10 Oct 2016 → 14 Oct 2016 Conference number: 7 http://www.isola-conference.org/isola2016/

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	9952
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	7th International Symposium on Leveraging Applications of Formal Methods, Verification and Validation, ISoLA 2016
Abbreviated title	ISoLA 2016
Country/Territory	Greece
City	Corfu
Period	10/10/16 → 14/10/16
Internet address	http://www.isola-conference.org/isola2016/

Keywords

IR-103348
EC Grant Agreement nr.: FP7/318490
METIS-321693
EC Grant Agreement nr.: FP7/600708
EWI-27678

Access to Document

10.1007/978-3-319-47166-2_2

http://dx.doi.org/10.1007/978-3-319-47166-2_2

Cite this

Reijsbergen, D. P., de Boer, P.-T., & Scheinhardt, W. R. W. (2016). Hypothesis testing for rare-event simulation: limitations and possibilities. In T. Margaria, & B. Steffen (Eds.), Leveraging Applications of Formal Methods, Verification and Validation: Foundational Techniques: 7th International Symposium, ISoLA 2016, Imperial, Corfu, Greece, October 10–14, 2016, Proceedings, Part I (pp. 16-26). (Lecture Notes in Computer Science; Vol. 9952). Springer. https://doi.org/10.1007/978-3-319-47166-2_2

Reijsbergen, D.P. ; de Boer, Pieter-Tjerk ; Scheinhardt, Willem R.W. / Hypothesis testing for rare-event simulation : limitations and possibilities. Leveraging Applications of Formal Methods, Verification and Validation: Foundational Techniques: 7th International Symposium, ISoLA 2016, Imperial, Corfu, Greece, October 10–14, 2016, Proceedings, Part I. editor / Tiziana Margaria ; Bernhard Steffen. Springer, 2016. pp. 16-26 (Lecture Notes in Computer Science).

@inbook{6b21d4377f164dbda1403bcc858c6264,

title = "Hypothesis testing for rare-event simulation: limitations and possibilities",

abstract = "One of the main applications of probabilistic model checking is to decide whether the probability of a property of interest is above or below a threshold. Using statistical model checking (SMC), this is done using a combination of stochastic simulation and statistical hypothesis testing. When the probability of interest is very small, one may need to resort to rare-event simulation techniques, in particular importance sampling (IS). However, IS simulation does not yield 0/1-outcomes, as assumed by the hypothesis tests commonly used in SMC, but likelihood ratios that are typically close to zero, but which may also take large values. In this paper we consider two possible ways of combining IS and SMC. One involves a classical IS-scheme from the rare-event simulation literature that yields likelihood ratios with bounded support when applied to a certain (nontrivial) class of models. The other involves a particular hypothesis testing scheme that does not require a-priori knowledge about the samples, only that their variance is estimated well.",

keywords = "IR-103348, EC Grant Agreement nr.: FP7/318490, METIS-321693, EC Grant Agreement nr.: FP7/600708, EWI-27678",

author = "D.P. Reijsbergen and {de Boer}, Pieter-Tjerk and Scheinhardt, {Willem R.W.}",

note = "This work is partially supported by the EU projects SENSATION, 318490, and QUANTICOL, 600708.; 7th International Symposium on Leveraging Applications of Formal Methods, Verification and Validation, ISoLA 2016, ISoLA 2016 ; Conference date: 10-10-2016 Through 14-10-2016",

year = "2016",

month = oct,

day = "10",

doi = "10.1007/978-3-319-47166-2_2",

language = "English",

isbn = "978-3-319-47165-5",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "16--26",

editor = "Tiziana Margaria and Bernhard Steffen",

booktitle = "Leveraging Applications of Formal Methods, Verification and Validation: Foundational Techniques",

address = "Germany",

url = "http://www.isola-conference.org/isola2016/",

}

Reijsbergen, DP, de Boer, P-T & Scheinhardt, WRW 2016, Hypothesis testing for rare-event simulation: limitations and possibilities. in T Margaria & B Steffen (eds), Leveraging Applications of Formal Methods, Verification and Validation: Foundational Techniques: 7th International Symposium, ISoLA 2016, Imperial, Corfu, Greece, October 10–14, 2016, Proceedings, Part I. Lecture Notes in Computer Science, vol. 9952, Springer, pp. 16-26, 7th International Symposium on Leveraging Applications of Formal Methods, Verification and Validation, ISoLA 2016, Corfu, Greece, 10/10/16. https://doi.org/10.1007/978-3-319-47166-2_2

Hypothesis testing for rare-event simulation: limitations and possibilities. / Reijsbergen, D.P.; de Boer, Pieter-Tjerk ; Scheinhardt, Willem R.W.
Leveraging Applications of Formal Methods, Verification and Validation: Foundational Techniques: 7th International Symposium, ISoLA 2016, Imperial, Corfu, Greece, October 10–14, 2016, Proceedings, Part I. ed. / Tiziana Margaria; Bernhard Steffen. Springer, 2016. p. 16-26 (Lecture Notes in Computer Science; Vol. 9952).

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Academic › peer-review

TY - CHAP

T1 - Hypothesis testing for rare-event simulation

T2 - 7th International Symposium on Leveraging Applications of Formal Methods, Verification and Validation, ISoLA 2016

AU - Reijsbergen, D.P.

AU - de Boer, Pieter-Tjerk

AU - Scheinhardt, Willem R.W.

N1 - Conference code: 7

PY - 2016/10/10

Y1 - 2016/10/10

N2 - One of the main applications of probabilistic model checking is to decide whether the probability of a property of interest is above or below a threshold. Using statistical model checking (SMC), this is done using a combination of stochastic simulation and statistical hypothesis testing. When the probability of interest is very small, one may need to resort to rare-event simulation techniques, in particular importance sampling (IS). However, IS simulation does not yield 0/1-outcomes, as assumed by the hypothesis tests commonly used in SMC, but likelihood ratios that are typically close to zero, but which may also take large values. In this paper we consider two possible ways of combining IS and SMC. One involves a classical IS-scheme from the rare-event simulation literature that yields likelihood ratios with bounded support when applied to a certain (nontrivial) class of models. The other involves a particular hypothesis testing scheme that does not require a-priori knowledge about the samples, only that their variance is estimated well.

AB - One of the main applications of probabilistic model checking is to decide whether the probability of a property of interest is above or below a threshold. Using statistical model checking (SMC), this is done using a combination of stochastic simulation and statistical hypothesis testing. When the probability of interest is very small, one may need to resort to rare-event simulation techniques, in particular importance sampling (IS). However, IS simulation does not yield 0/1-outcomes, as assumed by the hypothesis tests commonly used in SMC, but likelihood ratios that are typically close to zero, but which may also take large values. In this paper we consider two possible ways of combining IS and SMC. One involves a classical IS-scheme from the rare-event simulation literature that yields likelihood ratios with bounded support when applied to a certain (nontrivial) class of models. The other involves a particular hypothesis testing scheme that does not require a-priori knowledge about the samples, only that their variance is estimated well.

KW - IR-103348

KW - EC Grant Agreement nr.: FP7/318490

KW - METIS-321693

KW - EC Grant Agreement nr.: FP7/600708

KW - EWI-27678

U2 - 10.1007/978-3-319-47166-2_2

DO - 10.1007/978-3-319-47166-2_2

M3 - Chapter

SN - 978-3-319-47165-5

T3 - Lecture Notes in Computer Science

SP - 16

EP - 26

BT - Leveraging Applications of Formal Methods, Verification and Validation: Foundational Techniques

A2 - Margaria, Tiziana

A2 - Steffen, Bernhard

PB - Springer

Y2 - 10 October 2016 through 14 October 2016

ER -

Reijsbergen DP, de Boer PT , Scheinhardt WRW. Hypothesis testing for rare-event simulation: limitations and possibilities. In Margaria T, Steffen B, editors, Leveraging Applications of Formal Methods, Verification and Validation: Foundational Techniques: 7th International Symposium, ISoLA 2016, Imperial, Corfu, Greece, October 10–14, 2016, Proceedings, Part I. Springer. 2016. p. 16-26. (Lecture Notes in Computer Science). doi: 10.1007/978-3-319-47166-2_2

Hypothesis testing for rare-event simulation: limitations and possibilities

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this