Timeline for What is the most efficient way to generate a random permutation from probabilistic pairwise swaps?
Current License: CC BY-SA 3.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 30, 2015 at 17:59 | history | edited | Peter Taylor | CC BY-SA 3.0 |
Improve LaTeX for the minor
|
| Mar 16, 2011 at 20:15 | comment | added | mjqxxxx | I'm awarding the bounty here, although the answer provides neither an asymptotic improvement over the $\Omega(n \log n)$ lower bound nor any improvement on the $n(n-1)/2$ upper bound, because at least it proves that $n(n-1)/2$ is optimal in a single nontrivial case. | |
| Mar 16, 2011 at 20:13 | history | bounty ended | mjqxxxx | ||
| Mar 14, 2011 at 17:25 | comment | added | mkatkov | Bitonic sorter for 8 inputs can be a good candidate. It can first equalize permutations for group 1-4 and 5-8 in 3 layers, than merge them in 1 layer with proba 1/2, and then unwind arising unequal probabilities in next 2 layers. The point here is that the configurations are symmetric with respect to lines 1-4 and 5-8, which requires independent unwinding. | |
| Mar 14, 2011 at 16:45 | comment | added | mkatkov | Consider sorting network with 1/2 gates. Consider all permutations arising from ordered state. The conditional probabilities of permutations (1, 2, ...) and (2, 1, ...) will differ by the number of computational path inputs (1,2) can reach states (1, 2) and (2,1). To fix that one need to add a gate between lines 1 and 2 with odds inverse to the number of paths between 2 configurations. This gate will equalize many (2, 1, ...), (1, 2, ...) permutations. The question here what is optimal set of pairs to equalize all permutations | |
| Mar 14, 2011 at 15:43 | comment | added | mkatkov | @Peter Equal probability of reaching output is not sufficient. One can construct sorting network that will have equal probability of output, but still not equal probabilities for permutations. I need to find a way to state the equal computational paths more formally. It is easy for 1/2 gates network, but more difficult in general case. | |
| Mar 14, 2011 at 15:17 | comment | added | Peter Taylor | @mkatkov, "Having equal odds of traveling from all inputs to all outputs by symmetry will produce equiprobable permutations" requires proof. I can make a network with four inputs and four gates for which each input has 1/4 probability of reaching each output, but it will have impossible permutations. I was planning to consider the Benes construction, but without making symmetry assumptions about the probabilities. | |
| Mar 14, 2011 at 14:54 | comment | added | mkatkov | Why not consider fast search networks with gates with proba 1/2. That creates all permutations with not equal proba due to different number of computational paths, but then one can unwind that differences by applying not equal weights for pairs of lines. Having equal odds of traveling from all inputs to all outputs by symmetry will produce equiprobable permutations. Symmetric sorting networks will produce not many different computational paths, and it is easier to analyze. | |
| Mar 14, 2011 at 13:21 | comment | added | Peter Taylor | @mjqxxxx, I calculate that in searching for a 9-gate solution to $n=5$ you would have to consider approximately 104 million cases (although this could be reduced a bit with cleverness), but for each case you would be computing 120 equations in 5 variables with cross-terms and then checking for a solution. It's probably doable with a standard desktop computer, but it requires a bit more effort because you can't so easily constrain the possible values of the probabilities. | |
| Mar 14, 2011 at 13:17 | history | edited | Peter Taylor | CC BY-SA 2.5 |
added 299 characters in body
|
| Mar 14, 2011 at 12:15 | comment | added | mjqxxxx | These are definitely checkable... am I right in thinking that the $n=5$ case is already out of reach, though, for explicit checking? | |
| Mar 14, 2011 at 1:36 | comment | added | Joe Fitzsimons | Excellent, that's a very nice observation. | |
| Mar 13, 2011 at 23:29 | comment | added | Yuval Filmus | ... even after the correction. | |
| Mar 13, 2011 at 22:32 | history | edited | Peter Taylor | CC BY-SA 2.5 |
Correction - I failed to fully expand the symmetries
|
| Mar 13, 2011 at 19:57 | comment | added | Yuval Filmus | My case enumeration failed to produce any shorter example. | |
| Mar 13, 2011 at 17:58 | history | answered | Peter Taylor | CC BY-SA 2.5 |