I have a set of 455 items from which I select at most 160 items randomly, with replacement. First I seed with srand() and then use rand() to select each number. I observe that in my selections of up to 160 items, I tend to see at least 10 items selected more than once. This seems to indicate that the random numbers are not evenly distributed.
Is there a way to have more evenly distributed random numbers?
Your intuition about the results is wrong. If the numbers are truly random and distributed evenly between 0 and 455, then the probability of there being at least 10 duplicates in the set of 160 numbers is actually quite high (in fact it is a virtual certainty). Informally this is called the "Birthday Paradox", although it is not actually a paradox.
This chart shows the probability of different numbers of duplicates appearing when you select 160 indepedent identically distributed values with replacement from a set of 455. As you can see it is actually most likely that you get 22 duplicated values, with there being almost no chance that you get less than 10 or more than 35.
It sounds like your underlying implementation of generating random numbers is working perfectly fine. What seems to be the problem is the way you are selecting items from among the total population. This wikipedia article on simple random samples describes the difference between choosing a subset with replacement vs. one without replacement. You want the latter.
Imagine you have a box with many uniquely numbered balls in it. What you are doing is choosing a ball at random, but after writing down what you have chosen, putting the ball back into the box before choosing again. This allows for the possibility of making a repeated choice. However, what you want is to eliminate that possibility once that ball has been chosen. In order to do that you will have to change the mechanism you have used for making the random choice based on your randomly generated number. A good example can be found here.
Try using arc4random() from stdlib.h. It has a better pseudo-random number generation algorithm than rand(), and it doesn't require you to set an initial seed.
A proper set of random number generators is implemented in the gnu gsl library. You can pick from a quite variety of well tested random number generators. For serious computations, do not use rand(). In your case I would use a gsl_ran_sample from the given input set. This would look like this:
#include <stdlib.h>
#include <gsl/gsl_rng.h>
#include <gsl/gsl_randist.h>
#define N 455
#define K 160
int main(int argc, char **argv)
{
double arr[N];
double randarr[K];
gsl_rng *r = NULL;
const gsl_rng_type *T;
int seed = 31456; // intial seed of the random number generator
int i;
// gsl_rng_env_setup(); // if you want to set different random number generators etc.. or set external seeds
T = gsl_rng_ranlxs2;
r = gsl_rng_alloc(T);
gsl_rng_set(r, seed);
for (i = 0; i < N; i++) {
arr[i] = i;
}
// gsl_ran_choose(r, randarr, K, arr, N, sizeof(double)); // without replacement
// in case of choose: you will need to call gsl_ran_shuffle(r, randarr, K, sizeof(double)) if you want to randomize the order.
gsl_ran_sample(r, randarr, K, arr, N, sizeof(double)); // with replacement
fprintf(stdout, "Picked array elements:\n");
for (i = 0; i < K; i++) {
fprintf(stdout, "%f\n", randarr[i]);
}
gsl_rng_free(r);
return 0;
}
if you have a properly installed gsl. compile with
gcc -Wall main.c `gsl-config --cflags --libs`
Create an array of 455 integers from 0 to 454, randomly shuffle it, then use its first 160 numbers as indices into the array of the original 455 items. That'll guarantee uniqueness of the selection.
I should add a little pic from Dilbert explaining probability in a funny way.
There's also a good article on statistical randomness on Wikipedia.
Well, without seeing your code its hard to tell what's wrong, but you can always use the /dev/random device to draw random numbers. Just open it as a file and read from it.
However, you still might get repetitions. Just filter them out.
While I'm sure there are other pseudo-random number generators you could use, its besides the point. Your expectations are unrealistic. Using a random number generator that I have reason to trust*, I find that you need to pick fewer than 100 items from a set of 455 in order to expect fewer than 10 items to be duplicates. If uniqueness is important, its fairly easy to implement; if randomness is important, then you're fine as is. I can just about guarantee that your random number distribution is just fine.
*I used various transformations on the raw random number to pick from a set. If there was a problem with the generator, the different transformations would have shown different biases. They did not, so I'm satisfied that the generator is close enough to random for the problem at hand.
