<p>A working algorithm that I described in a comment above is the following:</p>

<ul>
<li>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$.</li>
<li>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)$.</li>
<li>Etc</li>
</ul>

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

CC BY-SA 2.5
2011-03-10T04:53:45.920Z
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.
mkatkov
CC BY-SA 2.5
2011-03-08T21:05:09.607Z
2011-03-08T21:05:09.607Z
Anthony Leverrier
<p>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 <a href="http://en.wikipedia.org/wiki/Sorting_network" rel="nofollow noreferrer">sorting networks</a>.  In this post, all times are in UTC and a “comment” means a comment on the question unless stated otherwise.</p>

<p>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:</p>

<ul>
<li>The <a href="https://cstheory.stackexchange.com/questions/5321/what-is-the-most-efficient-way-to-generate-a-random-permutation-from-probabilisti/5360#5360">solution by Anthony Leverrier</a> with <i>n</i>(<i>n</i>−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.)</li>
<li>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(<i>n</i> log <i>n</i>) comparators, the resulting circuit generates every permutation with probability at least 1/2<sup>O(<i>n</i> log <i>n</i>)</sup> = 1/poly(<i>n</i>!), as observed in my comment at March 7 22:59.</li>
<li>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.</li>
</ul>

<p>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 <i>n</i>=4 is a counterexample.  See his comments at March 10 11:08 and March 10 14:01.</p>

CC BY-SA 2.5
2011-03-10T16:21:04.480Z
@Ito the answer I deleted is actually the first half of pairwise sorting network (see Wikipedia), adding second half should do the job, although, it is slightly less efficient than expected optimum.
mkatkov
CC BY-SA 2.5
2011-03-10T16:29:57.773Z
@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 :) ).
Tsuyoshi Ito
CC BY-SA 2.5
2011-03-10T16:49:38.577Z
@Ito I will miss the details again. Take any sorting network e.g. odd-even merge sorting network, or pairwise sorting network. Gates there are operating independently. Run all permutations through the network, assign the probabilities of the swap to the gate, according to swapping fraction. Theses networks has O(n log^2 n) gates. In my opinion you have the key ingredients for the solution, and if I did not mix things up you deserve bounty.
mkatkov
CC BY-SA 2.5
2011-03-10T16:55:31.527Z
@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.
Tsuyoshi Ito
CC BY-SA 2.5
2011-03-10T17:13:17.277Z
@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.
mjqxxxx
CC BY-SA 2.5
2011-03-10T19:47:06.193Z
To rephrase sorting networks seem to equalize marginal distributions of elements across position, not the joint one, which is required for the problem at hand. Anthony solution seem avoid this by dropping elements from the network. So if one can reduce each step in Anthony algorithm to log n gates that solves the problem.
mkatkov
CC BY-SA 2.5
2011-03-10T20:20:11.347Z
@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.
Peter Taylor
CC BY-SA 2.5
2011-03-11T15:59:38.177Z
Fast sorting networks I tried does not produce all permutations, sorting networks repeated twice produce all permutations, but it is not clear that this way is possible to obtain uniform distribution of permutations (my experiments did not).
mkatkov
CC BY-SA 2.5
2011-03-11T16:41:19.643Z
@mkatkov: “Fast sorting networks I tried does not produce all permutations”: That cannot happen.  Every sorting network (with the comparators replaced by probabilistic swap gates with probability strictly between 0 and 1) produces all the n! permutations with nonzero probability (although the distribution may not be uniform).  I recommend you to double-check that you used a correct sorting network.
Tsuyoshi Ito
CC BY-SA 2.5
2011-03-11T18:06:27.333Z
@Ito It is not necessary. For sorting network all permutations converge to ordered state. Symmetric networks like bubble-sort are guaranteed to produce all permutations. So, I suggest to compute switching probabilities in sorting network, assign to the gates, and reverse the stream to produce random permutations.
mkatkov
CC BY-SA 2.5
2011-03-11T19:21:36.573Z
@mkatkov: “For sorting network all permutations converge to ordered state.”  That implies that all permutations arise with nonzero probability if we decide the orders randomly, as I stated.
Tsuyoshi Ito
CC BY-SA 2.5
2011-03-12T04:42:14.557Z
@Ito I was wrong. Sorting networks produce non-equal probabilities at least due to different number of computational path. To correct that one can compute n^2 matrix of paths between input k and output m. For fast sorting networks the depth is $log^2 n$, and therefore there are no more than $log^4 n$ distinct length pairs. Swapping adjacent lines with proba = inv odds to equalize the relative weights one can equalize all computational paths, that will require additional depth of $log^4 n$. I cannot figure out why if all paths are equal permutations will have different probabilities.
mkatkov
CC BY-SA 2.5
2011-03-14T15:23:11.543Z
@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.
Peter Taylor
CC BY-SA 2.5
2011-03-10T15:58:26.113Z
2011-03-10T16:48:14.573Z
2017-04-13T12:32:28.743Z
Tsuyoshi Ito
<p>The following seems to be new and relevant information:</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

