4
$\begingroup$

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:

  1. set the first 2 bits to 1, leaving all others to 0
  2. 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.

Butterfly network for n=8 and w=2

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:

  1. The network is able to generate all the $\binom{n}{w}$ bitstring of length $n$ and weight $w$
  2. 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. enter image description here But in general, how many configurations maps to the same bitstring? Worst case? Best case?

$\endgroup$
2
  • $\begingroup$ What do you mean "to generate previous output" in 2.? Are you actually going to do this sequentially, so generate the first weight w output, apply random bits and swap, generate next one from the first, etc. etc.? $\endgroup$
    – kodlu
    May 11, 2019 at 0:16
  • $\begingroup$ @kodlu for our objective, let's assume I try sequentially all the distinct $2^x$ flip bit configurations to produce all the distinct output bitstring of length $n$ and weight $w$. How many times should I expect to see a repetition of the same output bitstring in the best and worst case? $\endgroup$
    – tigerjack
    May 11, 2019 at 7:22

1 Answer 1

1
+100
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ Thanks for your great reply. I am a bit unsure on what your $n$ represents; is it the same of my $n$? When you say in my example $n=2$, do you refer to the number of stages of the butterfly network? $\endgroup$
    – tigerjack
    May 24, 2019 at 17:02
  • $\begingroup$ Also, if the $w$ vertices are labeled in a different way, what changes is which of the final configuration has the best or worst case, but the probabilities remain unaltered, am I right? Accordingly, it is not possible to obtain a uniform distribution for $w>1$. $\endgroup$
    – tigerjack
    May 24, 2019 at 17:05
  • 1
    $\begingroup$ @tigerjack89 Yes, our $n$'s are the same. If you change the labeling, then the probabilities also change. For $n=2$, if you start from 1010, then nothing can happen in the first stage, and you can obtain strings 1010, 1001, 0110, 0101 with probability $1/4$, while the remaining two strings cannot be obtained. But it can never become perfectly uniform over all strings, of course, unless $\binom nw$ is a power of 2. $\endgroup$
    – domotorp
    May 24, 2019 at 19:15
  • 1
    $\begingroup$ Thanks again, and yes, my experimental data confirm your statements. Coming back to $n$, in my example $n=4$, while in your answer you say $n=2$. This is why I think there is a difference between the two. $\endgroup$
    – tigerjack
    May 24, 2019 at 19:42
  • $\begingroup$ @tigerjack89 Yes, of course you're right, your $n=2^{\textrm{my } n}$. $\endgroup$
    – domotorp
    May 24, 2019 at 20:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.