Fixed points of the smoothing transform: Two-sided solutions

Given a sequence $(C,T)=(C,T_1,T_2,\mathrm{.}\mathrm{.}\mathrm{.})$ of real-valued random variables with $T_j\ge 0$ for all $j\ge 1$ and almost surely finite $N = \sup{j \geq 1: T_j > 0}$,thesmoothingtransformassociatedwith$(C,T)$, defined on the set $\mathcal{P}(\mathbb{R})$ of probability distributions on the real line, maps an element $P\in \mathcal{P}(\mathbb{R})$ to the law of $C+{\sum }_{j\ge 1}{T}_j{X}_j$, where $X_1,X_2,\mathrm{.}\mathrm{.}\mathrm{.}$ 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 $X_{1}C+{\sum }_{j\ge 1}{T}_j{X}_j$. 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 \cite{FJ2000} and Aldous and Bandyopadhyay \cite{AB2005}. 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 $\mathtt{\text{Quicksort}}$ equation.