  Analyzing probabilistic programs and randomized algorithms are classical
problems in computer science. The first basic problem in the analysis of
stochastic processes is to consider the expectation or mean, and another basic
problem is to consider concentration bounds, i.e. showing that large deviations
from the mean have small probability. Similarly, in the context of
probabilistic programs and randomized algorithms, the analysis of expected
termination time/running time and their concentration bounds are fundamental
problems.In this work, we focus on concentration bounds for probabilistic
programs and probabilistic recurrences of randomized algorithms. For
probabilistic programs, the basic technique to achieve concentration bounds is
to consider martingales and apply the classical Azuma's inequality. For
probabilistic recurrences of randomized algorithms, Karp's classical "cookbook"
method, which is similar to the master theorem for recurrences, is the standard
approach to obtain concentration bounds. In this work, we propose a novel
approach for deriving concentration bounds for probabilistic programs and
probabilistic recurrence relations through the synthesis of exponential
supermartingales. For probabilistic programs, we present algorithms for
synthesis of such supermartingales in several cases. We also show that our
approach can derive better concentration bounds than simply applying the
classical Azuma's inequality over various probabilistic programs considered in
the literature. For probabilistic recurrences, our approach can derive tighter
bounds than the Karp's well-established methods on classical algorithms.
Moreover, we show that our approach could derive bounds comparable to the
optimal bound for quicksort, proposed by McDiarmid and Hayward. We also present
a prototype implementation that can automatically infer these bounds
