Summary: This paper is concerned with recurrence relations that arise frequently in the analysis of divide-and-conquer algorithms. In order to solve a problem instance of size \(x\), such an algorithm invests an amount of work \(a(x)\) to break the problem into subproblems of sizes \(h_1(x),h_2(x),\dots, h_k(x)\), and then proceeds to solve the subproblems. Our particular interest is in the case where the sizes \(h_i(x)\) are random variables; this may occur either because of randomization within the algorithm or because the instances to be solved are assumed to be drawn from a probability distribution. When the \(h_i\) are random variables the running time of the algorithm on instances of size \(x\) is also a random variable \(T(x)\). We give several easy-to-apply methods for obtaining fairly tight bounds on the upper tails of the probability distribution of \(T(x)\), and present a number of typical applications of these bounds to the analysis of algorithms. The proofs of the bounds are based on an interesting analysis of optimal strategies in certain gambling games.