Probabilistic Recurrence Relations
Title | Probabilistic Recurrence Relations |
Publication Type | Technical Report |
Year of Publication | 1991 |
Authors | Karp, R. M. |
Other Numbers | 649 |
Abstract | 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. |
URL | http://www.icsi.berkeley.edu/pubs/techreports/tr-91-019.pdf |
Bibliographic Notes | ICSI Technical Report TR-91-019 |
Abbreviated Authors | R. M. Karp |
ICSI Publication Type | Technical Report |