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].

For the entire collection see [Zbl 1329.68022].

##### MSC:

60F05 | Central limit and other weak theorems |

60G15 | Gaussian processes |

68W40 | Analysis of algorithms |

PDF
BibTeX
XML
Cite

\textit{K. Leckey} et al., in: 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). 253--264 (2014; Zbl 1355.60031)