48
$\begingroup$

The question I am interested in is related to generating random permutations. Given a probabilistic pairwise swap gate as the basic building block, what is the most efficient way to produce a uniformly random permutation of $n$ elements? Here I take "probabilistic pairwise swap gate" to be the operation which implements a swap gate between to chosen elements $i$ and $j$ with some probability $p$ which can be freely chosen for each gate, and the identity otherwise.

I realise this is not usually the way one generates random permutations, where usually one might use something like a Fisher-Yates shuffle, however, this will not work for the application I have in mind as the allowed operations are different.

Clearly this can be done, the question is how efficiently. What is the least number of probabilistic swaps necessary to achieve this goal?

UPDATE:

Anthony Leverrier provides a method below which does indeed produce the correct distribution using $O(n^2)$ gates, with Tsuyoshi Ito providing another approach with the same scaling in the comments. However, the best lower bound I have so far seen is $\lceil \log_2(n!) \rceil$, which scales as $O(n\log n)$. So, the question still remains open: Is $O(n^2)$ the best that can be done (i.e. is there a better lower bound)? Or alternatively, is there a more efficient circuit family?

UPDATE:

Several of the answers and comments have proposed circuits which are comprised entirely of probabilistic swaps where the probability is fixed at $\frac{1}{2}$. Such a circuit cannot solve this problem for the following reason (lifted from the comments):

Imagine a circuit which uses $m$ such gates. Then there are $2^m$ equiprobable computational paths, and so any permutation must occur with probability $k 2^{−m}$ for some integer k. However, for a uniform distribution we require that $k 2^{−m}=\frac{1}{n!}$, which can be rewritten as $k n! = 2^m$. Clearly this can't be satisfied for an integer value of $k$ for $n\geq3$, since $3|n!$ (for $n\geq 3$, but $3\nmid 2^m$.

UPDATE (from mjqxxxx who is offering the bounty):

The bounty being offered is for (1) a proof that $\omega(n \log n)$ gates are required, or (2) a working circuit, for any $n$, that uses less than $n(n-1)/2$ gates.

$\endgroup$
  • 8
    $\begingroup$ @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. $\endgroup$ – Joe Fitzsimons Mar 7 '11 at 14:13
  • 4
    $\begingroup$ ok, thanks for the explanation! Note that the probabilistic swap should have proba $(n-1)/n$ between position $n-1$ and position $n$. $\endgroup$ – Anthony Leverrier Mar 7 '11 at 14:23
  • 5
    $\begingroup$ 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))$. $\endgroup$ – Anthony Leverrier Mar 7 '11 at 16:45
  • 8
    $\begingroup$ 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!). $\endgroup$ – Tsuyoshi Ito Mar 7 '11 at 22:59
  • 3
    $\begingroup$ 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) $\endgroup$ – Tsuyoshi Ito Mar 7 '11 at 23:04

11 Answers 11

17
$\begingroup$

A working algorithm that I described in a comment above is the following:

  • First start by bringing a random element with probability $1/n$ in position $n$: swap positions 1 and 2 with proba $1/2$, then 2 and 3 with proba $2/3$, ... then $n-1$ and $n$ with proba $(n-1)/n$.
  • Apply the same procedure to bring a random element in position $n-1$: swap positions 1 and 2 with prob $1/2$ ... then positions $n-2$ and $n-1$ with proba $(n-2)/(n-1)$.
  • Etc

The number of gates required by this algorithm is $(n-1)+(n-2)+ \cdots + 2+1 = n(n-1)/2 = O(n^2)$.

$\endgroup$
  • 3
    $\begingroup$ This algorithm has a connection to bubble sort. In particular consider the state space of all permutations of size n. The probability that 1st elements greater than 2nd is 1/2, swap with that probability. Assume first two elements are sorted, what is the proba 2nd element > 3rd element 2/3, etc. Therefore, it seem possible to convert sorting algorithm into swap gate circuit, where each following step should take into account conditional probabilities, arising from previous steps. Which in a sense suggest explicit inefficient method to construct such circuits. $\endgroup$ – mkatkov Mar 10 '11 at 4:53
