Abstract
Given a sequence (C, T) = (C, T 1, T 2, . . .) of real-valued random variables with T j ≥ 0 for all j ≥ 1 and almost surely finite N = sup{j ≥ 1 : T j > 0}, the smoothing transform associated with (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 \geq 1} T_j X_j}\) , 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 \({X_{1} \stackrel {\mathrm{d}}{=}C + \sum_{j \geq 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 (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 \({\tt Quicksort}\) equation.
Article PDF
Similar content being viewed by others
References
Aldous D.J., Bandyopadhyay A.: A survey of max-type recursive distributional equations. Ann. Appl. Probab. 15(2), 1047–1110 (2005)
Alsmeyer, G., Biggins, J., Meiners, M.: The functional equation of the smoothing transform. Ann. Probab. Preprint. www.arXiv.org:0906.3133v2 (2010)
Alsmeyer G., Kuhlbusch D.: Double martingale structure and existence of \({\phi}\) -moments for weighted branching processes. Münster J. Math. 3, 163–212 (2010)
Alsmeyer G., Meiners M.: A min-type stochastic fixed-point equation related to the smoothing transformation. Theor. Stoch. Proc. 15(31), 19–41 (2009)
Alsmeyer, G., Meiners, M.: Fixed points of inhomogeneous smoothing transforms. J. Differ. Equ. Appl. doi:10.1080/10236198.2011.589514 (2010)
Alsmeyer G., Rösler U.: A stochastic fixed point equation related to weighted branching with deterministic weights. Electron. J. Probab. 11(2), 27–56 (2006)
Biggins J.D.: Martingale convergence in the branching random walk. J. Appl. Probab. 14(1), 25–37 (1977)
Biggins J.D.: Lindley-type equations in the branching random walk. Stoch. Proc. Appl. 75, 105–133 (1998)
Biggins J.D., Kyprianou A.E.: Seneta-Heyde norming in the branching random walk. Ann. Probab. 25(1), 337–360 (1997)
Biggins J.D., Kyprianou A.E.: Fixed points of the smoothing transform: the boundary case. Electron. J. Probab. 10(17), 609–631 (2005)
Bingham, N.H., Goldie, C.M., Teugels, J.L.: Regular variation. In: Encyclopedia of Mathematics and its Applications, vol. 27. Cambridge University Press, Cambridge (1989)
Caliebe A.: Symmetric fixed points of a smoothing transformation. Adv. Appl. Probab. 35(2), 377–394 (2003)
Caliebe A., Rösler U.: Fixed points with finite variance of a smoothing transformation. Stoch. Process. Appl. 107(1), 105–129 (2003)
Durrett R., Liggett T.M.: Fixed points of the smoothing transformation. Z. Wahrsch. Verw. Gebiete 64(3), 275–301 (1983)
Fill J.A., Janson S.: A characterization of the set of fixed points of the Quicksort transformation. Electron. Commun. Probab. 5, 77–84 (2000)
Gnedenko, B.V., Kolmogorov, A.N.: Limit distributions for sums of independent random variables. Translated from the Russian, annotated, and revised by K.L. Chung. With appendices by J.L. Doob and P. L. Hsu. Revised edition. Addison-Wesley Publishing Co., Reading (1968)
Gut, A.: Stopped random walks. Springer Series in Operations Research and Financial Engineering, 2nd edn
Hu Y., Shi Z.: Minimal position and critical martingale convergence in branching random walks, and directed polymers on disordered trees. Ann. Probab. 37(2), 742–789 (2009)
Iksanov A.M.: Elementary fixed points of the BRW smoothing transforms with infinite number of summands. Stoch. Process. Appl. 114(1), 27–50 (2004)
Jelenković, P., Olvera-Cravioto, M.: Implicit renewal theorem for trees with general weights. Preprint. www.arXiv.org:1012.2165v1 (2010)
Jelenković, P., Olvera-Cravioto, M.: Implicit renewal theory on trees. Preprint. www.arXiv.org:1006.3295 (2010)
Liu Q.: Fixed points of a generalized smoothing transformation and applications to the branching random walk. Adv. Appl. Probab. 30(1), 85–112 (1998)
Neininger, R., Rüschendorf, L.: Analysis of algorithms by the contraction method: additive and max-recursive sequences. Interacting Stochastic Systems, pp. 435–450 (2005)
Nerman O.: On the convergence of supercritical general (C-M-J) branching processes. Z. Wahrsch. Verw. Gebiete 57(3), 365–395 (1981)
Penrose M.D., Wade A.R.: On the total length of the random minimal directed spanning tree. Adv. Appl. Probab. 38(2), 336–372 (2006)
Rösler U.: A limit theorem for “Quicksort”. RAIRO Inform. Théor. Appl. 25(1), 85–100 (1991)
Rüschendorf L.: On stochastic recursive equations of sum and max type. J. Appl. Probab. 43(3), 687–703 (2006)
Samorodnitsky G., Taqqu M.S.: Stable Non-Gaussian Random Processes. Stochastic Modeling. Stochastic Models with Infinite Variance. Chapman & Hall, New York (1994)
Spitzmann, J.: Lösungen inhomogener stochastischer Fixpunktgleichungen (Solutions to inhomogeneous stochastic fixed-point equations). PhD thesis, Christian-Albrechts-Universität Kiel (2010)
Author information
Authors and Affiliations
Corresponding author
Additional information
M. Meiners’ research was supported by DFG-grant Me 3625/1-1.
Rights and permissions
About this article
Cite this article
Alsmeyer, G., Meiners, M. Fixed points of the smoothing transform: two-sided solutions. Probab. Theory Relat. Fields 155, 165–199 (2013). https://doi.org/10.1007/s00440-011-0395-y
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00440-011-0395-y
Keywords
- Branching random walk
- Characteristic function
- General branching processes
- Infinite divisibility
- Multiplicative martingales
- Smoothing transformation
- Stable distribution
- Stochastic fixed-point equation
- Weighted branching process