Using random number generator to generate a number

问题:

I came across the following question:

Using rand() function, generate a number with expected value k. Options are:

1)

   int GetRandom(int k)
   {
       v=0;
       while(rand()<1.0f/(float)k)
           v++; 
       return v;
    }

2)

   int GetRandom(int k)
   {
       v=0;
       while(rand()<(1-1.0f/(float)k))
           v++; 
       return v;
    }

3)

   int GetRandom(int k)
   {
       v=0;
       while(rand() > (1-1.0f/(float)(k+1)))
           v++; 
       return v;
    }

1) seemed like the correct answer. Examining the outcome for specific values of k seems to indicate this is the not the case. (I set k=3. The frequency distribution of values for 100000 trials can be seen in the image below )

How would one do this ?

The question is somewhat similar to this one.

回答1:

You want (2). This samples a Geometric Distribution (link) with mean k.

A geometric distribution represents an experiment of this kind:

• A certain event happens repeatedly, with an outcome that is either 0 or 1
• The outcome of an event is 1 with probability p and 0 with probability 1-p
• What is the index of the first event with an outcome of 1?

So if X ~ G(p), where X is a random variable and p is the probability above, then X represents "What is the index of the first event with an outcome of 1?" The expectation is E[X] = 1/p.

Given this information it should now be clear that the following represents a sampling of the random variable X with p = 1/k (and is equivalent to (2)).

int Sample(int k)
{
    int v = 1;
    while (true)
    {
        //outcome is true with probability p = 1/k
        bool outcome = rand() < 1 / (double)k;
        if (outcome)
            return v;
        else
            v++;
    }
}

Be aware that looking at the peak (mode) and expectation of the distribution are not the same thing. The peak of the geometric distribution is always going to be at 1!