Concentration of Measure for the Analysis of Randomized Algorithms

4

Interlude: Probabilistic Recurrences

Karp [49] developed an attractive framework for the analysis of randomized algorithms. Suppose we have a randomized algorithm that, on input x, performs “work” a(x) and then produces a subproblem of size H(x), which is then solved by recursion. One can analyse the performance of the algorithm by writing down a “recurrence”:

(4.1)

Superficially this looks just the same as the usual analysis of algorithms via recurrence relations. However, the crucial difference is that in contrast with deterministic algorithms, the size of the subproblem produced here, H(x) is a random variable, and so (4.1) is a ...