Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I have 3 IPs and every IP has a weight, I want to return the IP's according to its weights using the random function. For example if we have 3 IP's

  • X with weight 3
  • Y with weight 3
  • and Z with weight 3

I want to return X in 33.3% of cases and Y in 33.3% of cases and Z in 33.3% of cases, depending on random function in C.

I have tried this code :

double r = rand() / (double)RAND_MAX;
double denom = 3 + 3 + 3;
if (r < 3 / denom) {
// choose X
} else if (r < (3 + 3) / denom) {
// choose Y 
} else {
// choose Z
}

I repeat the function 1000 and I get: Choose x 495 times and Choose y 189 times and choose z 316 times. But what I want is to get X:333 y:333 Z:334 How can the weighted random be more accurate?

share|improve this question
3  
random will always be random..., unless you go with a true round robin –  ratchet freak Sep 1 '13 at 15:23
4  
Do you understand about variance in random distributions? What you've described is an example of a multinomial distribution, so the variance in each of your variables will be n * (0.33) * (0.66), where n is the number of trials. Your results will always jitter around the mean values of 0.33. –  Charles E. Grant Sep 1 '13 at 16:18
    
For what it's worth, I just ran a variant of that algorithm using FreeBSD's rand() routine, and while it didn't look particularly balanced by eye, it never approached the skew in the results that centosuser posted. –  Aidan Cully Sep 1 '13 at 17:25
1  
-1 for the contradictory title –  Dave Hillier Sep 1 '13 at 19:03
2  
Random means having a "lack of pattern or predictability in events". Your definition of random seems a little different. Given a trillion tries you'd expect a random distribution to be approximately 1/3 1/3 1/3, but only approximately. If with only 1000 tries you got 333, 333 and 334 I would strongly suspect that the random function was broken –  Richard Tingle Sep 2 '13 at 12:11
show 4 more comments

closed as off-topic by Kilian Foth, Michael Kohne, World Engineer Sep 4 '13 at 12:46

  • This question does not appear to be about software development within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

3 Answers

up vote 2 down vote accepted

(This part of the question was associated with revision 2 and is still quite applicable to that problem)

The standard approach to doing this is to populate an array with the appropriate weights:

[x, x, x, x, x, x, y, y, y, y, z, z]
 1  2  3  4  5  6  1  2  3  4  1  2

and then pick one at random.

Please note that random is random. It is very unlikely that you will ever a perfect distribution.

If you want to guarantee the distribution, you need to do (mostly) away with the random.

Instead, shuffle the above array. For example, one shuffling would give you:

[x, y, z, y, x, x, y, x, z, y, x, x]

And then loop over the array again and again returning the current index. It isn't random anymore, but it will guarantee the distribution remains what you are looking for always. This is just a slightly more 'random' version of a round robin distribution.

If this is attempting to load balance something, the round robin is a better approach and you might want to consider a evenly distributed round robin:

[x, y, x, y, x, z]

This has the same distribution as above and tries to keep everything at an even distance so not as to saturate any one resource.


As an aside, to the question of rand being poor, you may be dealing with an older standard library. From rand3 man page

   The versions of rand() and srand() in the Linux C Library use the
   same random number generator as random(3) and srandom(3), so the
   lower-order bits should be as random as the higher-order bits.
   However, on older rand() implementations, and on current
   implementations on different systems, the lower-order bits are much
   less random than the higher-order bits.  Do not use this function in
   applications intended to be portable when good randomness is needed.
   (Use random(3) instead.)

This can be demonstrated using the following C program that spits out the consecutive low byte and low nybbles from rand(). I happen to have a more modern system and don't have access to anything that might demonstrate this low order less randomness.

You can test it on your system with the following code which looks at the low byte, low 4 bits, and low 2 bits.

#include <stdlib.h>
#include <stdio.h>

