Stochastic Invariants for Probabilistic Termination

CHATTERJEE, Krishnendu, Petr NOVOTNÝ and Djordje ŽIKELIĆ. Stochastic Invariants for Probabilistic Termination. In Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages (POPL). New York, NY, USA: ACM, 2017, p. 145-160. ISSN 0362-1340. Available from: https://dx.doi.org/10.1145/3009837.3009873.

Basic information

• Original name: Stochastic Invariants for Probabilistic Termination
• Authors: CHATTERJEE, Krishnendu, Petr NOVOTNÝ and Djordje ŽIKELIĆ.
• Edition: New York, NY, USA, Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages (POPL), p. 145-160, 16 pp. 2017.
• Publisher: ACM

Other information

• Original language: English
• Type of outcome: Proceedings paper
• Confidentiality degree: is not subject to a state or trade secret
• Impact factor: Impact factor: 0.335 in 2016
• ISSN: 0362-1340
• Doi: http://dx.doi.org/10.1145/3009837.3009873
• UT WoS: 000408311200013
• Keywords in English: Probabilistic Programs; Termination; Martingales; Concentration
• Tags: International impact, Reviewed

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, and this problem has not been addressed yet. A fundamental and conceptual drawback of the existing approaches to address probabilistic termination is that even though the supermartingales consider the probabilistic behaviour of the programs, the invariants are obtained completely ignoring the probabilistic aspect (i.e., the invariants are obtained considering all behaviours with no information about the probability). In this work we address the probabilistic termination problem for linear-arithmetic probabilistic programs with nondeterminism. We formally define the notion of stochastic invariants, which are constraints along with a probability bound that the constraints hold. We introduce a concept of 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. Along with our conceptual contributions, we establish the following computational results: First, the synthesis of a stochastic invariant which supports some ranking supermartingale and at the same time admits a repulsing supermartingale can be achieved via reduction to the existential first-order theory of reals, which generalizes existing results from the non-probabilistic setting. Second, given a program with "strict invariants" (e.g., obtained via abstract interpretation) and a stochastic invariant, we can check in polynomial time whether there exists a linear repulsing supermartingale w.r.t. the stochastic invariant (via reduction to LP). We also present experimental evaluation of our approach on academic examples.