Generating bitstring combinations using a butterfly network I'm using a butterfly network to generate a random combination of a bitstring of length $n$ and weight $w$. Let me clarify it with an example. Suppose I want a random bitstring of length 8 and Hamming weight 2. The idea is:


*

*set the first 2 bits to 1, leaving all others to 0

*apply the butterfly network; each bit-swap has a 50/50 chance of being enabled


Basically for each swap we toss a fair coin to enable/disable the swap: if it is enabled, the involved bits are swapped, otherwise the bits are passed through. You can see that we have $x = \frac{n}{2}\log{n}$ distinct swaps (leaving away all the possible optimizations), corresponding to just as many coin tosses. 

We can rephrase the previous problem saying that each swap is controlled by a control bit: if it is 1, the corresponding swap is enabled; otherwise, it is disabled. We have therefore $2^x$ distinct configurations of control bits.
Now my question is: how many times the same bitstring is generated in output? There are two main factors to be considered:


*

*The network is able to generate all the $\binom{n}{w}$ bitstring of length $n$ and weight $w$

*To accomplish the goal we use $2^x$ distinct configurations of swaps.


To rephrase the previous problems, we have $2^x$ possible configurations, but just $\binom{n}{w}$ distinct output: there must be some collision, i.e. two or more distinct swaps configurations (or equivalently control bits configurations) mapping to the same output bitstring. In the image below, for example, we can see that we are trying to generate all the words of length 4 and Hamming weight 2. We can also notice that there are two different ways to generate the string 1010: if only flip 0 and 2 produces 1 OR if only flip 1 and flip 3 produces 1.

But in general, how many configurations maps to the same bitstring? Worst case? Best case?
 A: Due to the topology of the butterfly network, your question is equivalent to the following.

Label $w$ vertices of the $n$-dimensional hypercube 1, the rest with 0. For each $n$ directions, for each edge of that direction, swap the labels of their endvertices with probability $1/2$ (independently for each edge). What is the distribution of the labels at the end?

For $w=1$, we get all $2^n$ possibilities uniformly.
For $w=2$, suppose that we start from the position you've described, i.e., two endvertices of an edge of direction $n$ are labeled with 1. The first $n-1$ steps reduce to the $w=1$ case, so we'll have two vertices labeled 1 distributed uniformly on two facets that are perpendicular to direction $n$. Executing the final step gives the following probabilities for two vertices, $(u_1,\ldots, u_n)$ and $(v_1,\ldots, v_n)$, to be labeled 1:


*

*$1/2^{2n-2}$ if $u_i=v_i$ for all $i<n$.

*$1/2^{2n-1}$ if $u_i\ne v_i$ for some $i<n$.


So in case of your example $n=2$, this gives $1/4$ for $1100$ and $0011$, and $1/8$ for the remaining $4$ strings of weight $2$. You can compute the probabilities for other small cases similarly.
In the general case, a lot depends on how the $w$ vertices labeled 1 are positioned in the beginning. An easy generalization of the above is if $w=2^d$ and they form a subhypercube of the last $d$ directions. Then the "best" case is that they remain the same, with probability $(1/2^{n-d})^w$, while the "worst" case is if they are each mapped to different first $n-d$ coordinate places, with probability $w!(1/2^{n-d})^w$. I would assume that it's not hard to show that these are the extremal values also in general (where $d$ is replaced with $\log w$).
