Home | Contents | Submissions, editors, etc. | Login | Search | EJP
 Electronic Communications in Probability > Vol. 5 (2000) > Paper 9 open journal systems 


A Characterization of the Set of Fixed Points of the Quicksort Transformation

James Allen Fill, The Johns Hopkins University
Svante Janson, Uppsala University


Abstract
The limiting distribution m of the normalized number of key comparisons required by the Quicksort sorting algorithm is known to be the unique fixed point of a certain distributional transformation T -- unique, that is, subject to the constraints of zero mean and finite variance. We show that a distribution is a fixed point of T if and only if it is the convolution of m with a Cauchy distribution of arbitrary center and scale. In particular, therefore, m is the unique fixed point of T having zero mean.


Full text: PDF

Pages: 77-84

Published on: May 26, 2000
Bibliography
  1. Chung, K. L. (1974), A Course in Probability Theory. Second edition. Academic Press, New York. Math. Review 49:11579
  2. Durrett, R. and Liggett, T. M. (1983), Fixed points of the smoothing transformation, Z. Wahrsch. Verw. Gebiete 64, 275-301. Math. Review 85e:60059
  3. Fill, J. A. and Janson, S. (2000), Smoothness and decay properties of the limiting Quicksort density function. To apppear in a book edited by D . Gardy and A. Mokkadem, published by Birkhäuser, and based on the C olloquium on Mathematics and Computer Science: Algorithms, Trees, Combinatorics and Probabilities (University of Versailles-St. Quentin, Versailles, France, September, 2000). Preprint available from http://www.mts.jhu.edu/~fill/. Math. Review number not available.
  4. Guivarc'h, Y. (1990), Sur une extension de la notion de loi semi-stable, Ann. Inst. H. Poincaré Probab. Statist. 26, 261-285. Math. Review 91i:60141
  5. Knessl, C. and Szpankowski, W. (1999), Quicksort algorithm again revisited, Discrete Math. Theor. Comput. Sci. 3, 43-64. Math. Review 2000b:68052
  6. Liu, Q. (1998), Fixed points of a generalized smoothing transformation and applications to the branching random walk, Adv. in Appl. Probab. 30, 85-112. Math. Review 99f:60151
  7. Rösler, U. (1991), A limit theorem for `Quicksort', RAIRO Inform. Théor. Appl. 25, 85-100. Math. Review 92f:68028
  8. Rösler, U. (1992), A fixed point theorem for distributions, Stochastic Process. Appl. 42, 195-214. Math. Review 93k:60038
  9. Rösler, U. (1999), The analysis of stochastic divide and conquer algorithms, Algorithmica , to appear. Preprint available from http://www-computerlabor.math.uni-kiel.de/stochastik/roesler/e_research.html . Math. Review number not available.
  10. Rösler, U., and Rüschendorf, L. (1999), The contraction method for recursive algorithms, Algorithmica , to appear. Preprint available from http://www-computerlabor.math.uni-kiel.de/stochastik/roesler/e_research.html . Math. Review number not available.















Research
Support Tool
Capture Cite
View Metadata
Printer Friendly
Context
Author Address
Action
Email Author
Email Others


Home | Contents | Submissions, editors, etc. | Login | Search | EJP

Electronic Communications in Probability. ISSN: 1083-589X