4

I'm trying to generate a discrete uniform distribution in C between 0 and 1.

Normally you'd expect: t = rand()%2 , but it seems there is a problem with this approach (it seems to be related to lower bits having more probabilities, although I don't really understand much about that).

I tried a trick that I found somewhere on the Internet:

Let t1,t2 be 2 not so uniform distributions between 0 and 1 with probability p for 1, (1-p) for p. Then we take 2 random numbers:

t1 : p for 1, (1-p) for 0

t2 : p for 1, (1-p) for 0

If t1!=t2 we have the probability for (t1,t2)=(1,0) and (t1,t2) = (0,1) to be the same: p(1-p). So we just the repeat the sampling until we get t1!=t2 and we choose the random number t = t1 (it really doesn't matter). Here is my code: 

#include <time.h>
#include <stdlib.h>


int main()
{
/*
Declare variable to hold seconds on clock.
*/
int i,t1,t2,t;
time_t seconds;
seconds = time(NULL);

/*
Get value from system clock and
place in seconds variable.
*/
time(&seconds);
/*
Convert seconds to a unsigned
integer.
*/
srand((unsigned int) seconds);
/*
Output random values.
*/
    for (i =0; i < 10; ++i)
    {
        do
        {
            t1 = rand()%2;
            t2 = rand()%2;
        }
        while (t1==t2);
        t = t1;

        printf("%d\n",t);
    }
            /*printf("%d",rand()%2);
    printf("%d",rand()%2);*/

return 0;
}

Am I right or wrong? Thank you very much!

Dang Manh Truong
  • 795
  • 2
  • 10
  • 35
  • You're going to need to understand what's actually wrong with `rand` to understand why this can't possibly work (it's nothing to do with the distribution), but basically: don't use `rand`. – user2357112 Nov 02 '15 at 03:54
  • 5
    A simple alternative to `rand()%2` that doesn't suffer from bias due to low-entropy in the lowest bit is `rand() > RAND_MAX / 2`. – Cornstalks Nov 02 '15 at 03:54
  • So by "discrete uniform distribution between 0 and 1", you mean simply 0 with probability 1/2 and 1 with probability 1/2? – Mark Adler Nov 02 '15 at 04:23

2 Answers2

2

Never use rand(). Use random() or even better, a generator from the PCG family.

For either one, all of the provided bits are good individually. random() provides 31 random bits. Use all of them instead of just one. There's no point in throwing away the other 30. E.g.

static inline int random_bit(void)
{
    static long val;
    static int bits = 0;
    int bit;

    if (bits == 0) {
        val = random();
        bits = 31;
    }
    bit = val & 1;
    val >>= 1;
    bits--;
    return bit;
}
Mark Adler
  • 101,978
  • 13
  • 118
  • 158
0

The built-in random number generator rand() isn't guaranteed to have a particular distribution as you assumed (probability of 'p' and '1-p'). Although rand() > RAND_MAX / 2 is better, it still may not be having a particular distribution. It is better to use any other method as described here.

Having said that, if you assumed that the probability of 1 and 0 are 'p' and '1-p' for your random number generator, then what you have done to generate uniform distribution looks mathematically correct with probability of 2*p*(1-p) for each of 1 and 0, although you wouldn't be willing to use this as you indicated in comments.

Community
  • 1
  • 1
user1969104
  • 2,340
  • 14
  • 15
  • OK, I will find another function for this. But if p is large (about 0.9) wouldn't the while loop be less likely to break (because the probability of t1 =t2=1 would be 0.9*09 much larger than when they are different ) I'm just guessing :P – Dang Manh Truong Nov 02 '15 at 04:32
  • @TruongTroll, you are right. If you assume that p is 1, then p(1-p) is 0, and the loop never breaks. But still mathematically, your solution is a uniform random generator with each outcome having a probability of 0 :-). – user1969104 Nov 02 '15 at 04:36