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, JSTOR 2347997238-243&rft.date=1982&rft_id=https://www.jstor.org/stable/2347997#id-name=JSTOR&rft.aulast=Gerontidis&rft.aufirst=I.&rft.au=Smith, R. L.&rfr_id=info:sid/en.wikipedia.org:Sampling in order" class="Z3988">
• 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.1047731926-27&rft.date=1972&rft_id=info:doi/10.1080/00031305.1972.10477319&rft.aulast=Lurie&rft.aufirst=D.&rft.au=Hartley, H. O.&rfr_id=info:sid/en.wikipedia.org:Sampling in order" class="Z3988">
• Ripley, Brian D. (1987), Stochastic Simulation, Wiley, pp. 96–98, ISBN 0-471-81884-496-98&rft.pub=Wiley&rft.date=1987&rft.isbn=0-471-81884-4&rft.aulast=Ripley&rft.aufirst=Brian D.&rfr_id=info:sid/en.wikipedia.org:Sampling in order" class="Z3988">