Inferring Expected Runtimes of Probabilistic Integer Programs Using Expected Sizes

Fabian Meyer, Marcel Hark, Jürgen Giesl

We present a novel modular approach to infer upper bounds on the expected runtime of probabilistic integer programs automatically. To this end, it computes bounds on the runtime of…