Equally distributed probability in C [duplicate]

Question

This question already has answers here:

Generating a uniform distribution of INTEGERS in C (4 answers)

Closed 7 years ago.

I have a program that runs over 1000000 iterations to simulate server load. Arrival rate of requests is a variable. For example if arrival rate is 2: This means at every 2 iterations, there should be 1 request incoming which would generate "around" 500,000 requests at the end of simulation and so on. I can not do this just by introducing a new request at each nth interval depending on the arrival rate. There must be a factor of luck involved.

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

//random number generator method
int random_number(int min_num, int max_num){
  int result=0,low_num=0,hi_num=0;

  if(min_num<max_num){
    low_num=min_num;
    hi_num=max_num+1; // this is done to include max_num in output.
  }else{
    low_num=max_num+1;// this is done to include max_num in output.
    hi_num=min_num;
  }
  result = (rand()%(hi_num-low_num))+low_num;
  return result;
}

int main(){
  srand(time(NULL));
  unsigned int arrivalRate = 2;
  unsigned int noOfRequests = 0;
  unsigned int timer;
  for(timer = 0; timer < 1000000; timer++){
    //gives a random number between 0 and arrival rate
    int x = random_number(0, arrivalRate);
    //there is a new request
    if(x <= 1){
      noOfRequests++;
    }    
  }
  printf("No of requests: %d", noOfRequests);
}

So, if I run this code with arrivalRate 2, it generates around 600,000 requests which should be only around 500,000 (+-1000 is tolerable) requests. How can I improve my code to generate more reasonable results, it is producing way too much than expected.

Answer 1

The result of the random function is uniformly distributed between 0 and 2. Which means the output is either 0, 1, or 2 with 33% probability each. You are testing for <= 1, which means you have a 67% probability of accepting the request, which is around 666K per million.

To solve your problem, you need to exclude the lower bound from the interval, change the computation of result to:

result = (rand()%(hi_num-low_num+1))+low_num;

Or you might want to exclude the upper bound instead, depending on what you need. Your statement "This means at every 2 iterations, there should be 1 request incoming" is not consistent with randomly picking 2 numbers out of a set of 3.

Answer 2

I guess the problem lies in a bias in the values returned by your random number function.

rand() returns a floating point number, but result is being truncated to an integer, which will bias it towards smaller numbers. Since noOfRequests increments when result is <=1, this may be why noOfRequests ends up so much larger than 500,000.

Answer 3

For example if arrival rate is 2: This means at every 2 iterations, there should be 1 request incoming...

No, it means that on average there should be 1 incoming for every 2 iterations. There's a big difference. That means the average number of requests generated per iteration is 1/2, not 2.

In reality you probably want to use a different distribution than Uniform. If you're generating counts at each time step, sometimes you'll have a count of 0, and occasionally it could be much more. The way you've written your program so far you want a discrete (counting) distribution which never goes negative and has a mean of 1/2. Do not use something like the normal (aka Gaussian) distribution - it will both give fractional values and go negative on you.

In the long run, you may want to convert over to a discrete event simulation model. No need to look at every time tick if nothing's happening, and viewing time as continuous rather than ticked is often more realistic. Check out this Winter Simulation Conference tutorial paper for a ten page intro on how to do this. The code there is Java, but the concepts can and have been implemented in any number of languages. Basically you need a priority queue to track what happens in what order, and a small event loop as described in the paper to control things.