Let $A$ be a uniformly random permutation of the numbers $\{1,2,\cdots,n\}$. I want to generate a uniformly random permutation from $A$ on the numbers $\{1,2,\cdots,n,n+1,\cdots,n+m\}$. In other words, first I generate $A$ uniformly randomly. Then, taking that $A$, I want to generate $B$ such that final result is uniformly random.

I need to do it as follows: I first generate $A$ and then using an extra $m$ continuous-uniform random variables $X_i$ on the continuous interval $[0,n+m]$, append them at the end of $A$, and then rewrite everything in terms of their relative order.

Example: $n=3$, $m=2$. I generate $A=(2,1,3)$. I generate the two elements $X_1=1.1,X_2=2.6$. Appending this to the end of $A$: $(2,1,3,1.1,2.6)$ and now rewriting in terms of relative order $B=(3,1,5,2,4)$.

Unfortunately I'm not convinced that the final result really is a uniform permutation on $\{1,2,\cdots,n+m\}$. Is there a way to prove or modify it to make it work?

Note: this procedure absolutely has to incorporate the following:

1) Taking a uniformly random A

2) Somehow generating m extra elements $X_i$

3) Appending $X_i$ to the end of $A$.

4) Rewrite in relative order

so really step (2) is the only freedom I have.


You're right, this will not yield a uniform distribution for $m\gt1$. The probability for two given elements to be adjacent in a random order is roughly $\frac2n$ (since each element has roughly $2$ neighbours), whereas in your algorithm for $m=2$ the two additional elements have roughly $\frac1n$ probability of ending up adjacent.

You can't fix this by transforming the $X_i$ individually; as long as they're independent they can't have the right distribution. To modify the algorithm, you could add the additional elements one at a time, $m$ times $1$ instead of $m$ in $1$ go; or you could make the $X_i$ dependent, with joint distribution as required to make the distribution of the resulting permutation come out right. I'm not sure whether either of these options is allowed under your rules.

| cite | improve this answer | |

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.