Expected-Cost Analysis for Probabilistic Programs and Semantics-Level Adaption of Optional Stopping Theorems

2021/03/30 by Wang, Di, Hoffmann, Jan, Reps, Thomas
#FOS: Computer and information sciences #Programming Languages (cs.PL)

paper · doi:10.48550/arxiv.2103.16105

Abstract

In this article, we present a semantics-level adaption of the Optional Stopping Theorem, sketch an expected-cost analysis as its application, and survey different variants of the Optional Stopping Theorem that have been used in static analysis of probabilistic programs.

Related

• Bounded Expectations: Resource Analysis for Probabilistic Programs
• Raising Expectations: Automating Expected Cost Analysis with Types
• An Iris for Expected Cost Analysis
• Cost Analysis of Nondeterministic Probabilistic Programs
• Denotational Foundations for Expected Cost Analysis