Density functions for QuickQuant and QuickVal

DOI10.1214/22-EJP899MaRDI QIDQ6378980arXivFDO

Authors James Allen Fill, Wei-Chun Hung

Publication date 29 September 2021

Published in arXiv

Full work available at URL https://doi.org/10.1214/22-EJP899

Mathematics Subject Classification ID

Combinatorial probability (60C05) Probability distributions: general theory (60E05) Searching and sorting (68P10)

arXiv classification

cs.DSmath.PR

Abstract: We prove that, for every $0leqtleq1$, the limiting distribution of the scale-normalized number of key comparisons used by the celebrated algorithm QuickQuant to find the $t$th quantile in a randomly ordered list has a Lipschitz continuous density function $f_t$ that is bounded above by $10$. Furthermore, this density $f_t(x)$ is positive for every $x>mint,1-t$ and, uniformly in $t$, enjoys superexponential decay in the right tail. We also prove that the survival function $1-F_t(x)=in{t}_x^{infty}!f_t(y),mathrmdy$ and the density function $f_t(x)$ both have the right tail asymptotics $exp[-xlnx-xlnlnx+O(x)]$. We use the right-tail asymptotics to bound large deviations for the scale-normalized number of key comparisons used by QuickQuant.

This page was built for publication: Density functions for QuickQuant and QuickVal

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6378980)