The Solution of Linear Probabilistic Recurrence Relations

Linear probabilistic divide‐and‐conquer recurrence relations arise when analyzing the running time of divide‐and‐conquer randomized algorithms. We consider first the problem of finding the expected value of the random process T(x) , described as the output of a randomized recursive algorithm T . On input x , T generates a sample (h1,…,hk) from a given probability distribution on [0,1]k and recurses by returning g(x) + Σi=1kciT(hi x) until a constant is returned when x becomes less than a given number. Under some minor assumptions on the problem parameters, we present a closed‐form asymptotic solution of the expected value of T(x) . We show that E[T(x)] = Θ( xp + xp∈t1x(g(u)/ up+1 ) du) , where p is the nonnegative unique solution of the equation Σi=1kciE[hip] = 1 . This generalizes the result in [1] where we considered the deterministic version of the recurrence. Then, following [2], we argue that the solution holds under a broad class of perturbations including floors and ceilings that usually accompany the recurrences that arise when analyzing randomized divide‐and‐conquer algorithms.