<hr>

<p>[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.</p>

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

CC BY-SA 2.5
2011-03-11T22:17:01.440Z
Thanks, that is certainly useful to know. I am still interested to know about the gate number for generating the exact distribution, however.
Joe Fitzsimons
CC BY-SA 2.5
2011-03-11T22:11:40.103Z
2011-03-11T22:11:40.103Z
Manu
<p>Here's a somewhat interesting solution for $n=4$. The same idea also works for $n=6$.</p>

<p>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 &amp;\text{ w.p. } (1-p)^2, \\
YYXX &amp;\text{ w.p. } p^2, \\
XYXY &amp;\text{ w.p. } p(1-p), \\
YXYX &amp;\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.</p>

<p>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.</p>

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

<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.</p>

CC BY-SA 2.5
2011-03-15T23:00:50.253Z
@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.
Peter Taylor
CC BY-SA 2.5
2011-03-08T23:11:30.850Z
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)$.
Joe Fitzsimons
CC BY-SA 2.5
2011-03-08T23:18:35.580Z
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](http://en.wikipedia.org/wiki/Legendre_polynomials) P_n.  (more)
Tsuyoshi Ito
CC BY-SA 2.5
2011-03-08T23:20:43.160Z
(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.
Tsuyoshi Ito
CC BY-SA 2.5
2011-03-08T22:46:47.953Z
2011-03-08T22:46:47.953Z
Yuval Filmus
<p>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.</p>

<p>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}$.</p>

<p>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$.</p>

<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$.</p>

<p>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 &amp; p \\ p &amp; 1-p\end{pmatrix}$, so they have full rank unless $p=\frac{1}{2}$, in which case they have rank $n-1$.</p>

<p>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}$.</p>

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

<hr />

<p>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}$.</p>

<p>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}$.</p>

<p>The first case gives $p=\overline{p}=\frac{1}{2}$, $q=\frac{2}{3}$ (<strong>correction</strong> 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.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 2.5
2011-03-16T20:15:24.073Z
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.
mjqxxxx
CC BY-SA 2.5
2011-03-13T19:57:22.073Z
My case enumeration failed to produce any shorter example.
Yuval Filmus
CC BY-SA 2.5
2011-03-13T23:29:22.060Z
... even after the correction.
Yuval Filmus
CC BY-SA 2.5
2011-03-14T01:36:36.203Z
Excellent, that's a very nice observation.
Joe Fitzsimons
CC BY-SA 2.5
2011-03-14T12:15:47.447Z
These are definitely checkable... am I right in thinking that the $n=5$ case is already out of reach, though, for explicit checking?
mjqxxxx
CC BY-SA 2.5
2011-03-14T13:21:36.077Z
@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.
Peter Taylor
CC BY-SA 2.5
2011-03-14T14:54:03.847Z
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.
mkatkov
CC BY-SA 2.5
2011-03-14T15:17:54.620Z
@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.
Peter Taylor
CC BY-SA 2.5
2011-03-14T15:43:26.130Z
@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.
mkatkov
CC BY-SA 2.5
2011-03-14T16:45:27.020Z
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
mkatkov
CC BY-SA 2.5
2011-03-14T17:25:43.287Z
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.
mkatkov
CC BY-SA 3.0
2011-03-13T17:58:41.137Z
2015-01-30T17:59:18.773Z
2015-01-30T17:59:18.773Z
Peter Taylor
<p>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.</p>

CC BY-SA 2.5
2011-03-09T21:36:15.307Z
And presumably two nearly random permutations can be composed to produce a permutation that is even more nearly random.
mjqxxxx
CC BY-SA 2.5
2011-03-09T22:02:49.637Z
... 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.
mjqxxxx
CC BY-SA 2.5
2011-03-09T20:34:16.823Z
2011-03-09T20:34:16.823Z
Jason Morton
<p>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:</p>

<ul>
<li>$\lvert{B_{2n}}\rvert$ and $\lvert{C_{2n}}\rvert$ are both $o(n^2)$, or neither is.</li>
</ul>

<p>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)$.</p>

