The Experts below are selected from a list of 1830 Experts worldwide ranked by ideXlab platform
Krishnendu Chatterjee - One of the best experts on this subject based on the ideXlab platform.
-
algorithmic analysis of qualitative and quantitative termination problems for affine probabilistic programs
ACM Transactions on Programming Languages and Systems, 2018Co-Authors: Krishnendu Chatterjee, Petr Novotný, Rouzbeh HasheminezhadAbstract:In this article, we consider the termination problem of probabilistic programs with real-valued variables. The questions concerned are: qualitative ones that ask (i) whether the program terminates with probability 1 (almost-sure termination) and (ii) whether the expected termination time is finite (finite termination); and quantitative ones that ask (i) to approximate the expected termination time (expectation problem) and (ii) to compute a bound B such that the probability not to terminate after B steps decreases exponentially (concentration problem). To solve these questions, we utilize the notion of ranking Supermartingales, which is a powerful approach for proving termination of probabilistic programs. In detail, we focus on algorithmic synthesis of linear ranking-Supermartingales over affine probabilistic programs (Apps) with both angelic and demonic non-determinism. An important subclass of Apps is LRApp which is defined as the class of all Apps over which a linear ranking-Supermartingale exists. Our main contributions are as follows. Firstly, we show that the membership problem of LRApp (i) can be decided in polynomial time for Apps with at most demonic non-determinism, and (ii) is NP-hard and in PSPACE for Apps with angelic non-determinism. Moreover, the NP-hardness result holds already for Apps without probability and demonic non-determinism. Secondly, we show that the concentration problem over LRApp can be solved in the same complexity as for the membership problem of LRApp. Finally, we show that the expectation problem over LRApp can be solved in 2EXPTIME and is PSPACE-hard even for Apps without probability and non-determinism (i.e., deterministic programs). Our experimental results demonstrate the effectiveness of our approach to answer the qualitative and quantitative questions over Apps with at most demonic non-determinism.
-
Termination of Nondeterministic Recursive Probabilistic Programs
arXiv: Programming Languages, 2017Co-Authors: Krishnendu ChatterjeeAbstract:We study the termination problem for nondeterministic recursive probabilistic programs. First, we show that a ranking-Supermartingales-based approach is both sound and complete for bounded terminiation (i.e., bounded expected termination time over all schedulers). Our result also clarifies previous results which claimed that ranking Supermartingales are not a complete approach even for nondeterministic probabilistic programs without recursion. Second, we show that conditionally difference-bounded ranking Supermartingales provide a sound approach for lower bounds of expected termination time. Finally, we show that Supermartingales with lower bounds on conditional absolute difference provide a sound approach for almost-sure termination, along with explicit bounds on tail probabilities of nontermination within a given number of steps. We also present several illuminating counterexamples that establish the necessity of certain prerequisites (such as conditionally difference-bounded condition).
-
POPL - Stochastic invariants for probabilistic termination
Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages - POPL 2017, 2017Co-Authors: Krishnendu Chatterjee, Petr Novotný, Ðorđe Žikelić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.
-
Stochastic Invariants for Probabilistic Termination
arXiv: Programming Languages, 2016Co-Authors: Krishnendu Chatterjee, Petr Novotný, Đorđe Žikelić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.
-
CAV (1) - Termination Analysis of Probabilistic Programs Through Positivstellensatz’s
Computer Aided Verification, 2016Co-Authors: Krishnendu Chatterjee, Amir Kafshdar GoharshadyAbstract:We consider nondeterministic probabilistic programs with the most basic liveness property of termination. We present efficient methods for termination analysis of nondeterministic probabilistic programs with polynomial guards and assignments. Our approach is through synthesis of polynomial ranking Supermartingales, that on one hand significantly generalizes linear ranking Supermartingales and on the other hand is a counterpart of polynomial ranking-functions for proving termination of nonprobabilistic programs. The approach synthesizes polynomial ranking-Supermartingales through Positivstellensatz’s, yielding an efficient method which is not only sound, but also semi-complete over a large subclass of programs. We show experimental results to demonstrate that our approach can handle several classical programs with complex polynomial guards and assignments, and can synthesize efficient quadratic ranking-Supermartingales when a linear one does not exist even for simple affine programs.
Abdelkarem Berkaoui - One of the best experts on this subject based on the ideXlab platform.
-
On representations of the set of Supermartingale measures and applications in continuous time
Stochastics, 2018Co-Authors: Abdelkarem BerkaouiAbstract:In a continuous time setting, we consider a set of -absolutely continuous probability measures, containing at least one equivalent to , and denote by , the smallest m-stable closed convex set of probability measures containing . We shall prove mainly under the martingale representation property with respect to a continuous vector valued martingale S, that is the set of Supermartingale measures for a family , where is a set of predictable vector valued processes. We state as an immediate consequence of Follmer-Kramkov Theorem in H. Follmer and D. Kramkov (Optional decompositions under constraints, Probab. Theory Relat. Fields 109 (1997), pp. 1–25), the decomposition of -Supermartingales.
-
On representations of the set of Supermartingale measures and applications in discrete time
Arabian Journal of Mathematics, 2017Co-Authors: Abdelkarem BerkaouiAbstract:We investigate some new results concerning the m-stability property. We show in particular under the martingale representation property with respect to a bounded martingale S that an m-stable set of probability measures is the set of Supermartingale measures for a family of discrete integral processes with respect to S. Open image in new window
-
On representations of the set of Supermartingale measures and applications in discrete time
Arabian Journal of Mathematics, 2017Co-Authors: Abdelkarem BerkaouiAbstract:We investigate some new results concerning the m-stability property. We show in particular under the martingale representation property with respect to a bounded martingale S that an m-stable set of probability measures is the set of Supermartingale measures for a family of discrete integral processes with respect to S .
Xiaolu Tan - One of the best experts on this subject based on the ideXlab platform.
-
A general Doob-Meyer-Mertens decomposition for g-Supermartingale systems
Electronic Journal of Probability, 2016Co-Authors: Bruno Bouchard, Dylan Possamaï, Xiaolu TanAbstract:We provide a general Doob-Meyer decomposition for $g$-Supermartingale systems, which does not require any right-continuity on the system. In particular, it generalizes the Doob-Meyer decomposition of Mertens (1972) for classical Supermartingales, as well as Peng's (1999) version for right-continuous $g$-Supermartingales. As examples of application, we prove an optional decomposition theorem for $g$-Supermartingale systems, and also obtain a general version of the well-known dual formation for BSDEs with constraint on the gains-process, using very simple arguments.
-
A general Doob-Meyer-Mertens decomposition for g-Supermartingale systems
Electronic Journal of Probability, 2016Co-Authors: Bruno Bouchard, Dylan Possamaï, Xiaolu TanAbstract:International audienceWe provide a general Doob-Meyer decomposition for g-Supermartingale systems, which does not require any right-continuity on the system, nor that the filtration is quasi left-continuous. In particular, it generalizes the Doob-Meyer decomposition of Mertens [35] for classical Supermartingales, as well as Peng's [40] version for right-continuous g-Supermartingales. As examples of application, we prove an optional decomposition theorem for g-Supermartingale systems, and also obtain a general version of the well-known dual formation for BSDEs with constraint on the gains-process, using very simple arguments
-
A general Doob-Meyer-Mertens decomposition for g-Supermartingale systems
Electronic Journal of Probability, 2016Co-Authors: Bruno Bouchard, Dylan Possamaï, Xiaolu TanAbstract:We provide a general Doob-Meyer decomposition for g-Supermartingale systems, which does not require any right-continuity on the system, nor that the filtration is quasi left-continuous. In particular, it generalizes the Doob-Meyer decomposition of Mertens [35] for classical Supermartingales, as well as Peng's [40] version for right-continuous g-Supermartingales. As examples of application, we prove an optional decomposition theorem for g-Supermartingale systems, and also obtain a general version of the well-known dual formation for BSDEs with constraint on the gains-process, using very simple arguments.
Gianluca Cassese - One of the best experts on this subject based on the ideXlab platform.
-
Quasimartingales with a linearly ordered index set
Statistics and Probability Letters, 2010Co-Authors: Gianluca CasseseAbstract:We consider quasi-martingales indexed by a linearly order set. We show that such processes are isomorphic to a given class of (finitely additive) measures. From this result we easily derive the classical theorem of Stricker as well as the decompositions of Riesz, Rao and the Supermartingale decomposition of Doob and Meyer.
-
Supermartingale decomposition with a general index set
Stochastic Processes and their Applications, 2010Co-Authors: Gianluca CasseseAbstract:We prove results on the existence of Doleans-Dade measures and of the Doob-Meyer decomposition for Supermartingales indexed by a general index set.
-
Finitely Additive Supermartingales
arXiv: Probability, 2008Co-Authors: Gianluca CasseseAbstract:The concept of finitely additive Supermartingales, originally due to Bochner, is revived and developed. We exploit it to study measure decompositions over filtered probability spaces and the properties of the associated Dol\'{e}ans-Dade measure. We obtain versions of the Doob Meyer decomposition and, as an application, we establish a version of the Bichteler and Dellacherie theorem with no exogenous probability measure.
-
Decomposition of Supermartingales indexed by a linearly ordered set
Statistics & Probability Letters, 2007Co-Authors: Gianluca CasseseAbstract:We prove a version of the Doob Meyer decomposition for Supermartingales with a linearly ordered index set.
Yuhu Feng - One of the best experts on this subject based on the ideXlab platform.
-
Semi-order fuzzy Supermartingales and submartingales with continuous time
Fuzzy Sets and Systems, 2002Co-Authors: Yuhu Feng, Xinglong ZhuAbstract:A new suitable semi-order in the fuzzy number space (En, D), the semi-order fuzzy Supermartingales and submartingales with continuous time and their characteristics are introduced. The famous Riesz decomposition and Doob-Meyer decomposition theorems in standard martingale theory are generalized to semi-order fuzzy Supermartingales. The proof of Doob-Meyer decomposition is rather technical and so the theory of fuzzy-valued measures generated by increasing fuzzy processes is developed.
-
Decomposition theorems for fuzzy Supermartingales and submartingales
Fuzzy Sets and Systems, 2000Co-Authors: Yuhu FengAbstract:Doob decomposition and Riesz decomposition theorems in standard martingale theory are generalized to fuzzy martingales. The concepts of two types of Riesz decomposition for fuzzy Supermartingales are given and the necessary and sufficient conditions of that fuzzy Supermartingale or submartingale (resp. Supermartingale) has Doob decomposition (resp. Riesz decomposition) are discussed in detail.