16
$\begingroup$

This is neither an answer nor new information. Here I will try to summarize the discussions which occurred in comments about relations between this problem and sorting networks. In this post, all times are in UTC and a “comment” means a comment on the question unless stated otherwise.

A circuit consisting of probabilistic swap gates (which swap two values randomly) naturally reminds us of a sorting network, which is nothing but a circuit consisting of comparators (which swap two values depending on the order between them). Indeed, circuits for the current problem and sorting networks are related to each other in the following ways:

  • The solution by Anthony Leverrier with n(n−1)/2 probabilistic swap gates can be understood as the sorting network for the bubble sort with the comparators replaced by probabilistic swap gates with suitable probabilities. See mkatkov’s comment at March 10 4:53 on that answer for details. The sorting network for the selection sort can also be used in the same way. (In the comment at March 7 23:04, I described Anthony’s circuit as the selection sort, but that was not correct.)
  • If we just want every permutation with nonzero probability and do not care about the distribution being uniform, then every sorting network does the job when all the comparators are replaced with probability-1/2 swap gates. If we use a sorting network with O(n log n) comparators, the resulting circuit generates every permutation with probability at least 1/2O(n log n) = 1/poly(n!), as observed in my comment at March 7 22:59.
  • In this problem, it is required that the probabilistic swap gates fire independently. If we remove this restriction, every sorting network can be converted to a circuit which generates the uniform distribution, as I mentioned in the comment at March 7 23:08 and user1749 described in greater details at March 8 14:07.

These facts apparently suggest that this problem is closely related to sorting networks. However, Peter Taylor found an evidence that the relation may not be very close. Namely, not every sorting network can be converted to a desired circuit by replacing the comparators with probabilistic swap gates with suitable probabilities. The five-comparator sorting network for n=4 is a counterexample. See his comments at March 10 11:08 and March 10 14:01.

$\endgroup$
  • 3
    $\begingroup$ @mkatkov: I have seen three or four deleted answers and I do not remember which was whose, sorry. If you have found a solution with less than n(n−1)/2 gates, I would like to know the whole construction (and it is not to steal mjqxxxx’s bounty from you :) ). $\endgroup$ – Tsuyoshi Ito Mar 10 '11 at 16:29
  • 2
    $\begingroup$ @mkatkov: I am still skeptical. As I wrote in the last paragraph of this post, Peter Taylor found that the five-comparator sorting network for n=4 cannot be converted to a solution for the current problem by replacing the comparators with probabilistic swap gates. This implies that your logic cannot work for every sorting network, although it does not rule out the possibility that it somehow works for, say, the odd-even mergesort. $\endgroup$ – Tsuyoshi Ito Mar 10 '11 at 16:55
  • 1
    $\begingroup$ @mkatkov: The reason this type of solution doesn't seem to work (or at least no working example has been shown) is that the swap gates in a pairwise sorting network fire in a highly correlated fashion. In this problem, all gates fire independently, which leads to a very different space of possible circuits. $\endgroup$ – mjqxxxx Mar 10 '11 at 17:13
  • 1
    $\begingroup$ @mkatbov, each step in Anthony's network selects one of m inputs (where m ranges from n down to 2). You can't select one of m inputs with fewer than m-1 gates, so in particular you can't do it with log m gates. Beating $O(n^2)$ is probably going to require some kind of divide-and-conquer approach. $\endgroup$ – Peter Taylor Mar 10 '11 at 20:20
  • 3
    $\begingroup$ @Tsuyoshi, Yuval and I have analysed all possible 5-gate solutions for $n=4$ and eliminated them all, which strengthens the result that not all sorting networks can be converted into uniform permutation networks into a result that there exist problem sizes for which the optimal uniform permutation network requires more gates than the optimal sorting network. $\endgroup$ – Peter Taylor Mar 14 '11 at 15:23