CC BY-SA 2.5
2011-03-09T19:35:17.670Z
2011-03-09T19:35:17.670Z
mjqxxxx
<p>This is really a comment but too long to post as a comment.  I suspect that the <a href="http://en.wikipedia.org/wiki/Representation_theory_of_the_symmetric_group">representation theory of the symmetric group</a> 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.</p>

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

<p>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 <i>C</i><sub>1</sub> and <i>C</i><sub>2</sub> are represented as formal sums <i>a</i><sub>1</sub>=∑<sub><i>g</i>∈S<sub><i>n</i></sub></sub><i>p</i><sub>1</sub>(<i>g</i>)<i>g</i> and <i>a</i><sub>2</sub>=∑<sub><i>g</i>∈S<sub><i>n</i></sub></sub><i>p</i><sub>2</sub>(<i>g</i>)<i>g</i>, respectively, then the behavior of the circuit <i>C</i><sub>1</sub> followed by <i>C</i><sub>2</sub> is represented as ∑<sub><i>g</i><sub>1</sub>,<i>g</i><sub>2</sub>∈S<sub><i>n</i></sub></sub><i>p</i><sub>1</sub>(<i>g</i><sub>1</sub>)<i>p</i><sub>2</sub>(<i>g</i><sub>2</sub>)<i>g</i><sub>1</sub><i>g</i><sub>2</sub> = <i>a</i><sub>1</sub><i>a</i><sub>2</sub>.</p>

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

<p>The formal sums ∑<sub><i>g</i>∈S<sub><i>n</i></sub></sub><i>f</i>(<i>g</i>)<i>g</i>, where <i>f</i> is a function from S<sub><i>n</i></sub> to ℂ, equipped with naturally defined addition and multiplication, form the ring called <a href="http://en.wikipedia.org/wiki/Group_ring">group algebra</a> ℂ[S<sub><i>n</i></sub>].  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.</p>

<p>Or maybe this is just far-fetched.</p>

