More out of curiosity than anything else. I know you can always generate a list of random numbers and then sort it, but I was wondering if there exists a (pseudo)random number generator whose output is already in sorted order? I found this, but it and everything else I found only generates integer lists. Is there an equivalent for floats and without worrying about repetition?
$\begingroup$
$\endgroup$
7
1 Answer
$\begingroup$
$\endgroup$
2
You haven't answered the question about what distribution, so I will assume you want the uniform distribution on [0,1].
Yes, this can be done. However, I doubt that the result will be better in practice than just generating $n$ numbers uniformly at random and sorting them.
Based on the order statistics of the uniform distribution, the distribution of the smallest of $n$ numbers from the uniform distribution is known: it has a Beta$(1,n)$ distribution. Also, it is known how to sample from such a distribution.
So, there is a simple algorithm: sample the first number $x_1$ from the sorted sequence, by generating a random sample from Beta$(1,n)$. Then, sample the second number $x_2$, by letting $x_2 = x_1 + d_2/(1-x_1)$ where $d_2$ is sampled from Beta$(1,n-1)$, and $x_3 = x_2 + d_3/(1-x_1-x_2)$ where $d_3$ is sampled from Beta$(1,n-2)$, and so on.
Why does this work? Well, obviously $x_1$ has the right distribution. Also, the numbers $x_2,\dots,x_n$ can be obtained by sampling uniformly at random from $[x_1,1]$ and sorting, so we can generate them recursively using the same algorithm. Finally, unwinding the recursion gives the above algorithm.
-
$\begingroup$ Amazing thanks! Can you tell me why you doubt the result will be better in practice than sorting? $\endgroup$– Sas2450May 11 at 0:45
-
$\begingroup$ @Sas2450, sorting is simple and quite efficient in practice, whereas sampling from a Beta distribution looks more complex to me. $\endgroup$– D.W. ♦May 11 at 0:57
everything [found] generates integer listsassuming non-negative values only and sorted order to mean non descending, take the "head sums" of the list, add lower limit of desired range and scale by ratio of final sum and range.) $\endgroup$