pseudo-random numbers

[computerages]

Hi, I have read from somewhere that random numbers generated by computers are really pseudo-random numbers in reality. If this is true, could anyone tell me what kind of patterns exist in the random numbers generated by computers that make them pseudo-random numbers?

 

thx.

[Genecks]

Nothing is random. Computers has physical boundaries and ties. In other words, their physical components, environment, programming, along with the laws of physics, determine the numbers they generate.

 

Maybe that's not what you are looking for.

[layzwombat]

I am certainly not an expert in this area, but this may be a note that will help. If you were to go into excel and use the random number generator - it will give you random numbers. However, if you are in a classroom and you instruct the class to all do the same operation in the random number generator (same mean, std, etc.) the entire class will get the same values. Is that what you are getting at?

[the tree]

A very easy way of generating pseudo-random numbers involves a calculation on the current time. In reality computers and calculators often use a calculation on the previous number, these are sometimes crackable, not always easily. One really common one is Linear congruential generators, the calculation to get from one number to the next is really easy: [math]V_{j+1} = \left( A \times V_j + B \right) \bmod M[/math], where A, B and M are constants. It is always possible to work out the constants, but I couldn't tell you how.

 

Layzwombat: that would happen with both random numbers, and reasonable quality pseudo-random numbers, it doesn't demonstrate much.

 

Genecks: although the laws of physics are deterministic (to a point), a throw of a fair die is still considered random, as is background radiation, and quite a few other things that can't be properly modeled. Pseudo-random means that if you're willing to spend the time and effort, then knowing the next number is not as impossible.

[EvoN1020v]

Computers always use algorithms to generate random numbers. I emphasize that you understand the definition of an algorithm!!

[the tree]

Oh they use algorithms to do everything, personally I think one should know what the computer is doing (the formula) then how it is doing it (the algorithm) then, I suppose, how it's doing that (the electronics?).

[Bignose]

To bring it back to the OP, one of the real problems of using pseudo-random numbers used to come up when computer chips were first being used in slot machines and poker machines in casinos. The algorithms they used to make their pseudo-random numbers would leave tell-tale signs like two relatively rare occurrences coming up right next to each other. This sign could be compared with a table of outputs from the algorithm, and since the table was small (in computer standard tens of thousands is small), you could locate where in the algorithm the computer chip was. Then the player could bet accordingly since they knew when the big payout were coming -- bet low on losers, bet high on winners obviously -- even walking away from a machine if no winners were coming for quite some time.

 

This is not nearly as big of an issue anymore, since the algorithms would generate tens or even hundreds of millions of numbers before repetition now, so getting a few results and looking them up in the table is much, much harder. Though not impossible. I don't think that Vegas will be going back to the old physical slot machines anytime soon, though, since those are much, much easier to tamper with than the computer ones.

[aj47]

You might want to read .....

http://www.scienceforums.net/forum/showthread.php?t=16839

[D H]

Wikipedia has a fairly good article on pseudo-random numbers.

 

Tree discussed linear congruent generators and pointed to a Wiki article on this subject. Tree, did you notice the disclaimer in this article

It is, however, well known that the properties of this class of generator are far from ideal.

 

Unfortunately, it is easy to write a bad pseudo-random number generator. For example, Microsoft's basic random number generator 'RAND' remains notoriously bad (surprise, surprise). It repeats after generating 32,768 values.

 

I do a lot of Monte-Carlo analyses, sometimes running tens of thousands of cases, each of which involves many thousands of calls to the random number generator. I need a very good pseudo-random number generator. I also need repeatable random numbers, which is exactly what a pseudo-random number generator gives. Suppose test case #89623 (for example) displayed some very wierd results. If I used a true random number generator, how could I possibly re-create that one specific test? With a pseudo-random number generator, I can re-create it and analyze it to death.

[the tree]

Tree, did you notice the disclaimer in this article[?]

Yes I did, I mentioned that it is always possible to "crack" an LCG. I said that LCG was popular, not good. Both *NIX and Microsoft systems use it, because the fact is that the absolute quality of pseudorandomness is not usually mission critical.

 

If for instance, you had to chose the route that a telephone connection should take, when the straightest path is too busy, then you would require pseudorandom numbers but not of absolutely brilliant quality. Same with the AI behind some computer games, who cares if one component of the opponents decision making is predictable?

 

Of course, for scientific or security purposes, you'd need something better and more complicated. I just mentioned LCG because it is so popular and really, really, easy to understand.

[computerages]

I have two more questions:

 

1. Is there any way to do a control experiment about random numbers? I mean having a control group and a experimental group and a hypothesis to prove something about random numbers. I am not really sure what could control and experimental groups contain... Do you guys have any ideas?

 

2. Does the type of hardware have any effect on the quality of random numbers generated by Mersenne twister? By quality I mean that to what extent the numbers appear to be random. I will check the quality using relative frequency probability first and then taking percent error.

 

thx guys

[the tree]

1. Is there any way to do a control experiment about random numbers?

You could confirm that they'd be evenly distributed, I guess. You wouldn't be able to prove anything interesting about random numbers, because there isn't anything. However, in a many an experiment, you will need to use a random element.

2. Does the type of hardware have any effect on the quality of random numbers generated by Mersenne twister?

No, absolutely not. The algorithm is identical regardless of hardware. Having better hardware can only help perform exactly the same operations faster (learn about Turing completeness).

[timo]

1. Is there any way to do a control experiment about random numbers? I mean having a control group and a experimental group and a hypothesis to prove something about random numbers. I am not really sure what could control and experimental groups contain... Do you guys have any ideas?

The most obvious property is that they should have the desired distribution. Another property you usually want is that they appear uncorrelated. However, for the latter there is afaik no fixed definition of what that means and several more or less usefull definitions exist. If you just count from one to ten and then start at one again, it´s obvious that the numbers are evenly distributed but hopefully your criterion for non-correlation will tell you that they are correlated. Some time ago I checked some random number generators with a program called DieHard by G. Marsaglia (who also has published a paper on a random number generator and has even published the source iirc). Maybe you can find some criteria he used when looking for it.

 

2. Does the type of hardware have any effect on the quality of random numbers generated by Mersenne twister? By quality I mean that to what extent the numbers appear to be random. I will check the quality using relative frequency probability first and then taking percent error.

As far as I can see, there are different algorithms for different bit-sizes of the register. I do not know to what extend these algorithms differ in quality but obviously an algorithm with a lower number of bits can return less different numbes. I am not sure of the step from 32 bit (which allready is 4 (US-)billion possible different numbers) to 64 bit really makes a difference in any application. Using the 32-bit algorithm on a 64-bit machine (by atificially taking 32-bit integers) will return the same values as on a native 32-bit machine, so in this sense the algorithm is independent of hardware.