Abstract

In this work, we propose a stratified sampling method to statistically check Probabilistic Computation Tree Logic (PCTL) formulas on discrete-time Markov chains with sequential probability ratio test. Distinct from previous statistical verification methods using independent Monte Carlo sampling, our algorithm uses stratified samples that are negatively correlated, thus give lower variance. The experiments demonstrate that the new algorithm uses a smaller number of samples for a given confidence level on several benchmark examples.

Original languageEnglish (US)
Pages (from-to)85-90
Number of pages6
JournalIFAC-PapersOnLine
Volume51
Issue number16
DOIs
StatePublished - Jan 1 2018

    Fingerprint

Keywords

  • Markov chains
  • PRISM
  • Sequential probability ratio test
  • Temporal logic
  • Variance reduction

ASJC Scopus subject areas

  • Control and Systems Engineering

Cite this