2012/01/25 by Cyrille Jégourel, Jégourel, Cyrille, Axel Legay +3 · 3 citations
Computer Science · Decision Sciences · Engineering · Mathematics · #Computation (stat.CO) #Computational Engineering #FOS: Computer and information sciences #FOS: Electrical engineering #Finance #Performance (cs.PF) #Probabilistic and Robust Engineering Design #Reliability and Maintenance Optimization #Software Reliability and Analysis Research #Statistical Distribution Estimation and Applications #Systems and Control (eess.SY) #and Science (cs.CE) #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.1201.5229
openalex publication_date 2012/01/25 · openalex created_date 2022/10/03 · openalex updated_date 2026/07/28
Statistical model checking avoids the exponential growth of states associated\nwith probabilistic model checking by estimating properties from multiple\nexecutions of a system and by giving results within confidence bounds. Rare\nproperties are often very important but pose a particular challenge for\nsimulation-based approaches, hence a key objective under these circumstances is\nto reduce the number and length of simulations necessary to produce a given\nlevel of confidence. Importance sampling is a well-established technique that\nachieves this, however to maintain the advantages of statistical model checking\nit is necessary to find good importance sampling distributions without\nconsidering the entire state space.\n Motivated by the above, we present a simple algorithm that uses the notion of\ncross-entropy to find the optimal parameters for an importance sampling\ndistribution. In contrast to previous work, our algorithm uses a low\ndimensional vector of parameters to define this distribution and thus avoids\nthe often intractable explicit representation of a transition matrix. We show\nthat our parametrisation leads to a unique optimum and can produce many orders\nof magnitude improvement in simulation efficiency. We demonstrate the efficacy\nof our methodology by applying it to models from reliability engineering and\nbiochemistry.\n