N random choices according to probability

Question

This code is used to get random numbers with a certain probability: 8 is returned if r is between 0 and 0.8; 2 is returned if r is between 0.8 and 1.

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

int main()
{
    srand(time(NULL));
    double r = rand() / (double)RAND_MAX;
    double sum = 8 + 2;
    if (r < 8 / sum) {
        printf("80% \n");
    } else {
        printf("20% \n");
    }  
}

but if I have more than two numbers, say n, how can I handle it? Can I handle it with multiple if-else statements? Or what else?

Answer 1

Simple

1. Create an array of probabilities (sum to 1.0), in O(n) time
2. Generate a random number between 0.0 and 1.0
3. Iterate through the array, in O(n) time:
   • if the random number < the probability of the element, stop
   • otherwise decrement the random number by the probability and move to next element
4. The answer is the number corresponding to the element you stopped at

Complex

1. Create an array of cumulative probabilities and store them in an array, in O(n) time (this array should have increasing values)
2. Generate a random number between 0.0 and 1.0
3. Do a binary search to find the smallest element that is >= the random number, in O(log(n)) time.
4. The answer is the number corresponding to the element you stopped at

I have not included the necessary corner cases to address. I am sure you can do it yourself.

Answer 2

In addition to randomstring's proposals, you could consider building an Alias Table -- O(n log n) to construct the table, O(1) per value to generate.