Random number in range with equal probability

Question

This might be more Math related than C#, but I need a C# solution so I'm putting it here.

My question is about the probability of random number generators, more specifically if each possible value is returned with an equal probability.

I know there is the Random.Next(int, int) method which returns a number between the first integer and last (with the last being exclusive).

Random.Next() [without overloads] will return a value between 0 and Int32.MaxValue (which is 2147483647) - 1, so 2147483646.

If I want a value between 1 and 10, I could call Random.Next(1, 11) to do this, however does every value between 1 and 10 have an equal probability of occuring?

For example, the range is 10, so 2147483646 is not perfectly divisible by 10, so the values 1-6 have a slightly higher probability of occuring (because 2147483646 % 10 = 6). This is of course assuming that every value within Random.Next() [without overloads] returns a value between 0 and 2147483646 with equal probability.

How would one ensure that every number within a range has an equal probability of occuring? Let's say for a lottery type system where it would be unfair for some people to have a higher probility than others, I'm not saying I would use the C# built in RNG for this, I was just using it as an example.

Answer 1

I note that no one actually answered the meaty question in your post:

For example, the range is 10, so 2147483646 is not perfectly divisible by 10, so the values 1-6 have a slightly higher probability of occuring (because 2147483646 % 10 = 6). This is of course assuming that every value within Random.Next() [without overloads] returns a value between 0 and 2147483646 with equal probability.

How would one ensure that every number within a range has an equal probability of occuring?

Right, so you just throw out the values that cause the imbalance. For example, let's say that you had a RNG that could produce a uniform distribution over { 0, 1, 2, 3, 4 }, and you wanted to use it to produce a uniform distribution over { 0, 1 }. The naive implementation is: draw from {0, 1, 2, 3, 4} and then return the value % 2; this, however, would obviously produce a biased sample. This happens because, as you note, 5 (the number of items) is not evenly divisible by 2. So, instead, throw any draws that produce the value 4. Thus, the algorithm would be

 draw from { 0, 1, 2, 3, 4 }  if the value is 4, throw it out  otherwise, return the value % 2 

You can use this basic idea to solve the general problem.

however does every value between 1 and 10 have an equal probability of occuring?

Yes, it does. From MSDN:

Pseudo-random numbers are chosen with equal probability from a finite set of numbers.

Edit: Apparently the documentation is NOT consistent with the current implementation in .NET. The documentation states the draws are uniform, but the code suggests that it is not. However, that does NOT negate the fact that this is a soluble problem, and my approach is one way to solve it.

Answer 2

The C# built in RNG is, as you expect, a uniformly distributed one. Every number has an equal likelihood of occurring given the range you specify for Next(min, max).

You can test this yourself (I have) by taking, say, 1M samples and storing how many times each number actually appears. You'll get an almost flat-line curve if you graph it.

Also note that, each number having an equal likelihood doesn't mean that each number will occur the same amount of times. If you're looking at random numbers from 1 to 10, in 100 iterations, it won't be an even distribution of 10x occurrence for each number. Some numbers may occur 8 times, and others 12 or 13 times. However, with more iterations, this tends to even out somewhat.

Also, since it's mentioned in the comments, I'll add: if you want something stronger, look up cryptographic PRNGs. Mersenne Twister is particularly good from what I've seen (fast, cheap to compute, huge period) and it has open-source implementations in C#.