# How much bias is introduced by the remainder technique?

(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?

# Producing permutations, part two

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.

# Generating random non-uniform data in C#

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