15
+100
$\begingroup$

This isn't a full answer by any means, but it includes a result which may be useful and applies it to get some constraints on the case $n=4$ which limit the possible 5-gate solutions to 2500 easily enumerable cases.

First the general result: in any solution which permutes $n$ objects, there must be at least $n-1$ swaps which have probability $\frac{1}{2}$.

Proof: consider the permutation representation of the permutations of order $n$. These are the $n\times n$ matrices $A_\pi$ satisfying $(A_\pi)_{i,j} = [i = \pi(j)]$. Consider a swap between $i$ and $j$ with probability $p$: this has representation $(1-p)I + pA_{(i j)}$ (using cycle notation to represent the permutation). You can think of multiplication by this matrix in terms of representation theory or in Markov terms as applying the permutation $(i j)$ with probability $p$ and leaving things unchanged with probability $1-p$.

The permutation network is therefore a chain of such matrix multiplications. We start with the identity matrix and the final result will be a matrix $U$ where $U_{i,j} = \frac{1}{n}$, so we are going from a matrix of rank $n$ to a matrix of rank $1$ by multiplications - i.e. the rank is decreasing by $n-1$.

Considering the rank of the matrices $(1-p)I + pA_{(i j)}$, then, we see that they're essentially identity matrices apart from a minor $\begin{pmatrix}1-p & p \\ p & 1-p\end{pmatrix}$, so they have full rank unless $p=\frac{1}{2}$, in which case they have rank $n-1$.

Applying Sylvester's matrix inequality we therefore find that each swap decreases the rank only if $p=\frac{1}{2}$, and when this condition is met it decreases it by no more than 1. Therefore we require at least $n-1$ swaps of probability $\frac{1}{2}$.

Note that this bound can't be tightened because Anthony Leverrier's network achieves it.


Application to the case $n=4$. We already have solutions with 6 gates, so the question is whether solutions with 5 gates are possible. We now know that at least 3 of the gates must be 50/50 swaps, so we have two "free" probabilities, $p$ and $q$. There are 32 possible events (5 independent events each with two outcomes) and $4! = 24$ buckets each of which must contain at least one event. The events divide up as 8 with probability $\frac{pq}{8}$, 8 with probability $\frac{\overline{p}q}{8}$, 8 with probability $\frac{p\overline{q}}{8}$, and 8 with probability $\frac{\overline{p}\overline{q}}{8}$.

32 events into 24 buckets with no empty buckets implies that at least 16 buckets contain precisely one event, so at least two of the four probabilities given above are equal to $\frac{1}{24}$. Taking symmetries into account we have two cases: $pq = \overline{p}q = \frac{1}{3}$ or $pq = \overline{p}\overline{q} = \frac{1}{3}$.

The first case gives $p=\overline{p}=\frac{1}{2}$, $q=\frac{2}{3}$ (correction or $q=\frac{1}{3}$, unwinding the symmetry). The second case gives $pq=1-p-q+pq$, so $pq = p(1-p) = \frac{1}{3}$, which has no real solutions.

Therefore if there is a 5-gate solution we have four gates with probability $\frac{1}{2}$ and one gate with probability either $\frac{1}{3}$ or $\frac{2}{3}$. Wlog the first swap is $0\leftrightarrow 1$, and the second is either $0\leftrightarrow 2$ or $2\leftrightarrow 3$; the other three each have (no more than) five possibilities, because there's no point doing the same swap twice in a row. So we have $2\times 5^3$ swap sequences to consider and 10 ways of assigning the probabilities, leading to 2500 cases which could be enumerated and tested mechanically.

Update: Yuval Filmus and I have both enumerated and tested the cases and found no solutions, so the optimal solution for $n=4$ involves 6 gates, and examples of 6-gate solutions are found in other answers.

