Fixed points of the smoothing transform: two-sided solutions

Given a sequence (C, T) = (C, T (1), T (2), . . .) of real-valued random variables with T (j) a parts per thousand yen 0 for all j a parts per thousand yen 1 and almost surely finite N = sup{j a parts per thousand yen 1 : T (j) > 0}, the smoothing transform associated with (C, T), defined on the set of probability distributions on the real line, maps an element to the law of , where X (1), X (2), . . . is a sequence of i.i.d. random variables independent of (C, T) and with distribution P. We study the fixed points of the smoothing transform, that is, the solutions to the stochastic fixed-point equation . By drawing on recent work by the authors with J.D. Biggins, a full description of the set of solutions is provided under weak assumptions on the sequence (C, T). This solves problems posed by Fill and Janson (Electron Commun Probab 5:77-84, 2000) and Aldous and Bandyopadhyay (Ann Appl Probab 15(2):1047-1110, 2005). Our results include precise characterizations of the sets of solutions to large classes of stochastic fixed-point equations that appear in the asymptotic analysis of divide-and-conquer algorithms, for instance the equation.