Online quantile and density estimators. Ghosh, S. & Pasupathy, R. In Pasupathy, R., Kim, S., Tolk, A., Hill, R., & Kuhl, M. E., editors, Proceedings of the 2013 Winter Simulation Conference, pages 778–789, Piscataway, NJ, 2013. Institute of Electrical and Electronics Engineers, Inc..
Online quantile and density estimators [pdf]Paper  abstract   bibtex   
The traditional estimator for the p-quantile of a random variable X is obtained by inverting the empirical cumulative distribution function (cdf) constructed from n obtained observations. The estimator requires O(n) storage, and the mean squared error of the estimator decays as O(1/n). In this article, we present an alternative estimator that requires dramatically less storage with negligible loss in convergence rate. The proposed estimator relies on an alternative cdf that is constructed by accumulating the observed random variates into variable-sized bins that progressively become finer around the quantile. The size of the bins are adjusted to ensure that the increased bias due to binning does not adversely affect the resulting convergence rate. We present an "online'' version of the estimator, and discuss of some of its theoretical properties. We also discuss analogous ideas for density estimation.

Downloads: 0