How random is Random.Next()?

Question

I have been doing some testing on the Random class and I have used the following code:

while (x++ <= 5000000)
{
    y = rnd.Next(1, 5000000);
    if (!data.Contains(y))
        data.Add(y);
    else
    {
        Console.WriteLine("Cycle {2}: Repetation found for number {0} after {1} iteration", y, x, i);
        break;
    }
}

I kept changing the rnd max limit (i.e. 5000000) and I changed the number of iterations and I got the following result:

1) if y = rnd.Next(1, 5000) : The average is between 80 to 110 iterations
2) if y = rnd.Next(1, 5000000) : The average is between 2000 to 4000 iterations
3) if y = rnd.Next(1, int.MaxValue) : The average is between 40,000 to 80,000 iterations.

Why am I getting these averages, i.e. out of 10 times I checked for each value, 80% of the time I get within this average range. I dont think we can call it near to being Random.

What can I do to get a fairly random number.

Congratulations for discovering the birthday paradox. (http://en.wikipedia.org/wiki/Birthday_problem) — kennytm, Feb 25 '10 at 14:53
9, 9, 9, 9 Are you sure that this is random? That's the problem with random, you can never be sure. <3 Dilbert — Pierre-Alain Vigeant, Feb 25 '10 at 14:57
Duplicate: http://stackoverflow.com/questions/2145510/ (only language is different, the code is identical). — Dawid, Feb 25 '10 at 15:08
With your definition of random, consider using something like `class myRandom { int rnd; public int Next() { return rnd = ++rnd % int.MaxValue; } }` Guaranteed noncyclic, until all positive ints are used up. — Zano, Feb 25 '10 at 15:16

score 32 · Accepted Answer · edited Jan 31 '21 at 06:49

32

You are not testing for cycles. You are testing for how long it takes to get a random number you've had before. That's completely different. Your figures are spot on for testing how long it takes to get a random number you had before. Look in wikipedia under "the birthday paradox" for a chart of the probability of getting a collision after a certain number of iterations.

Coincidentally, last week I wrote a blog article about this exact subject. It'll go live on March 22nd; see my blog then for details.

If what you want to test for is the cycle length of a pseudo-random number generator then you need to look for not a number you've had before, but rather, a lengthy exact sequence of numbers that you've had before. There are a number of interesting ways to do that, but it's probably easier for me to just tell you: the cycle length of Random is a few billion, so you are unlikely to be able to write a program that discovers that fact. You'd have to store a lot of numbers.

However, cycle length is not the only measure of quality of a pseudo-random number generator. Remember, PRNGs are not random, they are predictable, and therefore you have to think very carefully about what your metric for "randomness" is.

Give us more details: why do you care how "random" Random is? What application are you using it for that you care? What aspects of randomness are important to you?

edited Jan 31 '21 at 06:49

Glorfindel

21,988
13
81
109

answered Feb 25 '10 at 14:51

Eric Lippert

647,829
179
1,238
2,067

+1 @Eric: Are you filling upp your blog before release? That's funny. – Zano Feb 25 '10 at 15:04
7

@Zano: Yes, I write a whole pile of articles at once and then set them up to go live twice a week. I'm about two months ahead at any given time. Raymond Chen publishes like five or ten times a week and has several *years* worth in his queue; I don't know how he does it! – Eric Lippert Feb 25 '10 at 15:11
Hehe that's funny. But don't the articles get outdated, if you do it years ahead of time? For instance a newer version of .NET or C# would behave different, etc. – Joan Venge Feb 25 '10 at 17:49
1

@Joan: Most of Raymond's articles deal with C programming with the Windows API--that doesn't change nearly fast enough to outdate many of the articles. – Ron Warholic Apr 27 '11 at 16:12
@EricLippert can you tell mi , here : http://www.sanfoundry.com/csharp-program-generates-randam-numbers/, Programmer generating random number. But how it takes the generation limit. means in for loop, he gives max `i<10`, therefore generated number has max 9 digits. So how it is taking a limit of less than 10 directly...?? – Rahul Chaudhari Mar 14 '16 at 06:03

score 18 · Answer 2 · edited Jan 31 '21 at 12:19

You are assuming that the randomness is better if numbers are not repeated. That is not true.

Real randomness doesn't have a memory. When you pick the next number, the chance to get the same number again is just as high as any other number in the range.

If you roll a dice and get a six, then roll the dice again, there is no less chance to get a six again. If you happen to get two sixes in a row, that doesn't mean that the dice is broken.

The randomness in the Random class it of course not perfect, but that is not what your test reveals. It simply shows a phenomenon that you get with every random number generator, even if actually creates real random numbers and not just pseudo-random numbers.

It might, actually. I have 10-sided dice that come up as 8,9,0 way more often than other numbers. They are great for Marvel Super Heroes, but bad for other games which want lower numbers. I.E. Dice CAN be broken. — PRMan, Apr 25 '17 at 17:58

score 3 · Answer 3 · answered Feb 25 '10 at 14:55

You are judging randomness by repeat pairs, which isn't the best test for randomness. The repeats you see are akin to the birthday paradox: http://en.wikipedia.org/wiki/Birthday_problem, where a repeat event can occur with a small sample size if you are not looking for a specific event.

score 2 · Answer 4 · answered Feb 25 '10 at 14:49

Per the documentation at http://msdn.microsoft.com/en-us/library/system.random.aspx

To generate a cryptographically secure random number suitable for creating a random password, for example, use a class derived from System.Security.Cryptography..::.RandomNumberGenerator such as System.Security.Cryptography..::.RNGCryptoServiceProvider.

score 2 · Answer 5 · answered Feb 25 '10 at 14:52

2

A computer can't generate a real random number. if You need a real random number (David gave you the best option from dot net framework) you need an external random source.

answered Feb 25 '10 at 14:52

Dani

14,639
11
62
110

1

I like how random.org use the noises in atmospheric disturbance. – Pierre-Alain Vigeant Feb 25 '10 at 15:01

How random is Random.Next()?

5 Answers5