Generating Random Numbers In Order

Suppose we wish to generate n independent random numbers, uniformly 
distributed between 0 and 1, and sort them into increasing order.
To avoid the sorting process, can we simply generate the random
numbers in order of size?

For a geometrical approach to this problem, consider first the 
simple case of drawing just TWO numbers from a uniform distribution 
on the interval 0 to 1.  The "state space" of all possible outcomes 
is illustrated below:

                |
              1 |------------
                |          / |
            x2  |        /   |
                |      /     |
                |    /       |
                |  /         |
              0 |/___________|___
                0            1
                        x1

Each point in this square is equally likely to be the result
of drawing two random numbers x1 and x2.  The cases in which
x1 is less than x2 are represented by the region above the
diagonal line.  So, if we want to generate points such that 
x1 is always less than x2, we essentially need to select
points randomly from the upper triangular region.  Therefore, 
we can choose x1 from the interval 0 to 1 with a density 
function proportional to (1-x), and then choose x2 from the 
interval x1 to 1 with a uniform density on the range x1 to 1.

Now consider the case of THREE random numbers.  In this case
our state space is a solid cube of equally probable points,
and we are focusing on the region of this cube in which x1 is
less than x2 is less than x3.  This wedge-shaped region is
1/6 of the cube, so, we can choose x1 from the interval 0 to 
1 with a density function proportional to (1-x)^2, then choose
x2 from the interval x1 to 1 with a density proportional to 
(1-x), and then choose x3 from the interval x2 to 1 with a 
uniform density.

In general, for n numbers we can define x0 = 0 and then for 
j=1 to n we can draw xj from the interval x{j-1} to 1 with 
density proportional to (1-x)^(n-j).

As Horst Kraemer notes, we may also simulate an n-sample of the 
"rank statistics" using a regular n-sample (u[1],...,u[n]) by the 
recursive transformation

 	x[1]    =  1 -           *u[1]^(1/n)
        x[2]    =  1 - (1-x[1]  )*u[2]^(1/(n-1))
         ....
        x[n]    =  1 - (1-x[n-1])*u[n] 

Incidentally, both William Feller and Sheldon Ross refer to the x[j] 
as "order statistics".   Ross's book "Introduction to Probability 
Models" includes a slightly more general discussion of the method 
described by Horst above.  (These methods may seem slightly counter-
intuitive, because of how they react to extreme values of the early 
u samples, but that's true of any method of generating a random 
sequence "in order".)

Return to MathPages Main Menu