A Gaussian limit process for optimal FIND algorithms

Henning Sulzbach (INRIA Paris-Rocquencourt)
Ralph Neininger (Goethe University Frankfurt)
Michael Drmota (TU Vienna)

Abstract


We consider versions of the FIND algorithm where the pivot element used is the median of a subset chosen uniformly at random from the data. For the median selection we assume that subsamples of size asymptotic to $c \cdot n^\alpha$ are chosen, where $0< \alpha \leq \frac{1}{2}$, $c>0$ and $n$ is the size of the data set to be split. We consider the complexity of FIND as a process in the rank to be selected and measured by the number of key comparisons required. After normalization we show weak convergence of the complexity to a centered Gaussian process as $n \to \infty$, which depends on $\alpha$. The proof relies on a contraction argument for probability distributions on càdlàg functions. We also identify the covariance function of the Gaussian limit process and discuss path and tail properties.


Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-28

Publication Date: January 6, 2014

DOI: 10.1214/EJP.v19-2933

References

  • Adler, Robert J. An introduction to continuity, extrema, and related topics for general Gaussian processes. Institute of Mathematical Statistics Lecture Notes—Monograph Series, 12. Institute of Mathematical Statistics, Hayward, CA, 1990. x+160 pp. ISBN: 0-940600-17-X MR1088478
  • Anderson, D. H.; Brown, R. Combinatorial aspects of C. A. R. Hoare's FIND algorithm. Australas. J. Combin. 5 (1992), 109--119. MR1165798
  • Billingsley, Patrick. Convergence of probability measures. Second edition. Wiley Series in Probability and Statistics: Probability and Statistics. A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1999. x+277 pp. ISBN: 0-471-19745-9 MR1700749
  • Blanchet, Jose H.; Sigman, Karl. On exact sampling of stochastic perpetuities. J. Appl. Probab. 48A (2011), New frontiers in applied probability: a Festschrift for Soren Asmussen, 165--182. ISBN: 0-902016-08-3 MR2865624
  • Boucheron, S., Lugosi, G. and Massart, P.: Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, (2013).
  • Dadoun, B. and Neininger, R.: A statistical view on exchanges in Quickselect. Proceedings of the Eleventh Workshop on Analytic Algorithmics and Combinatorics (ANALCO), (2014), 40--51. arXiv:1307.8403
  • Devroye, Luc. Exponential bounds for the running time of a selection algorithm. J. Comput. System Sci. 29 (1984), no. 1, 1--7. MR0761047
  • Devroye, Luc. Simulating perpetuities. Methodol. Comput. Appl. Probab. 3 (2001), no. 1, 97--115. MR1833738
  • Devroye, L. On the probabilistic worst-case time of "find''. Mathematical analysis of algorithms. Algorithmica 31 (2001), no. 3, 291--303. MR1855252
  • Devroye, Luc; Fawzi, Omar. Simulating the Dickman distribution. Statist. Probab. Lett. 80 (2010), no. 3-4, 242--247. MR2575452
  • Devroye, L. and James, L.: The double CFTP method. ACM Trans. Model. Comput. Simul. 21, (2011), 1--20.
  • Drmota, Michael; Janson, Svante; Neininger, Ralph. A functional limit theorem for the profile of search trees. Ann. Appl. Probab. 18 (2008), no. 1, 288--333. MR2380900
  • Dudley, R. M. Sample functions of the Gaussian process. Ann. Probability 1 (1973), no. 1, 66--103. MR0346884
  • Eickmeyer, Kord; Rüschendorf, Ludger. A limit theorem for recursively defined processes in $L^ p$. Statist. Decisions 25 (2007), no. 3, 217--235. MR2412071
  • Fill, James Allen; Huber, Mark Lawrence. Perfect simulation of Vervaat perpetuities. Electron. J. Probab. 15 (2010), no. 4, 96--109. MR2587562
  • Fill, James Allen; Nakama, Takéhiko. Analysis of the expected number of bit comparisons required by Quickselect. Algorithmica 58 (2010), no. 3, 730--769. MR2672478
  • Fill, James Allen; Nakama, Takehiko. Distributional convergence for the number of symbol comparisons used by QuickSelect. Adv. in Appl. Probab. 45 (2013), no. 2, 425--450. MR3102458
  • Grabner, Peter J.; Prodinger, Helmut. On a constant arising in the analysis of bit comparisons in quickselect. Quaest. Math. 31 (2008), no. 4, 303--306. MR2527443
  • Grübel, Rudolf. Hoare's selection algorithm: a Markov chain approach. J. Appl. Probab. 35 (1998), no. 1, 36--45. MR1622443
  • Grübel, Rudolf. On the median-of-$k$ version of Hoare's selection algorithm. Theor. Inform. Appl. 33 (1999), no. 2, 177--192. MR1707969
  • Grübel, Rudolf; Rösler, Uwe. Asymptotic distribution theory for Hoare's selection algorithm. Adv. in Appl. Probab. 28 (1996), no. 1, 252--269. MR1372338
  • Hoare, C.A.R.: Algorithm 65, FIND. Comm. Assoc. Comput. Mach. 4, (1961), 321--322.
  • Hwang, Hsien-Kuei; Tsai, Tsung-Hsi. Quickselect and the Dickman function. Combin. Probab. Comput. 11 (2002), no. 4, 353--371. MR1918722
  • Kirschenhofer, Peter; Prodinger, Helmut. Comparisons in Hoare's Find algorithm. Combin. Probab. Comput. 7 (1998), no. 1, 111--120. MR1611049
  • Kirschenhofer, P.; Prodinger, H.; Martínez, C. Analysis of Hoare's FIND algorithm with median-of-three partition. Average-case analysis of algorithms (Dagstuhl, 1995). Random Structures Algorithms 10 (1997), no. 1-2, 143--156. MR1611516
  • Knape, Margarete; Neininger, Ralph. Approximating perpetuities. Methodol. Comput. Appl. Probab. 10 (2008), no. 4, 507--529. MR2443077
  • Knape, Margarete; Neininger, Ralph. Appendix to "Approximating perpetuities'' [MR2443077]. Methodol. Comput. Appl. Probab. 15 (2013), no. 3, 707--712. MR3085887
  • Knof, D.: Struktur von Fixpunkten aus Prozess gleichungen. Dissertation, Christian-Albrechts-Universität zu Kiel, (2007). Electronically available via urn:nbn:de:gbv:8-diss-23169
  • Knof, Diether; Roesler, Uwe. The analysis of find and versions of it. Discrete Math. Theor. Comput. Sci. 14 (2012), no. 2, 129--154. MR2992953
  • Knuth, Donald E. Mathematical analysis of algorithms. Information processing 71 (Proc. IFIP Congress, Ljubljana, 1971), Vol. 1: Foundations and systems, pp. 19--27. North-Holland, Amsterdam, 1972. MR0403310
  • Kodaj, B.; Móri, T. F. On the number of comparisons in Hoare's algorithm "FIND''. Studia Sci. Math. Hungar. 33 (1997), no. 1-3, 185--207. MR1454110
  • Mahmoud, Hosam M. Average-case analysis of moves in Quick Select. ANALCO09—Workshop on Analytic Algorithmics and Combinatorics, 35--40, SIAM, Philadelphia, PA, 2009. MR2648340
  • Mahmoud, Hosam M. Distributional analysis of swaps in Quick Select. Theoret. Comput. Sci. 411 (2010), no. 16-18, 1763--1769. MR2650339
  • Mahmoud, Hosam M.; Modarres, Reza; Smythe, Robert T. Analysis of QUICKSELECT: an algorithm for order statistics. RAIRO Inform. Théor. Appl. 29 (1995), no. 4, 255--276. MR1359052
  • Martínez, Conrado; Roura, Salvador. Optimal sampling strategies in quicksort and quickselect. SIAM J. Comput. 31 (2001/02), no. 3, 683--705 (electronic). MR1896454
  • Martínez, Conrado; Panario, Daniel; Viola, Alfredo. Adaptive sampling strategies for quickselect. ACM Trans. Algorithms 6 (2010), no. 3, Art. 53, 46 pp. MR2682622
  • Mörters, Peter; Peres, Yuval. Brownian motion. With an appendix by Oded Schramm and Wendelin Werner. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, 2010. xii+403 pp. ISBN: 978-0-521-76018-8 MR2604525
  • Neininger, Ralph; Rüschendorf, Ludger. A general limit theorem for recursive algorithms and combinatorial structures. Ann. Appl. Probab. 14 (2004), no. 1, 378--418. MR2023025
  • Neininger, Ralph; Rüschendorf, Ludger. Analysis of algorithms by the contraction method: additive and max-recursive sequences. Interacting stochastic systems, 435--450, Springer, Berlin, 2005. MR2118586
  • Neininger, R. and Sulzbach, H.: On a functional contraction method. arXiv:1202.1370
  • Paulsen, Volkert. The moments of FIND. J. Appl. Probab. 34 (1997), no. 4, 1079--1082. MR1484039
  • Ragab, M.: Partial Quicksort and weighted branching processes. Dissertation, Christian-Albrechts-Universität zu Kiel, (2011). Electronically available via urn:nbn:de:gbv:8-diss-73701
  • Ragab, Mahmoud; Roesler, Uwe. The Quicksort process. Stochastic Process. Appl. 124 (2014), no. 2, 1036--1054. MR3138605
  • Rösler, Uwe. A limit theorem for "Quicksort''. RAIRO Inform. Théor. Appl. 25 (1991), no. 1, 85--100. MR1104413
  • Rösler, U.: Quickselect revisited. J. Iranian Stat. Soc. 3, (2004), 271--296.
  • Rösler, U.; Rüschendorf, L. The contraction method for recursive algorithms. Average-case analysis of algorithms (Princeton, NJ, 1998). Algorithmica 29 (2001), no. 1-2, 3--33. MR1887296
  • Rüschendorf, Ludger. On stochastic recursive equations of sum and max type. J. Appl. Probab. 43 (2006), no. 3, 687--703. MR2274793
  • Sulzbach, H.: On a Functional Contraction Method. Dissertation, Goethe-Universität Frankfurt am Main, (2012). Electronically available via urn:nbn:de:hebis:30:3-248587
  • Talagrand, Michel. Regularity of Gaussian processes. Acta Math. 159 (1987), no. 1-2, 99--149. MR0906527
  • Vallée, Brigitte; Clément, Julien; Fill, James Allen; Flajolet, Philippe. The number of symbol comparisons in QuickSort and QuickSelect. Automata, languages and programming. Part I, 750--763, Lecture Notes in Comput. Sci., 5555, Springer, Berlin, 2009. MR2544890
  • Wild, S., Nebel, M.E. and Mahmoud, H.M.: Analysis of Quickselect under Yaroslavskiy's Dual-Pivoting Algorithm. ARXIV1306.3819.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.