Timeline for What is the most efficient way to generate a random permutation from probabilistic pairwise swaps?
Current License: CC BY-SA 2.5
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 7, 2011 at 18:06 | comment | added | Andrew D. King | Good point. I somehow relaxed to the point of considering coin flips. This would be equivalent to choosing a random $2^{k-1}$-set from a $2^k$-set, and it's not clear to me that this is easy. | |
| Mar 7, 2011 at 15:49 | comment | added | Joe Fitzsimons | @Andrew: I don't see how to "merge these randomly" using the gates outlined in the question. | |
| Mar 7, 2011 at 15:18 | comment | added | Antonio Valerio Miceli-Barone | That was also my line of thinking when I proposed mergesort, however, on a second thought, it seems to me that it may not be possible to implement the merge operation using only the required type of gates, since they don't produce an output to tell whether they performed the permutation and they have no control input to condition them. | |
| Mar 7, 2011 at 15:06 | comment | added | Andrew D. King | Assume $n=2^k$ and proceed by induction on $k$. You have two random permutations of length $2^{k-1}$. If you merge these randomly (i.e. taking the next element from a randomly chosen subpermutation) then the merged results should certainly be random. The probability of position $i$ having an element from the "left" subpermutation is clearly 1/2 by symmetry. And conditioned on it having an element from the left subpermutation, it must have a uniformly random one from it. In this way you can see that the resulting permutation is indeed random. | |
| Mar 7, 2011 at 14:36 | comment | added | Joe Fitzsimons | And yes, $\lceil \log_2(n!) \rceil$ is the minimum, but this is only $O(n\log(n))$. | |
| Mar 7, 2011 at 14:19 | comment | added | Joe Fitzsimons | I'm not entirely sure how you would translate this into the probabilitsic swap gate model I gave above. I don't see how a probabilistic swap replaces the comparison and still achieves a random distribution. Hence, I'm also not sure why this would be optimal. | |
| Mar 7, 2011 at 13:46 | history | edited | Antonio Valerio Miceli-Barone | CC BY-SA 2.5 |
added 184 characters in body
|
| Mar 7, 2011 at 13:05 | history | answered | Antonio Valerio Miceli-Barone | CC BY-SA 2.5 |