$\endgroup$
  • 2
    $\begingroup$ My case enumeration failed to produce any shorter example. $\endgroup$ – Yuval Filmus Mar 13 '11 at 19:57
  • $\begingroup$ ... even after the correction. $\endgroup$ – Yuval Filmus Mar 13 '11 at 23:29
  • 1
    $\begingroup$ Excellent, that's a very nice observation. $\endgroup$ – Joe Fitzsimons Mar 14 '11 at 1:36
  • 1
    $\begingroup$ @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. $\endgroup$ – Peter Taylor Mar 14 '11 at 13:21
  • 4
    $\begingroup$ 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. $\endgroup$ – mjqxxxx Mar 16 '11 at 20:15
14
$\begingroup$

The following seems to be new and relevant information:

The paper [CKKL99] shows how to get 1/n close to a uniform permutation of n elements using a switching network of depth O(log n), and hence a total of O(n log n) comparators.

This construction is not explicit, but it can be made explicit if you increase the depth to polylog(n). See the pointers in the paper [CKKL01], which also contains more information.

A previous comment already pointed out a result saying that O(n log n) switches suffice, but the difference is that in switching networks the elements being compared are fixed.


[CKKL99] Artur Czumaj, Przemyslawa Kanarek, Miroslaw Kutylowski, and Krzysztof Lo- rys. Delayed path coupling and generating random permutations via distributed stochastic processes. In Symposium on Discrete Algorithms (SODA), pages 271{ 280, 1999.

[CKKL01] Artur Czumaj, Przemyslawa Kanarek, Miroslaw Kutylowski, and Krzysztof Lo- rys. Switching networks for generating random permutations, 2001.

$\endgroup$
  • $\begingroup$ Thanks, that is certainly useful to know. I am still interested to know about the gate number for generating the exact distribution, however. $\endgroup$ – Joe Fitzsimons Mar 11 '11 at 22:17
12
$\begingroup$

Here's a somewhat interesting solution for $n=4$. The same idea also works for $n=6$.

Start with the switches $(0,1),(2,3)$ with probability $1/2$. Reducing $0,1$ to $X$ and $2,3$ to $Y$, we are in the situation $XXYY$. Apply the switches $(0,3),(1,2)$ with probability $p$. The result is $$ \begin{align*} XXYY &\text{ w.p. } (1-p)^2, \\ YYXX &\text{ w.p. } p^2, \\ XYXY &\text{ w.p. } p(1-p), \\ YXYX &\text{ w.p. } p(1-p) \end{align*} $$ Our next move is going to be $(0,2),(1,3)$ with probability $1/2$. Thus we really only care if the result of the previous stage is of the form $XXYY/YYXX$ (case A) or of the form $XYXY/YXYX$ (case B). In case A these switches will result in a uniform probability over $XXYY/XYYX/YXXY/YYXX$. In case B they will be ineffective. Therefore $p$ must satisfy $$ p(1-p) = 1/6 \Longrightarrow p = \frac{3 \pm \sqrt{3}}{6}. $$ Given that, the result is uniform.

A similar idea works for $n=6$ - you first randomly sort each half, and then "merge" them. However, even for $n=8$ I can't see how to merge the halves properly.

The interesting point about this solution is the weird probability $p$.

As a side note, the set of probabilities $p$ which can conceivably help us is given by $1/(1-\lambda)$, where $\lambda \leq 0$ goes over all eigenvalues of all representations of $S_n$ at all transpositions.

$\endgroup$
  • 1
    $\begingroup$ The weird values for $p$ are indeed encouraging, as I think there is a reasonably simple proof that if we restrict the probabilities to $1/k$ for integer $k$ then the best you can do is $O(n^2)$. $\endgroup$ – Joe Fitzsimons Mar 8 '11 at 23:11
  • 5
    $\begingroup$ A little different way for 2n elements, which is still weird in a similar sense, is to shuffle the first n elements, shuffle the last n elements, swap (i,i+n) with probability p_i for i=1,…,n, shuffle the first n elements, and shuffle the last n elements. The probabilities p_i must be chosen so that the probability that exactly k out of the n swap gates fire is equal to $\binom{n}{k}^2/\binom{2n}{n}$ and such probabilities p_i are given by (1+x_i)/2 where x_1,…,x_n are the roots of the Legendre polynomial P_n. (more) $\endgroup$ – Tsuyoshi Ito Mar 8 '11 at 23:18
  • 6
    $\begingroup$ (cont’d) A disappointing thing about the variation which I described is that it requires n(n−1)/2 probabilistic swaps when n is a power of two, that is, exactly the same number of gates as the bubble-sort solution by Anthony Leverrier. $\endgroup$ – Tsuyoshi Ito Mar 8 '11 at 23:20
  • $\begingroup$ @Tsuyoshi, your construction is clearly correct, but I wonder whether it's doing more than necessary. I don't have time to work through the analysis at the moment, but if you do then you might find it worth considering whether there exist $p_0, p_1$ such that $0\leftrightarrow 1, p=\frac{1}{2}$; $2\leftrightarrow 3, p=\frac{1}{2}$; $0\leftrightarrow 2, p=p_0$; $1\leftrightarrow 3, p=p_1$; then apply a suitable permutation of the Legendre roots (and fill in the other quarters) can work. $\endgroup$ – Peter Taylor Mar 15 '11 at 23:00
7
$\begingroup$

Consider the problem of randomly shuffling the string $XX..XY..YY$, where each block has length $n$, with a circuit consisting of probabilistic pairwise swaps. That is, all $(2n)!/(n!)^2$ strings with $n$ $X$s and $n$ $Y$s must be equally probable outputs of the circuit, given the specified input. Let $B_{2n}$ be an optimal circuit for this problem, and let $C_{2n}$ be an optimal circuit for the original problem (randomly shuffling $2n$ elements). Applying a random permutation is sufficient to randomly interleave the $X$s and $Y$s, so $\lvert{B_{2n}}\rvert \le \lvert{C_{2n}}\rvert$. On the other hand, we can shuffle $2n$ elements by shuffling the first $n$ elements, shuffling the last $n$ elements, and finally applying circuit $B_{2n}$. This implies that $\lvert{C_{2n}}\rvert \le 2\lvert{C_{n}}\rvert + \lvert{B_{2n}}\rvert$. Combining these two bounds, we can derive the following result:

  • $\lvert{B_{2n}}\rvert$ and $\lvert{C_{2n}}\rvert$ are both $o(n^2)$, or neither is.

We see that the two problems are equally difficult, at least in this sense. This result is somewhat surprising, because one might expect the $XY$-shuffle problem to be easier. In particular, the entropic argument shows that $\lvert{B_{2n}}\rvert$ is $\Omega(n)$, but gives the stronger result that $\lvert{C_{2n}}\rvert$ is $\Omega(n \log n)$.

$\endgroup$
7
$\begingroup$

Diaconis and Shahshahani 1981, "Generating a Random Permutation with Random Transpositions" shows that 1/2 n log n random transpositions (note: there is no "O" here) result in a permutation close (in total variation distance) to uniform. I'm not sure if precisely what is allowed in your application lets you use this result, but it is quite fast, and tight in that it is an example of a cut-off phenomenon. See Random Walks on Finite Groups by Saloff-Coste for a survey of similar results.

$\endgroup$
  • 1
    $\begingroup$ And presumably two nearly random permutations can be composed to produce a permutation that is even more nearly random. $\endgroup$ – mjqxxxx Mar 9 '11 at 21:36
  • 7
    $\begingroup$ ... However, it should be noted that this is not really the same problem (even allowing for an approximate rather than exact solution), because the authors consider transpositions of randomly chosen pairs of elements, not probabilistic transpositions of specified pairs of elements. $\endgroup$ – mjqxxxx Mar 9 '11 at 22:02
5
$\begingroup$

This is really a comment but too long to post as a comment. I suspect that the representation theory of the symmetric group might be useful to prove a better lower bound. Although I know almost nothing about representation theory and I may be off the mark, let me explain why it might be related to the current problem.

Note that the behavior of a circuit consisting of probabilistic swap gates can be fully specified as a probability distribution p over Sn, the group of permutations on n elements. A permutation g∈Sn can be thought of as the event that ith output is g(i)th input for all i∈{1,…,n}. Now represent a probability distribution p as a formal sum ∑g∈Snp(g)g. For example, the probabilistic swap between wires i and j with probability p is represented as (1−p)e+pτij, where e∈Sn is the identity element and τij∈Sn is the transposition between i and j.

An interesting fact about this formal sum is that the behavior of the concatenation of two independent circuits can be formally described as a product of these formal sums. Namely, if the behaviors of circuits C1 and C2 are represented as formal sums a1=∑g∈Snp1(g)g and a2=∑g∈Snp2(g)g, respectively, then the behavior of the circuit C1 followed by C2 is represented as ∑g1,g2∈Snp1(g1)p2(g2)g1g2 = a1a2.

Therefore, a desired circuit with m probabilistic swaps exactly corresponds to a way of writing the sum (1/n!)∑g∈Sng as a product of m sums each of which is of the form (1−p)e+pτij. We would like to know the minimum number m of factors.

The formal sums ∑g∈Snf(g)g, where f is a function from Sn to ℂ, equipped with naturally defined addition and multiplication, form the ring called group algebra ℂ[Sn]. Group algebra is closely related to representation theory of groups, which is a deep theory as we all know and fear :). This makes me suspect that something in representation theory might be applicable to the current problem.

