Fixed points of the smoothing transform: two-sided solutions
Fixed points of the smoothing transform: two-sided solutions
复制标题
平滑变换的不动点：两侧解
DOI：
--
复制
发表时间：
2010
影响因子：
2
通讯作者：
M. Meiners
中科院分区：
文献类型：
--
作者：
G. Alsmeyer;M. Meiners
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.
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.
影响因子：
2.3
作者：
Alsmeyer;Gerold ;Biggins;Meiners;Matthias
通讯作者：
Matthias
影响因子：
1.1
作者：
Alsmeyer;Gerold ;Meiners;Matthias
通讯作者：
Matthias