## 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".)
```