Or maybe this is just far-fetched.

$\endgroup$
  • 2
    $\begingroup$ Here's what this reduces to. There are a bunch of representations of the symmetric group, that can be calculated explicitly for transpositions, with some work (usually they're only calculated explicitly for transpositions $(k,k+1)$). The initial value of each representation is the appropriate identity matrix. Applying a probabilistic swap multiplies each representation with $(1-p)I + pA_{ij}$, where $A_{ij}$ is the value of the representation at the performed swap $(ij)$. (cont'd) $\endgroup$ – Yuval Filmus Mar 11 '11 at 1:55
  • 2
    $\begingroup$ In order for the output to be uniform, we need all the representations other than the identity representation to be zero. So the probabilities $p$ should be chosen so that at least some of the matrices $(1-p)I + pA_{ij}$ are singular. The matrices $A_{ij}$ for each representation have different eigenvectors, so it's not clear what condition would enforce a particular representation to be zero. (cont'd) $\endgroup$ – Yuval Filmus Mar 11 '11 at 1:57
  • 3
    $\begingroup$ If, however, we could prove that every transposition reduces the average rank of a representation by at most $1/n^2$, say, then we would get an $n^2$ lower bound. Such a bound can be proven if we know the eigenvectors corresponding to each representation and each transposition. This information can be worked out in principle, but there's no assurance that this approach would produce anything non-trivial. $\endgroup$ – Yuval Filmus Mar 11 '11 at 1:59
  • 1
    $\begingroup$ (cont’d) and this linear transformation is exactly the matrix arising in the representation of S_n by n×n permutation matrices. Although n−1 is trivial as a lower bound on the number of gates (the entropy argument already gives a better lower bound), my hope is that it might be possible to generalize your argument to other representations to yield a better lower bound on the total number of gates. $\endgroup$ – Tsuyoshi Ito Mar 11 '11 at 16:53
  • 4
    $\begingroup$ @Yuval, @Peter: I noticed that for every representation, (1−p)I+pA_{ij} is nonsingular unless p=1/2 (because A_{ij}^2=I implies that the eigenvalues of A_{ij} are ±1). Therefore, counting the rank is useful only for lower-bounding the number of probability-1/2 gates, which was already done optimally by Peter. In other words, if the representation theory is useful in the way I suggested in this post, we need something other than counting the rank of matrices! I am not sure if that is realistic. $\endgroup$ – Tsuyoshi Ito Mar 11 '11 at 22:51
