  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 concept of tail probability $\Pr[T \ge
\kappa]$, i.e., the probability that the randomized runtime $T$ of the PRR
exceeds the time limit $\kappa$. Our focus is the formal analysis of tail
bounds that aims at finding a tight asymptotic upper bound $u \geq
\Pr[T\ge\kappa]$ in the time limit $\kappa$. To address this problem, the
classical and most well-known approach is the cookbook method by Karp (JACM
1994), while other approaches are mostly limited to deriving tail bounds of
specific PRRs via involved custom analysis.
  In this work, we propose a novel approach for deriving
exponentially-decreasing tail bounds (a common type of tail bounds) for PRRs
whose preprocessing time and random passed sizes observe discrete or
(piecewise) uniform distribution and whose recursive call is either a single
procedure call or a divide-and-conquer. We first establish a theoretical
approach via Markov's inequality, and then instantiate the theoretical approach
with a template-based algorithmic approach via a refined treatment of
exponentiation. Experimental evaluation shows that our algorithmic approach is
capable of deriving tail bounds that are (i) asymptotically tighter than Karp's
method, (ii) match the best-known manually-derived asymptotic tail bound for
QuickSelect, and (iii) is only slightly worse (with a $\log\log n$ factor) than
the manually-proven optimal asymptotic tail bound for QuickSort. Moreover, our
algorithmic approach handles all examples (including realistic PRRs such as
QuickSort, QuickSelect, DiameterComputation, etc.) in less than 0.1 seconds,
showing that our approach is efficient in practice.
