<p>It's possible that what the OP wants is as follows:</p>

<p>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. </p>

<p>Now the goal is to define a way of sampling from this simplex with independent samples from the data (rather than trying to sample from the simplex directly). </p>

<p>In fact this can be done. <a href="http://luc.devroye.org/rnbookindex.html" rel="nofollow">Luc Devroye's book</a> 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). </p>

CC BY-SA 3.0
2012-03-12T15:46:31.390Z
2012-03-12T15:46:31.390Z
Suresh Venkat
<p>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.</p>

<p>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</p>

<ol>
<li><p>Over all possible $\pi$, each $\rho(x)$ is uniformly distributed in $[0,1]$</p></li>
<li><p>$\rho(\pi(1)) &lt; \rho(\pi(2)) &lt; \dots &lt; \rho(\pi(n))$</p></li>
<li><p>(Optional) $\rho(\pi(i))$ depends only only $\pi(1), \dots, \pi(i)$</p></li>
</ol>

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

CC BY-SA 3.0
2012-03-12T12:04:51.213Z
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
CC BY-SA 3.0
2012-03-12T12:10:13.563Z
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
<ds.algorithms><randomized-algorithms><pr.probability>
Generate random permutation via iid uniforms --- is inverse transformation possible?
David Harris
# Generate random permutation via iid uniforms --- is inverse transformation possible?

(Asked by: username_0 on 2012-03-12)

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?

**Tags:** ds.algorithms, randomized-algorithms, pr.probability
> **Comments:**
> **username_1**: 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?  
> **username_1**: 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?  

---

## 1 answers

### Answer by username_2 on 2012-03-12. Score: 4 | Accepted answer

It's possible that what the OP wants is as follows:

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.

Now the goal is to define a way of sampling from this simplex with independent samples from the data (rather than trying to sample from the simplex directly).

In fact this can be done. [Luc Devroye's book](http://luc.devroye.org/rnbookindex.html) 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).


---

