Timeline for What is the most efficient way to generate a random permutation from probabilistic pairwise swaps?
Current License: CC BY-SA 2.5
50 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 1, 2019 at 17:57 | comment | added | Daniel Lubarov | If we're okay with swap gate probabilities which depend on prior swap gates, couldn't we randomize a permutation network rather than a sorting network? That seems preferable since there are simple and practical n log(n) permutation networks, i.e. Benes or Waksman networks. | |
| Mar 16, 2011 at 20:13 | history | bounty ended | mjqxxxx | ||
| Mar 13, 2011 at 17:58 | answer | added | Peter Taylor | timeline score: 15 | |
| Mar 11, 2011 at 22:11 | answer | added | Manu | timeline score: 14 | |
| Mar 11, 2011 at 20:01 | comment | added | Tsuyoshi Ito | @Peter: I know that that is not the answer to the question, but it might be worth posting it as an answer. | |
| Mar 11, 2011 at 16:19 | comment | added | Peter Taylor | For those who aren't following all the comments to answers below, considering the ranks of matrices in the permutation representation of $S_n$ allows us to prove a requirement that there be at least $n-1$ gates with swap probability $1/2$. | |
| Mar 10, 2011 at 19:21 | answer | added | Tsuyoshi Ito | timeline score: 5 | |
| Mar 10, 2011 at 15:58 | answer | added | Tsuyoshi Ito | timeline score: 16 | |
| Mar 10, 2011 at 14:04 | history | edited | Joe Fitzsimons | CC BY-SA 2.5 |
added 736 characters in body
|
| Mar 10, 2011 at 14:01 | comment | added | Peter Taylor | @Tsuyoshi, fair comment. I redid the analysis with $0\leftrightarrow 2$ prob p, $1\leftrightarrow 3$ prob q, $0\leftrightarrow 1$ prob r, $2\leftrightarrow 3$ prob s, $1\leftrightarrow 2$ prob t. Input 0 to output 3 has prob $ps$; $P(2\rightarrow 3)=(1-p)s$; and so $p=s=1/2$. Similarly $1\rightarrow 0$ and $3\rightarrow 0$ give $q=r=1/2$, and it's reduced to the symmetric case I considered. | |
| Mar 10, 2011 at 11:50 | comment | added | Tsuyoshi Ito | @Peter: (1) I am skeptical about the “reused for symmetry” reasoning. See a construction in my comments on Yuval’s answer, which assigns different probabilities to apparently “symmetric” swap gates. (2) But your conclusion seems correct: the five-comparator sorting network for n=4 cannot be converted to a desired circuit by replacing the comparators with probabilistic swap gates (if my calculation is correct). | |
| Mar 10, 2011 at 11:08 | comment | added | Peter Taylor | As a note on @Tsuyoshi's comments doubting that all sorting networks can be turned into permutation networks, the five-swap network for n=4 consisting of $0\leftrightarrow 2$ prob p, $1\leftrightarrow 3$ prob p, $0\leftrightarrow 1$ prob q, $2\leftrightarrow 3$ prob q, $1\leftrightarrow 2$ prob r (the example optimal sorting network for n=4 on Wikipedia, probabilities p and q reused for symmetry) leads via consideration of the possible destinations of input 0 to $p=q=1/2$, and then for the 24 possible outputs to have equal probabilities we require $r=1-r=r+(1-r)=16/24$ | |
| Mar 10, 2011 at 1:25 | comment | added | mjqxxxx | @Tsuyoshi: I'm the one that offered the bounty, so I thought I was supposed to explain the conditions (and I wasn't sure where else to put that explanation). If not, I apologize... either you or @Joe should feel free to edit the question to clarify the situation. | |
| Mar 9, 2011 at 22:30 | comment | added | Tsuyoshi Ito | @mjqxxxx: I think that you should at least include your name in your edit. Actually I do not like the idea of other people than the asker editing the question to state the criteria of an open bounty in general, but I am in no position to complain about it because I am not the asker of this question. | |
| S Mar 9, 2011 at 22:17 | history | suggested | mjqxxxx | CC BY-SA 2.5 |
edited to describe what would be required to be awarded the bounty
|
| Mar 9, 2011 at 22:10 | review | Suggested edits | |||
| S Mar 9, 2011 at 22:17 | |||||
| Mar 9, 2011 at 22:03 | history | bounty started | mjqxxxx | ||
| Mar 9, 2011 at 20:34 | answer | added | Jason Morton | timeline score: 8 | |
| Mar 9, 2011 at 19:35 | answer | added | mjqxxxx | timeline score: 7 | |
| Mar 9, 2011 at 17:01 | comment | added | Antonio Valerio Miceli-Barone | Yes. I thought that time-homogeneous chains may be possibly more simple to work with. | |
| Mar 9, 2011 at 16:02 | comment | added | Joe Fitzsimons | @user1749: I don't see why that is a problem, I wasn't implying that it be time-homogeneous. That said, you can make an equivalent time-homogeneous chain by adding a counter to the state of the system which gets incremented by every swap and using a more complicated transition in which the location of the swap is conditioned on the counter. | |
| Mar 9, 2011 at 15:55 | comment | added | Antonio Valerio Miceli-Barone | Therefore, if the circuit generates an uniformly random permutation, the DTMC reaches a uniform stationary distribution in exactly L steps. | |
| Mar 9, 2011 at 15:50 | comment | added | Antonio Valerio Miceli-Barone | This is how I would do it: Consider a circuit of L sequential gates. Define the state space of the DTMC as $X\equiv Permutations(n) \times \mathbb{Z}/L\mathbb{Z}$. That is, the state of the DTMC is the pair $(curPerm,\, pc)$. For each value of the program counter in $[0,\,L-2]$ the possible next states are $(curPerm,\, pc+1)$ and $(swap(curPerm,\,i(pc),\,j(pc)),\, pc+1)$. For the value of the program counter equal to $L-1$, its value in the next state is defined to be chosen uniformly randomly. | |
| Mar 9, 2011 at 15:43 | comment | added | Antonio Valerio Miceli-Barone | How do you reduce your system to a markov chain, considering that at each step the swap gate operates between different lines? | |
| Mar 9, 2011 at 15:04 | history | edited | Joe Fitzsimons | CC BY-SA 2.5 |
added 496 characters in body
|
| Mar 8, 2011 at 22:46 | answer | added | Yuval Filmus | timeline score: 12 | |
| Mar 8, 2011 at 22:01 | answer | added | Dave | timeline score: 1 | |
| Mar 8, 2011 at 21:05 | answer | added | Anthony Leverrier | timeline score: 17 | |
| Mar 8, 2011 at 19:08 | comment | added | Joe Fitzsimons | @Anthony: Perhaps you should post your method as an answer, since it is at least a working solution to the problem even if we have not yet managed to determine its optimality. None of the current answers give working circuits. | |
| Mar 8, 2011 at 16:51 | comment | added | Joe Fitzsimons | @Tsuyoshi: I think you have hit the nail on the head about the lack of ability to condition on previous results is causing the trouble. Feel's like there is probably some result about Markov chains that I am blissfully unaware of which would give a tight bound. | |
| Mar 8, 2011 at 15:58 | answer | added | Frédéric Grosshans | timeline score: 0 | |
| Mar 8, 2011 at 14:07 | comment | added | Antonio Valerio Miceli-Barone | Indeed, if you were able to condition the swap probability on the outcome of the previous swaps you could transform any sorting network in a corresponding random permutation network in this way: Consider a $2 \times n$ matrix, with the identity permutation in the first row and a random permutation on the second row. Sorting the columns according to the second row yields a random permutation in the first row (the inverse of the initial one). Thus, the sorting algorithm compares randomly generated numbers, however, in the general case, the outcomes of these comparisons are not independent. | |
| Mar 8, 2011 at 4:07 | history | edited | Kaveh |
edited tags
|
|
| Mar 8, 2011 at 2:23 | history | tweeted | twitter.com/#!/StackCSTheory/status/44946291465265154 | ||
| Mar 7, 2011 at 23:08 | comment | added | Tsuyoshi Ito | (cont’d) If the probability can depend on whether the previous gates fired or not, then any sorting network can be converted to a circuit which generates permutations uniformly at random, but this is a massive weakening of the requirement of independence. | |
| Mar 7, 2011 at 23:06 | comment | added | Tsuyoshi Ito | (cont’d) Although this suggests that we may be able to construct a more efficient circuit by using a more efficient sorting network, I doubt that we can construct a desired circuit for 8 elements by replacing the comparators in the sorting network for, say, bitonic sort (Figure 7) with probabilistic swaps. The difficulty in this approach seems to come from the requirement that the probabilistic swap gates fire independently from each other. (more) | |
| Mar 7, 2011 at 23:04 | comment | added | Tsuyoshi Ito | Back to the original problem. Note that the O(n^2) solution which Anthony described can be viewed as replacing each comparator in the sorting network representing the selection sort with a probabilistic swap gate with a suitable probability. (more) | |
| Mar 7, 2011 at 22:59 | comment | added | Tsuyoshi Ito | This is different from what you want, but there is a family of circuits of size O(n log n) which generate every permutation with probability at least 1/p(n!) for some polynomial p: consider a sorting network with size O(n log n) and replace each comparator with a probability-1/2 swap gate. Because of the correctness of the sorting network, every permutation has to arise with nonzero probability, which is necessarily at least 1/2^{O(n log n)} = 1/poly(n!). | |
| Mar 7, 2011 at 16:50 | comment | added | Joe Fitzsimons | @Anthony: I just noticed my comment missed a closing dollar, but that scaling should have read $O(n\log n)$, so it is in line with your calculation. | |
| Mar 7, 2011 at 16:45 | comment | added | Anthony Leverrier | In terms of entropy required, the algorithm needs $(n-1) h(1/2) + (n-2) h(1/3) + \cdots + (n-k) h(1/(k+1)) + \cdots + h(1/n)$ random bits where $h(.)$ is the binary entropy function. I cannot compute that sum exactly but it is $O(n \log_2(n)^2)$ according to mathematica ... while the optimum is at least $O(n \log_2(n))$. | |
| Mar 7, 2011 at 16:32 | comment | added | Joe Fitzsimons | @Anthony: Yes, alternatively, if you look at how it is nested you should see that qubits $1$ to $n-2$ get permuted twice in a row (I guess this is simply a different way of looking at the same thing), and eliminating this seems to give the same $O(n^2)$ scaling. However, the best lower bound I see is $\lceil log_2(n!) \rceil$, which is $O(n\log n), so I am unsure of whether this is the best you can do or if there is a more efficient scheme. | |
| Mar 7, 2011 at 16:12 | comment | added | Anthony Leverrier | @Joe: in your construction, applying $C$ before the probabilistic swap seems to be overkill. It should be enough to bring in position $n$ one of the $n$ elements with probability $1/n$. To do this, swap positions 1 and 2 with probability 1/2, then 2 and 3 with proba 2/3 ... then $n-1$ and $n$ with proba $(n-1)/n$. Then, apply $C$ over the $n-1$ first elements. This seems to give a complexity $O(n^2)$ instead of $O(2^n)$ with your algorithm. | |
| Mar 7, 2011 at 14:24 | comment | added | Joe Fitzsimons | @Anthony: Yes, sorry. | |
| Mar 7, 2011 at 14:23 | comment | added | Anthony Leverrier | ok, thanks for the explanation! Note that the probabilistic swap should have proba $(n-1)/n$ between position $n-1$ and position $n$. | |
| Mar 7, 2011 at 14:13 | comment | added | Joe Fitzsimons | @Anthony: Perhaps it's not obvious, but you can: Imagine that circuit $C$ creates a uniform distribution of permutations of the first $n-1$ elements. Then $C$ followed by a probabilistic swap (with probability 0.5) between position $n-1$ and position $n$ will produce a uniformly random choice for position $n$. If you follow this by applying $C$ again to the first $n-1$ elements, you should get a uniformly random distribution. | |
| Mar 7, 2011 at 13:37 | comment | added | Anthony Leverrier | Is it obvious that one can simulate the uniform distribution exactly with this technique? I would expect that one can approach the uniform distribution arbitrarily well as the number of gates increases but an exact convergence for any $n$ seems somewhat surprising. | |
| Mar 7, 2011 at 13:05 | answer | added | Antonio Valerio Miceli-Barone | timeline score: 0 | |
| Mar 7, 2011 at 12:59 | comment | added | Joe Fitzsimons | @Anthony: Sorry. I assume $i$, $j$ and $p$ are fixed for each gate, but in constructing a circuit of such gates they can be freely chosen (not restricted to nearest neighbours, etc.). However, $i$ and $j$ can not be chosen randomly, which I guess is why you ask. The only randomness introduced should come from the probability $p_k$ of each gate $k$ implementing a swap versus the identity. | |
| Mar 7, 2011 at 12:55 | comment | added | Anthony Leverrier | How do you pick elements $i$ and $j$ in your case? | |
| Mar 7, 2011 at 12:39 | history | asked | Joe Fitzsimons | CC BY-SA 2.5 |