zbMATH — the first resource for mathematics

Analysis of radix selection on Markov sources. (English) Zbl 1355.60031
Bousquet-Mélou, Mireille (ed.) et al., Proceeding of the 25th international conference on probabilistic, combinatorial and asymptotic methods in the analysis of algorithms, AofA’14, UPMC-Jussieu, Paris, France, June 16–20, 2014. Nancy: The Association. Discrete Mathematics & Theoretical Computer Science (DMTCS). Discrete Mathematics and Theoretical Computer Science (DMTCS-HAL). Proceedings BA, 253-264 (2014).
Summary: The complexity of the algorithm Radix Selection is considered for independent data generated from a Markov source. The complexity is measured by the number of bucket operations required and studied as a stochastic process indexed by the ranks; also the case of a uniformly chosen rank is considered. The orders of mean and variance of the complexity and limit theorems are derived. We find weak convergence of the appropriately normalized complexity towards a Gaussian process with explicit mean and covariance functions (in the space \(D[0,1]\) of càdlàg functions on \([0, 1]\) with the Skorokhod metric) for uniform data and the asymmetric Bernoulli model. For uniformly chosen ranks and uniformly distributed data the normalized complexity was known to be asymptotically normal. For a general Markov source (excluding the uniform case) we find that this complexity is less concentrated and admits a limit law with non-normal limit distribution.
For the entire collection see [Zbl 1329.68022].

60F05 Central limit and other weak theorems
60G15 Gaussian processes
68W40 Analysis of algorithms
Full Text: Link arXiv