Mathematics – Probability
Scientific paper
2010-09-13
Mathematics
Probability
33 pages
Scientific paper
Given a sequence $(C,T) = (C,T_1,T_2,...)$ of real-valued random variables with $T_j \geq 0$ for all $j \geq 1$ and almost surely finite $N = \sup\{j \geq 1: T_j > 0\}$, the smoothing transform associated with $(C,T)$, defined on the set $\mathcal{P}(\R)$ of probability distributions on the real line, maps an element $P\in\mathcal{P}(\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 \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 \texttt{Quicksort} equation.
Alsmeyer Gerold
Meiners Matthias
No associations
LandOfFree
Fixed points of the smoothing transform: Two-sided solutions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Fixed points of the smoothing transform: Two-sided solutions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fixed points of the smoothing transform: Two-sided solutions will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-337774