Sampling in order
In statistics, some Monte Carlo methods require independent observations in a sample to be drawn from a one-dimensional distribution in sorted order. In other words, all n order statistics are needed from the n observations in a sample. The naive method performs a sort and takes O(n log n) time. There are also O(n) algorithms which are better suited for large n. The special case of drawing n sorted observations from the uniform distribution on [0,1] is equivalent to drawing from the uniform distribution on an n-dimensional simplex; this task is a part of sequential importance resampling.
Further reading
- Bentley, Jon Louis; Saxe, James B. (1979), "Generating sorted lists of random numbers", Computer Science Department, Paper 2450, retrieved January 4, 2014
- Gerontidis, I.; Smith, R. L. (1982), "Monte Carlo Generation of Order Statistics from General Distributions", Journal of the Royal Statistical Society. Series C (Applied Statistics) 31 (3): 238–243, retrieved January 4, 2014
- Lurie, D.; Hartley, H. O. (1972), "Machine-Generation of Order Statistics for Monte Carlo Computations", The American Statistician 26 (1): 26–27, doi:10.1080/00031305.1972.10477319
- Ripley, Brian D. (1987), Stochastic Simulation, Wiley, pp. 96–98, ISBN 0-471-81884-4
This article is issued from Wikipedia - version of the Wednesday, September 09, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.