int main (int argc, char** argv) {
    int i, r;
    int a8, a4, a2;

    srand(0);
    FILE *fp0xff = fopen("low8.out", "w");
    FILE *fp0x0f = fopen("low4.out", "w");
    FILE *fp0x03 = fopen("low2.out", "w");
    for(i = 0; i < 10000; i++) {
        /* 1 of 4 */
        r = rand();
        a8 = r & 0xff;
        a4 = r & 0x0f;
        a2 = r & 0x03;

        fprintf(fp0xff, "%c",a8);

        /* 2 of 4 */
        r = rand();
        a8 = r & 0xff;
        a4 = (a4 << 4) | (r & 0x0f);
        a2 = (a2 << 2) | (r & 0x03);

        fprintf(fp0xff, "%c",a8);
        fprintf(fp0x0f, "%c",a4);

        /* 3 of 4 */
        r = rand();
        a8 = r & 0xff;
        a4 = r & 0x0f;
        a2 = (a2 << 2) | (r & 0x03);

        fprintf(fp0xff, "%c",a8);

        /* 4 of 4 */
        r = rand();
        a8 = r & 0xff;
        a4 = (a4 << 4) | (r & 0x0f);
        a2 = (a2 << 2) | (r & 0x03);

        fprintf(fp0xff, "%c",a8);
        fprintf(fp0x0f, "%c",a4);
        fprintf(fp0x03, "%c",a2);
    }
    fclose(fp0xff);
    fclose(fp0x0f);
    return 0;
}

The output of this program can then be examined using ent which runs a number of tests of randomness against a stream of bytes.

Running this against the low2.out on my system produces:

Entropy = 7.982762 bits per byte.

Optimum compression would reduce the size
of this 10000 byte file by 0 percent.

Chi square distribution for 10000 samples is 240.46, and randomly
would exceed this value 73.46 percent of the times.

Arithmetic mean value of data bytes is 127.6318 (127.5 = random).
Monte Carlo value for Pi is 3.150060024 (error 0.27 percent).
Serial correlation coefficient is -0.002842 (totally uncorrelated = 0.0).

Which is frankly, a reasonably good random stream.

The reason I am testing the low two bytes is that you are doing things with % 9 which works only with these low bits. You may find that your random number generator is old and might need to implement your own (if that degree of randomness is something that you need to work with).

One approach would be, well, to implement your own. The Mersenne twister is quite well regarded and you can find implementations for a wide range of languages quite easily.

The other thing to do would be to shift the random number you get down 8 bits to get rid of any low order less randomness and use those bits.

You can get an idea of the poor quality of rand in some generators from Random.org.

For, example, rand() called by php on Windows produces the following:

enter image description here

(from Random.org)

Which is quite certainly, not a good random.

share|improve this answer
    
round robin is good when the weights is equals ,,, but when the weights are different ,,there isn't any better solution than using the random ,,but the problem that it is not accurate –  centosuser Sep 1 '13 at 15:57
2  
@centosuser, you haven't really understood MichaelT's solution. The example he gives doesn't have equal weights. He's using the weights listed in your original post before your edit. –  Charles E. Grant Sep 1 '13 at 16:26
1  
@centosuser using any weights, you can shuffle the weighted array and loop over that. It doesn't matter what the weights are. It is also possible, that you've got a poor random number generator, and I went into that area with this latest edit. –  MichaelT Sep 1 '13 at 16:42
    
@CharlesE.Grant Its also possible, that he's dealing with a poor random number generator. There are still quite a few of them out there. Combined with looking effectively at %9 he's often looking at the low bits which are often less than ideal. There are some approaches to addressing this (like shifting the low bits off or using a different random function). –  MichaelT Sep 1 '13 at 16:44
add comment

I would usually do something like this:

int r = rand();
if (r % 3 == 0) {
// choose X
} else if (r % 3 == 1) {
// choose Y 
} else {
// choose Z
}

It's probably not perfect (I think RAND_MAX might give a Y instead of Z or something like that), but if the random number generator works properly, you'd expect to see a good distribution of X, Y and Z. The expected deviance from a uniform distribution would be less than the sample size you're using now.

share|improve this answer
add comment

If you want to truly guarantee that you'll get exactly the distribution you want, you can create a pool of values that you pull from:

int xpool = 333;
int ypool = 333;
int zpool = 334;

int x = 0;
int y = 0;
int z = 0;

for(unsigned int trial=0;trial<1000;trial++) {

    unsigned int r = rand() % (xpool + ypool + zpool);

    if(r < xpool) {
        x++;
        xpool--;
    } 
    else if(r < xpool + ypool ) {
        y++;
        ypool--;
    }
    else {
        z++;
        zpool--;
    }
}
cout << "x: " << x << " y:" << y << " z:" << z << endl;

This will guarantee that you always have an exact distribution, but the order will be as random as rand() can make it. This works well if the number of choices is low, and you know how many trials you will have ahead of time.

It depends on what you want. If you want something to give a good weighted distribution with infinite trials, use @MichaelT's answer. If you want to guarantee an exact distribution and know the number of trials, the do something like this.

share|improve this answer
add comment

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