Probabilistic Recurrence Relations

TitleProbabilistic Recurrence Relations
Publication TypeTechnical Report
Year of Publication1991
AuthorsKarp, R. M.
Other Numbers649

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),ldots,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.

Bibliographic Notes

ICSI Technical Report TR-91-019

Abbreviated Authors

R. M. Karp

ICSI Publication Type

Technical Report