1
$\begingroup$

Anthony's $O(n^2)$ algorithm can be run in parallel by starting the next iteration of the procedure after the first two probabilistic swaps, resulting in $O(n)$ runtime.

$\endgroup$
  • 4
    $\begingroup$ I think the relevant complexity measure for this question is the number of gates and not the runtime. $\endgroup$ – Anthony Leverrier Mar 8 '11 at 22:04
  • 3
    $\begingroup$ @Anthony is correct that what I am interested in is simply the minimum number of gates necessary. $\endgroup$ – Joe Fitzsimons Mar 9 '11 at 1:40
0
$\begingroup$

If I understand correctly, if you want your circuit to be able to generate all permutations, you need at least $\lceil \log_2(n!) \rceil$ probabilistic gates, though I'm not sure how the minimal circuit can be constructed.

UPDATE:

I think that if you take the Mergesort algorithm and replace all comparisons with random choices with appropriate probabilities you'll get the circuit you are looking for.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Joe Fitzsimons Mar 7 '11 at 14:19
  • 1
    $\begingroup$ And yes, $\lceil \log_2(n!) \rceil$ is the minimum, but this is only $O(n\log(n))$. $\endgroup$ – Joe Fitzsimons Mar 7 '11 at 14:36
  • 1
    $\begingroup$ 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. $\endgroup$ – Andrew D. King Mar 7 '11 at 15:06
  • 1
    $\begingroup$ 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. $\endgroup$ – Antonio Valerio Miceli-Barone Mar 7 '11 at 15:18
  • 3
    $\begingroup$ @Andrew: I don't see how to "merge these randomly" using the gates outlined in the question. $\endgroup$ – Joe Fitzsimons Mar 7 '11 at 15:49