CC BY-SA 2.5
2011-03-10T20:27:43.023Z
Surely using $\mathbb{R}$ rather than $\mathbb{C}$ would sufficient? ;)
Peter Taylor
CC BY-SA 2.5
2011-03-10T20:30:21.897Z
@Peter: You are right.  I wrote ℂ just because it seems that ℂ is more common than ℝ in representation theory (judging from the very little I know).
Tsuyoshi Ito
CC BY-SA 2.5
2011-03-11T01:55:09.543Z
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)
Yuval Filmus
CC BY-SA 2.5
2011-03-11T01:57:02.053Z
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)
Yuval Filmus
CC BY-SA 2.5
2011-03-11T01:59:01.320Z
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.
Yuval Filmus
CC BY-SA 2.5
2011-03-11T12:41:28.457Z
@Yuval: Thank you for the detailed comments.  I agree that it reduces to proving some lower bound on the ranks of the matrices (1−p)I+pA_{ij}.  I lack the knowledge and the experience in representation theory necessary to actually try this approach or even to judge whether it is plausible to hope that this approach produces anything nontrivial.
Tsuyoshi Ito
CC BY-SA 2.5
2011-03-11T13:41:07.440Z
@Yuval, surely each such $(1-p)I+pA_{ij}$ is an order-$n$ identity matrix apart from a minor $[[1-p,p][p,1-p]]$? That has determinant $1-2p$, so is singular iff $p = 1/2$. We require the chain of matrices to send $I$ to a flat $B_{ij}=1/n$ so the chain must be singular, but (superficially, at least) all that gets us is that at least one swap probability is $1/2$.
Peter Taylor
CC BY-SA 2.5
2011-03-11T13:51:41.580Z
Correction: we get a bit more. The chain maps a matrix of rank $n$ to one of rank $1$ via multiplications by matrices of rank $n$ or $n-1$ (when $p=1/2$). Therefore by Sylvester’s rank inequality there must be at least $n-1$ swaps with $p=1/2$.
Peter Taylor
CC BY-SA 2.5
2011-03-11T13:54:17.413Z
@Peter: No, I think that you are considering the representation of S_n by n×n permutation matrices, but that is merely one of the many representations of S_n.  (Actually I had been confused by the same thing first.)  In addition, I think that Yuval is talking about irreducible representations.  The representation by n×n permutation matrices is not irreducible for n≥2.
Tsuyoshi Ito
CC BY-SA 2.5
2011-03-11T14:00:57.797Z
And it occurs to me that Anthony Leverrier's solution achieves that lower bound of $n-1$ swaps with $p=1/2$.
Peter Taylor
CC BY-SA 2.5
2011-03-11T14:06:24.237Z
@Tsuyoshi, ok, but I *think* my analysis is still correct.
Peter Taylor
CC BY-SA 2.5
2011-03-11T14:08:31.660Z
@Peter: Except for the claim “all that gets us is that at least one swap probability is 1/2” (even with the correction to n−1 gates).
Tsuyoshi Ito
CC BY-SA 2.5
2011-03-11T16:15:48.400Z
@Tsuyoshi, the parenthetical "superficially, at least" was there for a reason ;)
Peter Taylor
CC BY-SA 2.5
2011-03-11T16:50:13.100Z
@Peter: (1) Fair enough.  (2) An equivalent way of stating your finding is that if each of the n output gates of a circuit has the uniform marginal distribution (which is a weaker assumption than the permutation being uniform), then the circuit necessarily contains at least n−1 probability-1/2 swap gates.  Instead of using the terminology of representation theory, we can state its proof in terms of Markov chain; we can consider a circuit as a linear transformation which maps a probability distribution over n wires to another, (more)
Tsuyoshi Ito
CC BY-SA 2.5
2011-03-11T16:53:48.730Z
(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.
Tsuyoshi Ito
CC BY-SA 2.5
2011-03-11T18:57:16.827Z
It is indeed trivial as a lower bound on the total number of gates, but it might be possible to combine it with the information-theoretic approach to get useful information about what the other probabilities can be. I'm tempted to investigate what we can get by requiring the first n/2 gates to be $2i\leftrightarrow 2i+1$ with $p=1/2$ and the last n/2-1 to be $2i-1\leftrightarrow 2i$.
Peter Taylor
CC BY-SA 2.5
2011-03-11T22:51:21.913Z
@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.
Tsuyoshi Ito
CC BY-SA 2.5
2011-03-10T19:21:25.170Z
2011-03-10T19:21:25.170Z
Tsuyoshi Ito
<p>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.</p>

CC BY-SA 2.5
2011-03-08T22:04:09.033Z
I think the relevant complexity measure for this question is the number of gates and not the runtime.
Anthony Leverrier
CC BY-SA 2.5
2011-03-09T01:40:37.560Z
@Anthony is correct that what I am interested in is simply the minimum number of gates necessary.
Joe Fitzsimons
CC BY-SA 2.5
2011-03-08T22:01:23.823Z
2011-03-08T22:01:23.823Z
Dave
<p><strong>The following answer is wrong (see @joe fitzsimon's comment), but might be useful as starting point</strong></p>

<p>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$. </p>

<p>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:</p>

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

<p>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.</p>

<p>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$.</p>

<p>Then remains the obvious question : do these circuits perform uniform permutations ? <strong>No, see first comment below</strong></p>

CC BY-SA 2.5
2011-03-08T16:35:26.503Z
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$.
Joe Fitzsimons
CC BY-SA 2.5
2011-03-08T17:26:56.957Z
Indeed. I forgot too check the uniformity for $n=4$...
Frédéric Grosshans
CC BY-SA 2.5
2011-03-08T15:58:17.067Z
2011-03-08T17:54:46.593Z
2011-03-08T17:54:46.593Z
Frédéric Grosshans
<p>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.</p>

<p>UPDATE:</p>

<p>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.</p>

CC BY-SA 2.5
2011-03-07T14:19:27.483Z
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.
Joe Fitzsimons
CC BY-SA 2.5
2011-03-07T14:36:44.533Z
And yes, $\lceil \log_2(n!) \rceil$ is the minimum, but this is only $O(n\log(n))$.
Joe Fitzsimons
CC BY-SA 2.5
2011-03-07T15:06:03.047Z
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.
Andrew D. King
CC BY-SA 2.5
2011-03-07T15:18:13.637Z
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.
Antonio Valerio Miceli-Barone
CC BY-SA 2.5
2011-03-07T15:49:18.810Z
@Andrew: I don't see how to "merge these randomly" using the gates outlined in the question.
Joe Fitzsimons
CC BY-SA 2.5
2011-03-07T18:06:02.233Z
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.
Andrew D. King
CC BY-SA 2.5
2011-03-07T13:05:07.017Z
2011-03-07T13:46:06.967Z
2011-03-07T13:46:06.967Z
Antonio Valerio Miceli-Barone
<p>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.</p>

<p>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.</p>

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

<p>UPDATE:</p>

<p>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?</p>

<p>UPDATE:</p>

<p>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):</p>

<p>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$.</p>

<p>UPDATE (from mjqxxxx who is offering the bounty):</p>

<p>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.</p>

CC BY-SA 4.0
2019-05-01T17:57:36.347Z
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.
Daniel Lubarov
CC BY-SA 2.5
2011-03-07T12:55:22.287Z
How do you pick elements $i$ and $j$ in your case?
Anthony Leverrier
CC BY-SA 2.5
2011-03-07T12:59:16.897Z
@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.
Joe Fitzsimons
CC BY-SA 2.5
2011-03-07T13:37:28.290Z
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.
Anthony Leverrier
CC BY-SA 2.5
2011-03-07T14:13:01.170Z
@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.
Joe Fitzsimons
CC BY-SA 2.5
2011-03-07T14:23:08.480Z
ok, thanks for the explanation! Note that the probabilistic swap should have proba $(n-1)/n$ between position $n-1$ and position $n$.
Anthony Leverrier
CC BY-SA 2.5
2011-03-07T14:24:20.147Z
@Anthony: Yes, sorry.
Joe Fitzsimons
CC BY-SA 2.5
2011-03-07T16:12:53.483Z
@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.
Anthony Leverrier
CC BY-SA 2.5
2011-03-07T16:32:02.287Z
@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.
Joe Fitzsimons
CC BY-SA 2.5
2011-03-07T16:45:39.493Z
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))$.
Anthony Leverrier
CC BY-SA 2.5
2011-03-07T16:50:49.113Z
@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.
Joe Fitzsimons
CC BY-SA 2.5
2011-03-07T22:59:40.590Z
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](http://en.wikipedia.org/wiki/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!).
Tsuyoshi Ito
CC BY-SA 2.5
2011-03-07T23:04:32.037Z
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)
Tsuyoshi Ito
CC BY-SA 2.5
2011-03-07T23:06:59.710Z
(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](http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/bitonic/bitonicen.htm) (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)
Tsuyoshi Ito
CC BY-SA 2.5
2011-03-07T23:08:22.190Z
(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.
Tsuyoshi Ito
CC BY-SA 2.5
2011-03-08T14:07:15.393Z
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.
Antonio Valerio Miceli-Barone
CC BY-SA 2.5
2011-03-08T16:51:50.750Z
@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.
Joe Fitzsimons
CC BY-SA 2.5
2011-03-08T19:08:41.147Z
@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.
Joe Fitzsimons
CC BY-SA 2.5
2011-03-09T15:43:16.533Z
How do you reduce your system to a markov chain, considering that at each step the swap gate operates between different lines?
Antonio Valerio Miceli-Barone
CC BY-SA 2.5
2011-03-09T15:50:37.710Z
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.
Antonio Valerio Miceli-Barone
CC BY-SA 2.5
2011-03-09T15:55:00.043Z
Therefore, if the circuit generates an uniformly random permutation, the DTMC reaches a uniform stationary distribution in exactly L steps.
Antonio Valerio Miceli-Barone
CC BY-SA 2.5
2011-03-09T16:02:55.160Z
@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.
Joe Fitzsimons
CC BY-SA 2.5
2011-03-09T17:01:44.760Z
Yes. I thought that time-homogeneous chains may be possibly more simple to work with.
Antonio Valerio Miceli-Barone
CC BY-SA 2.5
2011-03-09T22:30:09.237Z
@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.
Tsuyoshi Ito
CC BY-SA 2.5
2011-03-10T01:25:47.667Z
@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.
mjqxxxx
CC BY-SA 2.5
2011-03-10T11:08:54.410Z
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$
Peter Taylor
CC BY-SA 2.5
2011-03-10T11:50:42.173Z
@Peter: (1) I am skeptical about the “reused for symmetry” reasoning.  See a construction in my comments on [Yuval’s answer](http://cstheory.stackexchange.com/questions/5321/what-is-the-most-efficient-way-to-generate-a-random-permutation-from-probabilisti/5364#5364), 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).
Tsuyoshi Ito
CC BY-SA 2.5
2011-03-10T14:01:09.957Z
@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.
Peter Taylor
CC BY-SA 2.5
2011-03-11T16:19:32.203Z
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$.
Peter Taylor
CC BY-SA 2.5
2011-03-11T20:01:06.883Z
@Peter: I know that that is not the answer to the question, but it might be worth posting it as an answer.
Tsuyoshi Ito
<co.combinatorics><randomness><probabilistic-circuits>
What is the most efficient way to generate a random permutation from probabilistic pairwise swaps?
Joe Fitzsimons
# What is the most efficient way to generate a random permutation from probabilistic pairwise swaps?

(Asked by: username_0 on 2011-03-07)

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.

**Tags:** co.combinatorics, randomness, probabilistic-circuits
> **Comments:**
> **username_2**: How do you pick elements $i$ and $j$ in your case?  
> **username_0**: @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.  
> **username_2**: 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.  
> **username_0**: @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.  
> **username_2**: ok, thanks for the explanation! Note that the probabilistic swap should have proba $(n-1)/n$ between position $n-1$ and position $n$.  
> **username_0**: @Anthony: Yes, sorry.  
> **username_2**: @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.  
> **username_0**: @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.  
> **username_2**: 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))$.  
> **username_0**: @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.  
> **username_3**: 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](http://en.wikipedia.org/wiki/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!).  
> **username_3**: 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)  
> **username_3**: (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](http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/bitonic/bitonicen.htm) (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)  
> **username_3**: (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.  
> **username_4**: 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.  
> **username_0**: @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.  
> **username_0**: @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.  
> **username_4**: How do you reduce your system to a markov chain, considering that at each step the swap gate operates between different lines?  
> **username_4**: 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.  
> **username_4**: Therefore, if the circuit generates an uniformly random permutation, the DTMC reaches a uniform stationary distribution in exactly L steps.  
> **username_0**: @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.  
> **username_4**: Yes. I thought that time-homogeneous chains may be possibly more simple to work with.  
> **username_3**: @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.  
> **username_5**: @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.  
> **username_6**: 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$  
> **username_3**: @Peter: (1) I am skeptical about the “reused for symmetry” reasoning.  See a construction in my comments on [Yuval’s answer](http://cstheory.stackexchange.com/questions/5321/what-is-the-most-efficient-way-to-generate-a-random-permutation-from-probabilisti/5364#5364), 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).  
> **username_6**: @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.  
> **username_6**: 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$.  
> **username_3**: @Peter: I know that that is not the answer to the question, but it might be worth posting it as an answer.  
> **username_1**: 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.  

---

## 11 answers

### Answer by username_2 on 2011-03-08. Score: 17

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)$.

> **Comments:**
> **username_7**: 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.  

---

### Answer by username_3 on 2011-03-10. Score: 16

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](http://en.wikipedia.org/wiki/Sorting_network). 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](https://cstheory.stackexchange.com/questions/5321/what-is-the-most-efficient-way-to-generate-a-random-permutation-from-probabilisti/5360#5360) 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.

> **Comments:**
> **username_7**: @Ito the answer I deleted is actually the first half of pairwise sorting network (see Wikipedia), adding second half should do the job, although, it is slightly less efficient than expected optimum.  
> **username_3**: @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 :) ).  
> **username_7**: @Ito I will miss the details again. Take any sorting network e.g. odd-even merge sorting network, or pairwise sorting network. Gates there are operating independently. Run all permutations through the network, assign the probabilities of the swap to the gate, according to swapping fraction. Theses networks has O(n log^2 n) gates. In my opinion you have the key ingredients for the solution, and if I did not mix things up you deserve bounty.  
> **username_3**: @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.  
> **username_5**: @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.  
> **username_7**: To rephrase sorting networks seem to equalize marginal distributions of elements across position, not the joint one, which is required for the problem at hand. Anthony solution seem avoid this by dropping elements from the network. So if one can reduce each step in Anthony algorithm to log n gates that solves the problem.  
> **username_6**: @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.  
> **username_7**: Fast sorting networks I tried does not produce all permutations, sorting networks repeated twice produce all permutations, but it is not clear that this way is possible to obtain uniform distribution of permutations (my experiments did not).  
> **username_3**: @mkatkov: “Fast sorting networks I tried does not produce all permutations”: That cannot happen.  Every sorting network (with the comparators replaced by probabilistic swap gates with probability strictly between 0 and 1) produces all the n! permutations with nonzero probability (although the distribution may not be uniform).  I recommend you to double-check that you used a correct sorting network.  
> **username_7**: @Ito It is not necessary. For sorting network all permutations converge to ordered state. Symmetric networks like bubble-sort are guaranteed to produce all permutations. So, I suggest to compute switching probabilities in sorting network, assign to the gates, and reverse the stream to produce random permutations.  
> **username_3**: @mkatkov: “For sorting network all permutations converge to ordered state.”  That implies that all permutations arise with nonzero probability if we decide the orders randomly, as I stated.  
> **username_7**: @Ito I was wrong. Sorting networks produce non-equal probabilities at least due to different number of computational path. To correct that one can compute n^2 matrix of paths between input k and output m. For fast sorting networks the depth is $log^2 n$, and therefore there are no more than $log^4 n$ distinct length pairs. Swapping adjacent lines with proba = inv odds to equalize the relative weights one can equalize all computational paths, that will require additional depth of $log^4 n$. I cannot figure out why if all paths are equal permutations will have different probabilities.  
> **username_6**: @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.  

