7
$\begingroup$

(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.

$\endgroup$
  • 2
    $\begingroup$ Can't you just draw a random number (make it positive if necessary) and add it to the previous random number. The result will be larger than the previous random number an can serve as the next random number. $\endgroup$ – M. Winter Aug 1 at 12:26
  • $\begingroup$ "truly random" & "random" don't mean anything in particular. From what distribution? $\endgroup$ – philipxy Aug 2 at 5:39
9
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ “Now you need n−1 numbers uniformly distributed between a1 and 1.”why can we just regard the left sequence as an independent new random sequence?Is this a usual way to solve such kind of question? $\endgroup$ – Player0 Aug 1 at 11:58
  • $\begingroup$ Thanks.I am surprised to know this fact.So now a_k can be expressed in terms of c_k.That's crazy! $\endgroup$ – Player0 Aug 1 at 13:39
5
$\begingroup$

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).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Isn't $Pr(Y_1\lt c)=1-\prod Pr(X_i\gt c)=1-(1-c)^n$ $\endgroup$ – Empy2 Aug 1 at 8:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.