2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Tsuyoshi Ito Mar 12 '12 at 12:04
  • 5
    $\begingroup$ 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? $\endgroup$ – Tsuyoshi Ito Mar 12 '12 at 12:10
4
$\begingroup$

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

$\endgroup$

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.