Modular Runtime Complexity Analysis of Probabilistic While Programs
Martin Avanzini, Schaper, Michael, Georg Moser · arXiv (Cornell University) · 2019
We are concerned with the average case runtime complexity analysis of a prototypical imperative language endowed with primitives for sampling and probabilistic choice. Taking inspiration from known approaches from to the modular resource analysis of non-probabilistic programs, we investigate how a modular runtime analysis is obtained for probabilistic programs.