A Gaussian limit process for optimal FIND algorithms

  • 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⋅nα are chosen, where 0<α≤12, 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→∞, which depends on α. 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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Henning SulzbachGND, Ralph NeiningerORCiDGND, Michael DrmotaORCiDGND
URN:urn:nbn:de:hebis:30:3-327510
DOI:https://doi.org/10.1214/EJP.v19-2933
ISSN:1083-6489
Parent Title (English):Electronic journal of probability
Document Type:Article
Language:English
Date of Publication (online):2014/01/06
Date of first Publication:2014/01/06
Publishing Institution:Universitätsbibliothek Johann Christian Senckenberg
Release Date:2014/01/27
Tag:FIND algorithm; Gaussian process; Quickselect; complexity; contraction method; functional limit theorem; key comparisons
Volume:19
Issue:3
Page Number:28
Note:
This work is licensed under a Creative Commons Attribution 3.0 License. http://creativecommons.org/licenses/by/3.0/
HeBIS-PPN:363411305
Institutes:Informatik und Mathematik / Mathematik
Dewey Decimal Classification:5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik
MSC-Classification:60-XX PROBABILITY THEORY AND STOCHASTIC PROCESSES (For additional applications, see 11Kxx, 62-XX, 90-XX, 91-XX, 92-XX, 93-XX, 94-XX) / 60Cxx Combinatorial probability / 60C05 Combinatorial probability
60-XX PROBABILITY THEORY AND STOCHASTIC PROCESSES (For additional applications, see 11Kxx, 62-XX, 90-XX, 91-XX, 92-XX, 93-XX, 94-XX) / 60Fxx Limit theorems [See also 28Dxx, 60B12] / 60F17 Functional limit theorems; invariance principles
60-XX PROBABILITY THEORY AND STOCHASTIC PROCESSES (For additional applications, see 11Kxx, 62-XX, 90-XX, 91-XX, 92-XX, 93-XX, 94-XX) / 60Gxx Stochastic processes / 60G15 Gaussian processes
68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section {04 in that areag 68-00 General reference works (handbooks, dictionaries, bibliographies, etc.) / 68Pxx Theory of data / 68P10 Searching and sorting
68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section {04 in that areag 68-00 General reference works (handbooks, dictionaries, bibliographies, etc.) / 68Qxx Theory of computing / 68Q25 Analysis of algorithms and problem complexity [See also 68W40]
Sammlungen:Universitätspublikationen
Licence (German):License LogoCreative Commons - Namensnennung 3.0

OPUS4 Logo