Scholarlink

The computational complexity of a probabilistic program C is traditionally measured by the expected values of certain random variables defined over the runs of C. However, in some cases, this approach may lead to misleading conclusions about the actual runtime behavior of the program. Furthermore, the analysis of expected values is not compositional in general. In this paper, we propose alternative complexity measures for probabilistic programs that overcome some of these difficulties.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Asymptotic Analysis of Probabilistic Programs: When Expectations Do Not Meet Our Expectations

  • 章节

  • 发表日期：

    2025年

查看全文
  • Michal Ajdarów,
  • Antonín Kučera,
  • Petr Novotný

摘要

The computational complexity of a probabilistic program C is traditionally measured by the expected values of certain random variables defined over the runs of C. However, in some cases, this approach may lead to misleading conclusions about the actual runtime behavior of the program. Furthermore, the analysis of expected values is not compositional in general. In this paper, we propose alternative complexity measures for probabilistic programs that overcome some of these difficulties.