No CrossRef data available.
Article contents
All solutions of the stochastic fixed point equation of the Quicksort process
Published online by Cambridge University Press: 01 February 2019
Abstract
The Quicksort process R (Rösler (2018)) can be characterized as the unique endogenous solution of the inhomogeneous stochastic fixed point equation R=D(UR1(1∧t∕U)+𝟭{U<t}(1-U)R2((t-U)∕(1-U))+C(U,t))t on the space 𝒟 of càdlàg functions, such that R(1) has the Quicksort distribution. In this paper we characterize all 𝒟-valued solutions of that equation. Every solution can be represented as the convolution of a solution of the inhomogeneous equation and a general solution of the homogeneous equation (Rüschendorf (2006)). The general solutions of the homogeneous equation are the distributions of Cauchy processes Y with constant drift. Any distribution of R+Y for independent R and Y is a solution of the inhomogeneous equation. Every solution of the inhomogeneous equation is of the form R+Y, where R and Y are independent. The endogenous solutions for the inhomogeneous equation are the shifted Quicksort process distributions. In comparison, the Quicksort distribution is the endogenous solution of the Quicksort fixed point equation unique up to a constant (Rösler (1991)). The general solution can be represented as the convolution of the shifted Quicksort distribution and some symmetric Cauchy distribution (Fill and Janson (2000)), possibly degenerate.
MSC classification
- Type
- Original Article
- Information
- Advances in Applied Probability , Volume 50 , Issue A: Branching and Applied Probability , December 2018 , pp. 131 - 140
- Copyright
- Copyright © Applied Probability Trust 2018