Statistical verification of PCTL using stratified samples

Y. Wang, N. Roohi, M. West, M. Viswanathan, and G. E. Dullerud

in Proceedings of the 6th IFAC Conference on Analysis and Design of Hybrid Systems (ADHS 2018), 2018.

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.

DOI: 10.1016/j.ifacol.2018.08.015

Full text: WaRoWeViDu2018.pdf