What is the most efficient way to generate a random permutation from probabilistic pairwise swaps?

Question

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.

Answer 1

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

Answer 2

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

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

• The solution by Anthony Leverrier with n(n−1)/2 probabilistic swap gates can be understood as the sorting network for the bubble sort with the comparators replaced by probabilistic swap gates with suitable probabilities. See mkatkov’s comment at March 10 4:53 on that answer for details. The sorting network for the selection sort can also be used in the same way. (In the comment at March 7 23:04, I described Anthony’s circuit as the selection sort, but that was not correct.)
• If we just want every permutation with nonzero probability and do not care about the distribution being uniform, then every sorting network does the job when all the comparators are replaced with probability-1/2 swap gates. If we use a sorting network with O(n log n) comparators, the resulting circuit generates every permutation with probability at least 1/2^{O(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.

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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.

Answer 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 8

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

Note that the behavior of a circuit consisting of probabilistic swap gates can be fully specified as a probability distribution p over S_n, the group of permutations on n elements. A permutation g∈S_n can be thought of as the event that ith output is g(i)th input for all i∈{1,…,n}. Now represent a probability distribution p as a formal sum ∑_g∈Snp(g)g. For example, the probabilistic swap between wires i and j with probability p is represented as (1−p)e+pτ_ij, where e∈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₁ and C₂ are represented as formal sums a₁=∑_g∈Snp₁(g)g and a₂=∑_g∈Snp₂(g)g, respectively, then the behavior of the circuit C₁ followed by C₂ is represented as ∑_g1,g2∈Snp₁(g₁)p₂(g₂)g₁g₂ = a₁a₂.

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

The formal sums ∑_g∈Snf(g)g, where f is a function from S_n to ℂ, equipped with naturally defined addition and multiplication, form the ring called group algebra ℂ[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.

Answer 9

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.

Answer 10

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.

Answer 11

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