Randomly sample an array with a fixed number of zeros

Question

I have optimized code to randomly sample an array containing -1s, 0s and 1s with probabilities 1/4,1/2,1/4. It looks like

#define n (12)
unsigned int x,y=34353,z=57768,w=1564; //PRNG seeds
/* xorshift PRNG
 * Taken from https://en.wikipedia.org/wiki/Xorshift#Example_implementation
 * Used under CC-By-SA */
u_int32_myRand() {
    unsigned int t;
    t = x ^ (x << 11);
    x = y; y = z; z = w;
    return w = w ^ (w >> 19) ^ t ^ (t >> 8);
}

x=(int)time(NULL); //seed PRNG
unsigned int k
int F[n];
for(k=0; k<n; k++) {
      F[k]=(1-(myRand()&3))%2;  
    }

How can I modify this so that it only returns arrays that have exactly n/3 zeros in them and still have it fast?

Answer 1

The easiest way to do this would be to fill the first part of the array with n/3 zeros. Then add as many 1's and -1's as you want. Then, do a Fisher-Yates shuffle to randomize the array.

The problem with trying to "randomly distribute n/3 zeros" is that you have difficulty preventing overlap. That is, if you want to put 33 zeros in an array of 99, you can't just pick 33 random indexes because you're likely to get duplicates. So you'll end up with fewer than 33 zeros in the array.

As for performance, this will be nearly as fast as your current example. It just requires an extra pass over the array. The number of random numbers generated is the same.

Answer 2

Proceed in two steps:

1. Distribute exactly n/3 zeros randomly over your array and set the rest to 1.
2. Assign a random sign to the remaining ones to get the desired -1/+1.

Example code:

int F[n];
// fill with 1
for(k=0; k<n; k++) {
    F[k] = 1;
}
// distribute n/3 zeros
for(k=0; k<n/3; k++) {
    // find a location which does not have a 0 yet
    int i;
    do {
        i = myRand() % n;
    } while(F[i] == 0);
    F[i] = 0;
}
// change remaining (non zero) to -1 with 50% probability
for(k=0; k<n; k++) {
    if(F[k] && myRand()%2) F[k] = -1;
}

This has a runtime of around 2.4 n, but I do not think you can get much faster than that.

The while loop in the second for loop is in average executed around 1.2 times for the case of n/3 zeros.

---

Remark:

Trial and error used in the second for loop works quite well if the success probability is high enough. The number of trials you need in average for a probability of p is 1/p.

In our case (n/3 zeroes) the worst probability to find a good location (i.e. for the last zero) is 2/3, thus in average 1.5 iterations. To find places for all n/3 zeros you need in average around 0.2*n iterations.

The average runtime can be computed as -log(1-a), where a is the percentage of zeroes you want to distribute (in your case a = 1/3).

Some more examples: If you would want to distribute 2/3*n zeros, it would take 1.1*n iterations. For 0.99*n zeroes it is already 4.6*n iterations.

All in average. In the worst case it takes forever.

---

If you need a runtime guarantee you are perhaps better off by implementing real sampling without reselection, i.e. filling a container with all possible indices, sampling a random element as index and removing it from the container. But this probably has a runtime of around O(n*log(n)). Thus it works good for small n or a large percentage of zeroes.

Answer 3

Here is a simple algorithm that will do:

1. Put the required number of zeros (n/3) into your output array
2. For the remaining places, put 1 or -1 with probability 1/2
3. Shuffle the array

However:

... array containing -1s, 0s and 1s with probabilities 1/4,1/2,1/4

Does it mean that there are exactly n/4 1's in the array? Let's assume it doesn't. Then:

• Count the number of 1's (a) and -1's (b) in your array
• Probability for 1 is a/(a+b); use it in the above algorithm instead of 1/2

Note: if there are only zeros, or no zeros at all, in your input array - sampling with exactly n/3 zeros is impossible!