Stochastic Invariants for Probabilistic Termination Conference Paper

Author(s): Chatterjee, Krishnendu; Novotný, Petr; Zikelic, Djordje
Title: Stochastic Invariants for Probabilistic Termination
Affiliation IST Austria
Abstract: Termination is one of the basic liveness properties, and we study the termination problem for probabilistic programs with real-valued variables. Previous works focused on the qualitative problem that asks whether an input program terminates with probability~1 (almost-sure termination). A powerful approach for this qualitative problem is the notion of ranking supermartingales with respect to a given set of invariants. The quantitative problem (probabilistic termination) asks for bounds on the termination probability. A fundamental and conceptual drawback of the existing approaches to address probabilistic termination is that even though the supermartingales consider the probabilistic behavior of the programs, the invariants are obtained completely ignoring the probabilistic aspect. In this work we address the probabilistic termination problem for linear-arithmetic probabilistic programs with nondeterminism. We define the notion of {\em stochastic invariants}, which are constraints along with a probability bound that the constraints hold. We introduce a concept of {\em repulsing supermartingales}. First, we show that repulsing supermartingales can be used to obtain bounds on the probability of the stochastic invariants. Second, we show the effectiveness of repulsing supermartingales in the following three ways: (1)~With a combination of ranking and repulsing supermartingales we can compute lower bounds on the probability of termination; (2)~repulsing supermartingales provide witnesses for refutation of almost-sure termination; and (3)~with a combination of ranking and repulsing supermartingales we can establish persistence properties of probabilistic programs. We also present results on related computational problems and an experimental evaluation of our approach on academic examples.
Keywords: termination; Martingales; Concentration; Probabilistic programs
Conference Title: POPL: Principles of Programming Languages
Conference Dates: January 15 - January 21, 2017
Conference Location: Paris
Publisher: ACM  
Date Published: 2017-01-01
Start Page: 145
End Page: 160
DOI: 10.1145/3009837.3009873
Notes: This research was partially supported by Austrian Science Fund (FWF) NFN Grant No S11407-N23 (RiSE/SHiNE), ERC Start grant (279307: Graph Games), and Vienna Science and Technology Fund (WWTF) through project ICT15-003. The research leading to these results has received funding from the People Programme (Marie Curie Actions) of the European Union’s Seventh Framework Programme (FP7/2007-2013) under REA grant agreement no [291734]. Ðorde Žikelic participated in this research during a research visit at IST Austria, funded by the OeAD Sonderstipendien, IST AUSTRIA programme awarded by the Austrian Agency for International Cooperation in Education and Research.
Open access: yes (repository)
IST Austria Authors
Related IST Austria Work