  In this paper we present a method for obtaining tail-bounds for random
variables satisfying certain probabilistic recurrences that arise in the
analysis of randomized parallel divide and conquer algorithms. In such
algorithms, some computation is initially done to process an input x, which is
then randomly split into subproblems $h_1(x), ..., h_n(x)$, and the algorithm
proceeds recursively in parallel on each subproblem. The total work on input x,
W(x), then satisfies a probabilistic recurrence of the form $W(x) = a(x) +
\sum_{i=1}^n W (h_i(x))$, and the span (the longest chain of sequential
dependencies), satisfies $S(x) = b(x) + \max_{i=1}^n S(h_i(x))$, where a(x) and
b(x) are the work and span to split x and combine the results of the recursive
calls.
  Karp has previously presented methods for obtaining tail-bounds in the case
when n = 1, and under certain stronger assumptions for the work-recurrence when
n > 1, but left open the question of the span-recurrence. We first show how to
extend his technique to handle the span-recurrence. We then show that in some
cases, the work-recurrence can be bounded under simpler assumptions than Karp's
by transforming it into a related span-recurrence and applying our first
result. We demonstrate our results by deriving tail bounds for the work and
span of quicksort and the height of a randomly generated binary search tree.
