Can someone provide me with the mathematical expression for this code/function as a fast way to generate $n$ sorted $U[0,1]$ random numbers:
rsunif <- function(n) { n1 <- n+1
cE <- cumsum(rexp(n1)); cE[seq_len(n)]/cE[n1] }
$\begingroup$
$\endgroup$
1
-
2$\begingroup$ Given the code involves taking logs a lot of times, depending on the precise implementation and on the machine it's running on, in some cases it could potentially be faster to generate uniforms and sort them. $\endgroup$– Glen_bCommented May 27, 2018 at 1:37
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
The R code means returning $$(E_1,E_1+E_2,\ldots,E_1+\cdots+E_n)\Big/\sum_{i=1}^{n+1} E_i$$ and the result follows from checking that the differences between the cumulated sums of exponentials renormalised by the overall sum has the same distribution as the differences between order statistics for a uniform sample, $S_i=U_{(i)}-U_{(i-1)}$. This is described and established in the bible of simulation, Devroye's Non-Uniform Random Variate Generation (1986, pp. 207-219):
and also in Biau & Devroye Lectures on the Nearest Neighbor Method (pp.5-7)
Running a test to compare this spacing method with a direct ordering of uniform variates shows a clear advantage for this approach (for n=100 and 10⁷ replications, using R benchmark tool).
test replications elapsed relative user.self sys.self user.child
2 direct 1e7 355.213 4.722 355.112 0.024 0
1 spacings 1e7 75.221 1.000 75.208 0.000 0
although increasing $n$ to $n=10^3$ reduces the gain:
test replications elapsed relative user.self sys.self user.child
2 direct 1e6 96.225 1.886 96.20 0 0
1 spacings 1e6 51.029 1.000 51.02 0 0