Date: Feb 11, 2013 5:06 PM
Author: Luis A. Afonso
Subject: Finding quartiles by Monte Carlo
Even today is easy to find in literature the reference of ordering data with the goal of find test statistics quantiles, namely critical values.
Fewer permutations, more accurate p-values
Theo A. Knijnenburg et all. Vol. 25 ISMB 2009.
People is well aware that, unless sound knowledge of special techniques to this aim, to order a great amount of data is definitively a very time consuming job. In fact for a set of N items, the brute force method demands to compare each item with all the remainders in order to find what is place in the final ascending values raw, a N^2 total comparisons.
One can do otherwise, of course: data can be coded and memory-stored instantaneously it is simulated using, for example, the expression mem.=1000*INT[(x-u)/m] and W(mem.)=W(mem.)+1. Once all data x recorded one have only to add W´s till the quantile is just attained by excess. The quantities u and m, that can be 0 and 1, are such that even be set by sight: however if by chance a=min x and m= max x - min x one have 0 <= mem. <= 1000 which is a good practice in order to occupy not too much computer memory space.
Generally speaking one has to limit data. For example if we know that x follows a Normal Standard we are interested in the interval say [-4, 4] and we intend to use 8000 addresses, so for each x we start to cut like: if x< -4 then x = -4 and if x> 4 then x= 4, followed by x´= x + 4. Suppose that x= -1.23416, then x´= 2.76584, x´´=1000*x´= 2765.84, INT(x´´+ .5)= 2766, the memory address where 1 unit is added. The final part to perform is to find the wanted quantile of x´´, divide it by 1000 and subtract 4.
I did find 1.961 for the quartile 0.975 (4000000 values) whereas the exact value is 1.960, so or I do not care this difference, or, possibly, must find of a more accurate random number generator . . .
Luis A. Afonso