Quantiles on Stream: An Application to Monte Carlo Simulation

Wang Wei (), Ching Wai-Ki (), Wang Shouyang () and Lean Yu ()
Additional contact information
Wang Wei: Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing100190, China
Ching Wai-Ki: Advanced Modeling and Applied Computing Laboratory, Department of Mathematics, The University of Hong Kong, Hong Kong, China
Wang Shouyang: Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing100190, China

Journal of Systems Science and Information, 2016, vol. 4, issue 4, 334-342

Abstract: Monte Carlo simulation is an efficient method to estimate quantile. However, it becomes a serious problem when a huge sample size is required but the memory is insufficient. In this paper, we apply the stream quantile algorithm to Monte Carlo simulation in order to estimate quantile with limited memory. A rigorous theoretical analysis on the properties of the ϵn-approximate quantile is proposed in this paper. We prove that if ϵn = o(n-1/2), then the ϵn-approximate α-quantile computed by any deterministic stream quantile algorithm is a consistent and asymptotically normal estimator of the true quantile qα. We suggest setting ϵn = 1/(n1/2 log10n) in practice. Two deterministic stream quantile algorithms, including of GK algorithm and ZW algorithm, are employed to illustrate the performance of the ϵn-approximate quantile. The numerical example shows that the deterministic stream quantile algorithm can provide desired estimator of the true quantile with less memory.

Keywords: quantile; stream; Monte Carlo; simulation; estimation (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.21078/JSSI-2016-334-09 (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:bpj:jossai:v:4:y:2016:i:4:p:334-342:n:4

DOI: 10.21078/JSSI-2016-334-09

Access Statistics for this article

Journal of Systems Science and Information is currently edited by Shouyang Wang

More articles in Journal of Systems Science and Information from De Gruyter
Bibliographic data for series maintained by Peter Golla ().