Abstract
We prove that, for every , the limiting distribution of the scale-normalized number of key comparisons used by the celebrated algorithm QuickQuant to find the tth quantile in a randomly ordered list has a Lipschitz continuous density function that is bounded above by 10. Furthermore, this density is positive for every and, uniformly in t, enjoys superexponential decay in the right tail. We also prove that the survival function and the density function both have the right tail asymptotics . We use the right-tail asymptotics to bound large deviations for the scale-normalized number of key comparisons used by QuickQuant.
Funding Statement
Research of both authors supported by the Acheson J. Duncan Fund for the Advancement of Research in Statistics.
Acknowledgments
We thank Svante Janson, the Editor of Electronic Journal of Probability, two Associate Editors, and a referee for helpful comments on earlier versions of this paper; they led to significant improvements.
Citation
James Allen Fill. Wei-Chun Hung. "Density functions for QuickQuant and QuickVal." Electron. J. Probab. 28 1 - 50, 2023. https://doi.org/10.1214/22-EJP899
Information