---

### Answer by username_6 on 2011-03-13. Score: 15

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.

> **Comments:**
> **username_9**: My case enumeration failed to produce any shorter example.  
> **username_9**: ... even after the correction.  
> **username_0**: Excellent, that's a very nice observation.  
> **username_5**: These are definitely checkable... am I right in thinking that the $n=5$ case is already out of reach, though, for explicit checking?  
> **username_6**: @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.  
> **username_7**: 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.  
> **username_6**: @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.  
> **username_7**: @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.  
> **username_7**: 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  
> **username_7**: 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.  
> **username_5**: 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.  

---

### Answer by username_8 on 2011-03-11. Score: 14

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.

> **Comments:**
> **username_0**: Thanks, that is certainly useful to know. I am still interested to know about the gate number for generating the exact distribution, however.  

---

### Answer by username_9 on 2011-03-08. Score: 12

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.

> **Comments:**
> **username_0**: 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)$.  
> **username_3**: 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](http://en.wikipedia.org/wiki/Legendre_polynomials) P_n.  (more)  
> **username_3**: (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.  
> **username_6**: @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.  

---

### Answer by username_10 on 2011-03-09. Score: 8

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.

> **Comments:**
> **username_5**: And presumably two nearly random permutations can be composed to produce a permutation that is even more nearly random.  
> **username_5**: ... 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.  

---

### Answer by username_5 on 2011-03-09. Score: 7

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)$.


---

### Answer by username_3 on 2011-03-10. Score: 5

This is really a comment but too long to post as a comment. I suspect that the [representation theory of the symmetric group](http://en.wikipedia.org/wiki/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 S*n*, the group of permutations on *n* elements. A permutation *g*∈S*n* can be thought of as the event that *i*th output is *g*(*i*)th input for all *i*∈{1,…,*n*}. Now represent a probability distribution *p* as a formal sum ∑*g*∈S*n**p*(*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*∈S*n* is the identity element and *τ**ij*∈S*n* 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 *C*1 and *C*2 are represented as formal sums *a*1=∑*g*∈S*n**p*1(*g*)*g* and *a*2=∑*g*∈S*n**p*2(*g*)*g*, respectively, then the behavior of the circuit *C*1 followed by *C*2 is represented as ∑*g*1,*g*2∈S*n**p*1(*g*1)*p*2(*g*2)*g*1*g*2 = *a*1*a*2.

Therefore, a desired circuit with *m* probabilistic swaps exactly corresponds to a way of writing the sum (1/*n*!)∑*g*∈S*n**g* 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*∈S*n**f*(*g*)*g*, where *f* is a function from S*n* to ℂ, equipped with naturally defined addition and multiplication, form the ring called [group algebra](http://en.wikipedia.org/wiki/Group_ring) ℂ[S*n*]. 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.

> **Comments:**
> **username_6**: Surely using $\mathbb{R}$ rather than $\mathbb{C}$ would sufficient? ;)  
> **username_3**: @Peter: You are right.  I wrote ℂ just because it seems that ℂ is more common than ℝ in representation theory (judging from the very little I know).  
> **username_9**: 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)  
> **username_9**: 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)  
> **username_9**: 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.  
> **username_3**: @Yuval: Thank you for the detailed comments.  I agree that it reduces to proving some lower bound on the ranks of the matrices (1−p)I+pA_{ij}.  I lack the knowledge and the experience in representation theory necessary to actually try this approach or even to judge whether it is plausible to hope that this approach produces anything nontrivial.  
> **username_6**: @Yuval, surely each such $(1-p)I+pA_{ij}$ is an order-$n$ identity matrix apart from a minor $[[1-p,p][p,1-p]]$? That has determinant $1-2p$, so is singular iff $p = 1/2$. We require the chain of matrices to send $I$ to a flat $B_{ij}=1/n$ so the chain must be singular, but (superficially, at least) all that gets us is that at least one swap probability is $1/2$.  
> **username_6**: Correction: we get a bit more. The chain maps a matrix of rank $n$ to one of rank $1$ via multiplications by matrices of rank $n$ or $n-1$ (when $p=1/2$). Therefore by Sylvester’s rank inequality there must be at least $n-1$ swaps with $p=1/2$.  
> **username_3**: @Peter: No, I think that you are considering the representation of S_n by n×n permutation matrices, but that is merely one of the many representations of S_n.  (Actually I had been confused by the same thing first.)  In addition, I think that Yuval is talking about irreducible representations.  The representation by n×n permutation matrices is not irreducible for n≥2.  
> **username_6**: And it occurs to me that Anthony Leverrier's solution achieves that lower bound of $n-1$ swaps with $p=1/2$.  
> **username_6**: @Tsuyoshi, ok, but I *think* my analysis is still correct.  
> **username_3**: @Peter: Except for the claim “all that gets us is that at least one swap probability is 1/2” (even with the correction to n−1 gates).  
> **username_6**: @Tsuyoshi, the parenthetical "superficially, at least" was there for a reason ;)  
> **username_3**: @Peter: (1) Fair enough.  (2) An equivalent way of stating your finding is that if each of the n output gates of a circuit has the uniform marginal distribution (which is a weaker assumption than the permutation being uniform), then the circuit necessarily contains at least n−1 probability-1/2 swap gates.  Instead of using the terminology of representation theory, we can state its proof in terms of Markov chain; we can consider a circuit as a linear transformation which maps a probability distribution over n wires to another, (more)  
> **username_3**: (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.  
> **username_6**: It is indeed trivial as a lower bound on the total number of gates, but it might be possible to combine it with the information-theoretic approach to get useful information about what the other probabilities can be. I'm tempted to investigate what we can get by requiring the first n/2 gates to be $2i\leftrightarrow 2i+1$ with $p=1/2$ and the last n/2-1 to be $2i-1\leftrightarrow 2i$.  
> **username_3**: @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.  

---

### Answer by username_11 on 2011-03-08. Score: 1

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.

> **Comments:**
> **username_2**: I think the relevant complexity measure for this question is the number of gates and not the runtime.  
> **username_0**: @Anthony is correct that what I am interested in is simply the minimum number of gates necessary.  

---

### Answer by username_12 on 2011-03-08. Score: 0

**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**

> **Comments:**
> **username_0**: 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$.  
> **username_12**: Indeed. I forgot too check the uniformity for $n=4$...  

---

### Answer by username_4 on 2011-03-07. Score: 0

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.

> **Comments:**
> **username_0**: 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.  
> **username_0**: And yes, $\lceil \log_2(n!) \rceil$ is the minimum, but this is only $O(n\log(n))$.  
> **username_13**: 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.  
> **username_4**: 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.  
> **username_0**: @Andrew: I don't see how to "merge these randomly" using the gates outlined in the question.  
> **username_13**: 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.  

---

