Generate random permutation via iid uniforms — is inverse transformation possible?

A very common technique in the analysis of algorithms involving random permutations is to have each element $x$ select a rank $\rho(x)$ uniformly at random from the real interval $[0,1]$. The permutation $\pi$ is then formed by sorting on ranks.

Is it possible to invert this transformation? That is, given a permutation $\pi$ generated randomly in $S_n$, choose ranks $\rho(x)$ (with some additional randomness) such that

1. Over all possible $\pi$, each $\rho(x)$ is uniformly distributed in $[0,1]$

2. $\rho(\pi(1)) < \rho(\pi(2)) < \dots < \rho(\pi(n))$

3. (Optional) $\rho(\pi(i))$ depends only only $\pi(1), \dots, \pi(i)$

Seemingly, giving $\rho(\pi(1))$ the distribution on the minimum of $n$ uniform variables, and so on, would work. Is there are any reference?

• I do not know a reference, but the distribution on the minimum of n uniform and independent random variables in the interval [0,1] is easy to calculate. Hint: Given x∈[0,1], what is the probability that this minimum is greater than x? – Tsuyoshi Ito Mar 12 '12 at 12:04
• By the way, I do not know what your question is. If you generate n uniform and independent random variables in [0,1] and sort them so that the order matches π, then you obtain an n-tuple uniformly distributed from the set of n-tuple of values in [0,1] which has the same order as π. Is this what you want? – Tsuyoshi Ito Mar 12 '12 at 12:10

Fix an ordering. By the standard trick using hyperplane arrangements, each such ordering represents one of the n! congruent simplices that make up the unit hypercube in $n$ dimensions.
In fact this can be done. Luc Devroye's book describes the procedure (see V.3), which essentially boils down to letting $x_i$ be an exponentially distributed random variable, normalizing them, and then setting $\rho(\pi(i))$ to be the partial sum $\sum_{j \le i} x_i$ (I'm over simplifying a little, so what I said isn't entirely precise, but it's the general idea).