Automated Tail Bound Analysis for Probabilistic Recurrence Relations

Yican Sun, Hongfei Fu, Krishnendu Chatterjee +1

Probabilistic recurrence relations (PRRs) are a standard formalism for describing the runtime of a randomized algorithm. Given a PRR and a time limit $\kappa$, we consider the classical…