The Best of Times, the Worst of Times: Moment-Based Analysis of Probabilistic Cost Structures

Chenyu Zhou, Di Wang, Thomas Reps

This paper studies how to compute the moments -- mean, variance, and beyond -- of the cost (e.g., running time) of certain probabilistic programs, in which local costs combine not…