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.

bioinformatics.oxfordjournals.org/.../25/.../i161.f... -

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