Tag Archives: graphs

How much bias is introduced by the remainder technique?

Posted on by
28

(This is a follow-up article to my post on generating random data that conforms to a given distribution; you might want to read it first.)

Here’s an interesting question I was pondering last week. The .NET base class library has a method Random.Next(int) which gives you a pseudo-random integer greater than or equal to zero, and less than the argument. By contrast, the rand() method in the standard C library returns a random integer between 0 and RAND_MAX, which is usually 32768. A common technique for generating random numbers in a particular range is to use the remainder operator:

int value = rand() % range;

However, this almost always introduces some bias that causes the distribution to stop being uniform. Do you see why?
Continue reading →

Advertisements

Producing permutations, part two

Posted on by
10

Last time on FAIC I described a simple recursive algorithm for generating all permutations of the first n whole numbers: if you have all the permutations of the first n-1 whole numbers, you just insert the nth whole number at each of n positions in each permutation. So if we had all the permutations of {0, 1, 2} and we wanted all the permutations of {0, 1, 2, 3}, we just start listing permutations of {0, 1, 2} with the 3 stuck in each of 4 places:

  {3, 0, 1, 2},  
  {0, 3, 1, 2},
  {0, 1, 3, 2},
  {0, 1, 2, 3}, That does it for {0, 1, 2}...
  {3, 0, 2, 1}, 
  {0, 3, 2, 1},
  {0, 2, 3, 1}, 
  {0, 2, 1, 3}, That does it for {0, 2, 1}...

and continue to get the 24 permutations.

Continue reading →

Generating random non-uniform data in C#

Posted on by
7

UPDATE: I’ve posted a related article here.

When building simulations of real-world phenomena, or when generating test data for algorithms that will be consuming information from the real world, it is often highly desirable to produce pseudo-random data that conform to some non-uniform probability distribution.

But perhaps I have already lost some readers who do not remember STATS 101 all those years ago. I sure don’t. Let’s take a step back. Continue reading →