Hostname: page-component-586b7cd67f-t7fkt Total loading time: 0 Render date: 2024-11-27T23:40:57.882Z Has data issue: false hasContentIssue false
  • English
  • Français

All solutions of the stochastic fixed point equation of the Quicksort process

Part of: Theory of data Special processes Limit theorems

Published online by Cambridge University Press:  01 February 2019

S. Hallmann ,
U. Rösler  and
M. Wnuk
S. Hallmann*
Affiliation:
Christian-Albrechts-Universität zu Kiel
U. Rösler*
Affiliation:
Christian-Albrechts-Universität zu Kiel
M. Wnuk*
Affiliation:
Christian-Albrechts-Universität zu Kiel
*
Mathematisches Seminar, Christian-Albrechts-Universität zu Kiel, Ludewig-Meyn-Strasse 4, 24098 Kiel, Germany.
Mathematisches Seminar, Christian-Albrechts-Universität zu Kiel, Ludewig-Meyn-Strasse 4, 24098 Kiel, Germany. Email address: [email protected]
Mathematisches Seminar, Christian-Albrechts-Universität zu Kiel, Ludewig-Meyn-Strasse 4, 24098 Kiel, Germany.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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.

Keywords

Stochastic processstochastic fixed point equationQuicksort processSkorokhod convergence

MSC classification

Primary: 60F17: Functional limit theorems; invariance principles
Secondary: 60K99: None of the above, but in this section 68P10: Searching and sorting
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 

References

[1]Aldous, D. J. and Bandyopadhyay, A. (2005).A survey of max-type recursive distributional equations.Ann. Appl. Prob. 15,1047–1110.Google Scholar
[2]Alsmeyer, G. and Meiners, M. (2013).Fixed points of the smoothing transform: two-sided solutions.Prob. Theory Relat. Fields 155,165–199.Google Scholar
[3]Alsmeyer, G. and Rösler, U. (2006).A stochastic fixed point equation related to weighted branching with deterministic weights.Electron. J. Prob. 11,27–56.Google Scholar
[4]Athreya, K. B. and Ney, P. E. (1972).Branching Processes (Die Grundlehren der Mathematischen Wissenschaften 196).Springer,New York.Google Scholar
[5]Billingsley, P. (1968).Convergence of Probability Measures.John Wiley,New York.Google Scholar
[6]Fill, J. A. and Janson, S. (2000).A characterization of the set of fixed points of the Quicksort transformation.Electron. Commun. Prob. 5,77–84.Google Scholar
[7]Grübel, R. (1998).Hoare's selection algorithm: a Markov chain approach.J. Appl. Prob. 35,36–45.Google Scholar
[8]Grübel, R. and Roesler, U. (1996).Asymptotic distribution theory for Hoare's selection algorithm.Adv. Appl. Prob. 28,252–269.Google Scholar
[9]Knof, D. and Roesler, U. (2012).The analysis of Find and versions of it.Discrete Math. Theoret. Comput. Sci. 14,129–154.Google Scholar
[10]Kurtz, T.,Lyons, R.,Pemantle, R. and Peres, Y. (1997).A conceptual proof of the Kesten‒Stigum theorem for multi-type branching processes. In Classical and Modern Branching Processes (IMA Vol. Math. Appl. 84),Springer,New York, pp. 181–185.Google Scholar
[11]Lyons, R.,Pemantle, R. and Peres, Y. (1995).Conceptual proofs of Llog L criteria for mean behavior of branching processes.Ann. Prob. 23,1125–1138.Google Scholar
[12]Martínez, C. (2004).Partial Quicksort. In Proc. 6th Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithmics and Combinatorics (New Orleans, January 2004), eds L. Arge, G. F. Italiano and R. Sedgewick,SIAM, pp. 224–228.Google Scholar
[13]Martínez, C. and Rösler, U. (2010).Partial Quicksort and Quickpartitionsort. In 1st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10; Discrete Math. Theoret. Comput. Sci. AM),Association of Discrete Mathematics and Theoretical Computer Science,Nancy, pp. 505–512.Google Scholar
[14]Meiners, M. and Mentemeier, S. (2017).Solutions to complex smoothing equations.Prob. Theory Relat. Fields 168,199–268.Google Scholar
[15]Mentemeier, S. (2016).The fixed points of the multivariate smoothing transform.Prob. Theory Relat. Fields 164,401–458.Google Scholar
[16]Neininger, R. and Rüschendorf, L. (2005).Analysis of algorithms by the contraction method: additive and max-recursive equations. In Interacting Stochastic Systems, eds. J.-D. Deuschel and A. Greven,Springer,Berlin, pp. 435–450.Google Scholar
[17]Neininger, R. and Sulzbach, H. (2015).On a functional contraction method.Ann. Prob. 43,1777–1822.Google Scholar
[18]Ragab, M. and Roesler, U. (2014).The Quicksort process.Stoch. Process. Appl. 124,1036–1054.Google Scholar
[19]Rao, M. M. (1971).Projective limits of probability spaces.J. Multivariate Anal. 1,28–57.Google Scholar
[20]Rösler, U. (1991).A limit theorem for 'Quicksort'.RAIRO Inf. Théor. Appl. 25,85–100.Google Scholar
[21]Rösler, U. (1992).A fixed point theorem for distributions.Stoch. Process. Appl. 42,195–214.Google Scholar
[22]Rösler, U. (1993).The weighted branching process. In Dynamics of Complex and Irregular Systems (Bielefeld, 1991; Bielefeld Encount. Math. Phys. VIII),World Scientific,River Edge, NJ, pp. 154–165.Google Scholar
[23]Rösler, U. (2018).Almost sure convergence to the Quicksort process. To appear in Stoch. Process. Appl.Google Scholar
[24]Rösler, U. and Rüschendorf, L. (2001).The contraction method for recursive algorithms.Algorithmica 29,3–33.Google Scholar
[25]Rüschendorf, L. (2006).On the stochastic recursive equations of sum and max type.J. Appl. Prob. 43,687–703.Google Scholar