Fixed points of the smoothing transform: two-sided solutions
By Gerold Alsmeyer, M. Meiners. Probability theory and related fields, 2010
64 citations recorded by the source corpus.
Given a sequence (C, T) = (C, T1, T2, . . .) of real-valued random variables with Tj ≥ 0 for all j ≥ 1 and almost surely finite N = sup{j ≥ 1 : Tj > 0}, the smoothing transform associated with (C, T), defined on the set \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal{P}(\mathbb R)}$$\end{document} of probability distributions on the real line, maps an element \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${P \in \mathcal{P}(\mathbb R)}$$\end{document} to the law of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${C + \sum_{j \geq 1} T_j X_j}$$\end{document} , where X1, X2, . . . 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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${X_{1} \stackrel {\mathrm{d}}{=}C + \sum_{j \geq 1} T_j X_j}$$\end{document} . 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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\tt Quicksort}$$\end{document} equation.
Subfields: Artificial Intelligence, Management Science and Operations Research
View Paper: https://www.semanticscholar.org/paper/ba9bf13ac556caf9ee9d488e4709090123451253
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
In Management Science and Operations Research
Citations in the corpus
- Asymptotics for Weighted Random Sums (2011, background): “Such weighted random sums appear in the context of weighted branching processes and fixed-point equations of smoothing transforms (see [15, 12, 1]), and more recently, in the analysis of information ranking algorithms, e.”