0
$\begingroup$

The following answer is wrong (see @joe fitzsimon's comment), but might be useful as starting point

I have a sketch proposal in $O(n\log n)$. I have hand-checked it works for $n=4$ (!) but I have no proof yet that the result is uniform beyond $n=4$.

Suppose you have a circuit $C_n$ which generates a uniform random permutation on $n$ bits. Les $S_{i,j}^{\frac 12}$ the probabilistic swap gate which swaps the bits $i$ and $j$ with probability 1/2 and does nothing with probability $1/2$. Construct the following circuit $C_{2n}$ acting on $2n$ bits:

  1. $\forall 1\le k\le n$, apply the gate $S_{k,k+n}^{1/2}$;
  2. Apply $C_n$ on the first $n$ bits;
  3. Apply $C_n$ on the last $n$ bits;
  4. $\forall 1\le k\le n$, apply the gate $S_{k,k+n}^{1/2}$.

Step 1. is needed so that bits $1$ and $n+1$ can land in the same half of the permutation, and step 4. is needed by symmetry : if $C_{2n}$ is a solution, so is $C_{2n}^-1$ obtained by applying the gates in a reverse order is also a solution.

The size of this family of circuits obeys the following recursion relation : $$ |C_{2n}| = 2|C_n|+2n $$ with, obviously, $|C_1|=0$. One then easily sees that $|C_n|=n\log n$.

Then remains the obvious question : do these circuits perform uniform permutations ? No, see first comment below

$\endgroup$
  • 6
    $\begingroup$ I don't believe that these do perform uniform permutations. In fact, I think it is impossible to do exactly with such gates if you fix the probability to be 1/2. The reason for this is simple: imagine a circuit which uses $m$ such gates. Then there are $2^{m}$ equiprobable computational paths, and so any permutation must occur with probability $k 2^{-m}$ for some integer $k$. However, for a uniform distribution we require that $k 2^{-m} = \frac{1}{n!}$. Clearly this can't be satisfied for an integer value of $k$ for $n\geq 3$. $\endgroup$ – Joe Fitzsimons Mar 8 '11 at 16:35
  • $\begingroup$ Indeed. I forgot too check the uniformity for $n=4$... $\endgroup$ – Frédéric Grosshans Mar 8 '11 at 17:26

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.