The way to produce a random but ordered series of numbers?

Question

(Assume that "Rand()" can produce truly random real number so we can only produce truly random number through this function.)

The common way is to produce a disordered sequence firstly and then sort them. But my question is, can we find a faster way to do this? Since it's ordered, maybe we can let an initial number grow bigger randomly and then we get an ordered sequence directly with no need to sort it, but it is difficult to guarantee its randomness. Is it possible? I am a high school student and just curious about the answer.

Answer 1

Suppose you want $n$ random numbers $a_k$, uniformly distributed between $0$ and $1$.
The probability that $a_1\gt x$ is $(1-x)^n=c_1$, so pick a uniform random number $c_1$ and let $b_1=1-\sqrt[n]{c_1}$, and $a_1=b_1$.
Now you need $n-1$ numbers uniformly distributed between $a_1$ and $1$.
Let $b_2=1-\sqrt[n-1]{c_2}$ and $a_2=a_1+(1-a_1)b_2$.
In general, $$c_k=Rand() \\b_k=1-\sqrt[n+1-k]{c_k} \\ a_k = a_{k-1}+(1-a_{k-1})b_k$$ EDiT
Take just two numbers $x$ and $y$. All points $(x,y)$ in the unit square are equally likely. Once you know the lower number is $c$, you are restricted to the two lines $(c,y), c\le y \le1$ and $(x,c),c\le x\le1$. In either case, the points on the line segment are equally likely, so the remaining variable is uniformly distributed between $c$ and $1$.
With three numbers, you start with points $(x,y,z)$ in a cube. Once you know the lowest value, you are restricted to three squares at right angles. Within any one, say $(c,y,z)$, the remaining variables $(y,z)$ are uniformly distributed over a square, and just need rescaling to be uniformly distributed over the unit square.
It won't always be the case. There is a probability density function, or PDF, which plays the role of ordinary probability. Then calculus plays an important role.

Answer 2

You want to produce, for some given $n$, independent uniformly distributed random numbers $X_i\in[0,1]$ for $i=1,\ldots, n$, and then let $Y_1,\ldots,Y_n$ be the same numbers but in ascending order.

Note that $P(Y_1<c)=\prod_{i=1}^nP(X_i<c)=c^n$. As $P(\text{rand()}<c)=c$, you can produce $Y_1$ easily per $Y_1=\text{rand()}^{1/n}$. After that, note that the remaining numbers are uniformly distributed in $[Y_1,1]$. So by the same reasoning, we can let $Y_2=Y_1+(1-Y_1)\cdot\text{rand()}^{1/(n-1)}$ and so on, i.e., $Y_{k+1}=Y_k+(1-Y_k)\cdot\text{rand()}^{1/(n-k)}$.

---

Nevertheless, I suggest that in most circumstance the straightforward method of generating and sorting is preferable. After all, sorting takes only $O(n\ln n)$ time and we avoid the time for all those raising to the power (and possibly introduced inaccuracy).