Generalized equations of stability

Stochastic Analysis Seminar Series

In many models of Applied Probability, the distributional limits of recursively defined quantities satisfy distributional identities that are reminiscent of equations of stability.

Therefore, there is an interest in generalized concepts of equations of stability.

One extension of this concept is that of random variables ``stable by random weighted mean''  (this notion is due to Liu).

A random variable $X$ taking values in $\mathbb{R}^d$ is called ``stable by random weighted mean'' if it satisfies a recursive distributional equation of the following type:

\begin{equation}\tag{1}\label{eq:1}X ~\stackrel{\mathcal{D}}{=}~ C + \sum_{j \geq 1} T_j X_j.\end{equation}

Here, ``$\stackrel{\mathcal{D}}{=}$'' denotes equality of the corresponding distributions, $(C,T_1,T_2,\ldots)$ is a given sequence of real-valued random variables, and $X_1, X_2, \ldots$ denotes a sequence of i.i.d.\;copies of the random variable $X$ that are independent of $(C,T_1,T_2,\ldots)$.

The distributions $P$ on $\mathbb{R}^d$ such that \eqref{eq:1} holds when $X$ has distribution $P$ are called fixed points of the smoothing transform (associated with $(C,T_1,T_2,\ldots)$).

A particularly prominent instance of \eqref{eq:1} is the {\texttt Quicksort} equation, where $T_1 = 1-T_2 = U \sim \mathrm{Unif}(0,1)$, $T_j = 0$ for all $j \geq 3$ and $C = g(U)$ for some function $g$.

In this talk, I start with the {\texttt Quicksort} algorithm to motivate the study of eqref{eq:1}.

Then, I consider the problem of characterizing the set of all solutions to \eqref{eq:1} in a very general context.

Special emphasis is put on \emph{endogenous} solutions to \eqref{eq:1} since they play an important role in the given setting.


Matthias Meiners (University of Münster)

Monday, April 22, 2013 - 15:45
to 16:45