What is the true randomness of random numbers?

[cDimino]

Ok, so I'm creating a science fair project, called "A Study on the Generation of Random Numbers" My basic project outline is as follows:

Purpose:
People every day use random numbers to do everything from play the latest video game to encrypt their credit card information for the sending over the Internet. These numbers are, however, not truly random, and can therefore be replicated and discovered. The purpose of my experiment is to discover what it means to be a truly random number, and how exactly the computer comes up with this pseudorandom number that it uses in place of a genuine random number, and to create a program that generates truly random numbers.

Hypothesis:
The random number generator used by a home computer is based off of the CPU’s time, in milliseconds. It is fed through an algorithm, and then given to the program requesting the number. I hypothesize that the number given is actually predictable, and is therefore not truly random. I also hypothesize that there exists a program that can create more truly random numbers, but uses unorthodox methods of going about it.

Procedure:
I will begin by creating a program which creates a more random number than the computer. I will also obtain a set of random numbers as generated by a company that specializes in the creation of random numbers, and I will compare the randomness of all three (this means that I will have to establish a ‘standard of randomization’ from which I can base my comparison on). Then I will explore the future possibilities of the employment of these truly random numbers in the world, as well as in the home computer.

The most difficult part for me will be that "standard of randomness". I am currently unaware of something like this, but that is most likely due to my lack of education :-(. I would appreciate ANY help, seeing as I want to get an A+ (and maybe wow a few people, heh). Help concerning the "Standard of randomization" would be most appreciated at this point, but any help at all would be greatly appreciated. :-D

EDIT:

Don't worry about going over my head. I have a few months to grasp any new concepts I'll need to do this properly. I want this to work well, so the best method, regardless of conceptual difficulty, would be most helpful :-D Also, if this is misposted, I apologize, and again cite my lack of education =)

 

[chroot]

I think you're off to a very good start! Random numbers are an area of active research, and thus are an excellent topic for a world-class science fair project.

Well, let's see... first, I have to say I'd recommend streamlining your Purpose and Hypothesis to be more about your experiment and less about your research. Every good science fair project involves a significant amount of research, so I wouldn't put something like "look up what 'random' really means" in your purpose -- it is implied.

Note that pseudorandom number generators are not necessarily tied to "CPU time" at all.

Note that it's really not difficult to show that a pseudorandom number is not really random -- just give it the same seed twice, and it will give you the same sequence of numbers, twice. It isn't much of a science project to show that pseudorandom numbers aren't random, so I wouldn't worry about doing so.

Note that no computer algorithm is capable of generating truly random numbers -- the best that a digital computer can do is produce very good pseudorandom numbers.

How do you tell whether one sequence is more random than another? Collect statistics. Some basic features of truly random binary numbers are that the number of ones and zeros is equal over a sufficiently large sample, that the correlation coefficient between digits is very close to zero for a large sample, etc. There are many such statistics.

There are, in fact, hundreds of different PRN generator algorithms written by many different people, all with different strength and weaknesses. You might want to consider pitting some of these algorithms against each other, and letting your statistics determine which are better than the others.

Or you might want to consider something very unique, like using different random number generators to encrypt a large volume of text (many entire books, for example, from bartleby.com), then use cryptanalytic techniques on the resulting encrypted data. If the pseudorandom number generator is not very good, you'll be able to do some statistics on the encrypted data and show, at a minimum, that it's english text.

This kind of project is very cerebral, and you admittedly will have your reading cut out for you. In fact, the very best thing you can do is to go to good library and do some serious reading. You might want to consider starting with some of the "bibles" of cryptography, like Applied Cryptography by Schneier, and continuing with any of its hundreds of bibliography entires.

- Warren

 

[berkeman]

Sounds like a fun project. Yes, given the same seed value, a computer software or hardware random number generator generates the same sequence again. One measure of randomness is whether all of the potential numbers are covered before the sequence repeats. So if you have a 1-byte number that you are generating, all 256 possible results should be generated before the sequence repeats. It would be nice if the sequence would not actually repeat, but I'm not sure if there are algorithms that can do that. You may need to have an analog component to your random number generator in order to get more truly non-repetitive random behavior.

One analog thing that came to mind was an interesting set of discussions I read once about using Lava Lamps as random number generators. A Lava Lamp is an example of a fairly simple mechanical arrangement that exhibits fairly complex random analog behavior over time. To find some articles, I googled "random number" "lava lamp" and got lots of good hits. Here's one:

http://www.maa.org/mathland/mathtrek_5_7_01.html

You can also amplify white noise (if you have a truly white noise source) and use that as part of an analog random number generator. Have fun on the project!

 

[chroot]

That's a whole 'nother ball of wax, berkeman. You could use all kinds of different sources to generate random numbers, and then determine which is the best.

Some possibilities:

- you could use a program to record the "sound" heard by your sound card when there's no microphone plugged in.

- you could use a program to record the "image" seen by a webcam when the lens cap is on it.

- you could set up your webcam to view a lava lamp, and process the image of the lava lamp to extract its randomness (neat idea berkeman!)

- you could use a program to measure the times between the arrivals of network packets.

All of these are sources of "true" randomness in the envrionment that are available to your computer.

- Warren

 

[berkeman]

So you're saying that the Lava Lamp is a whole 'nother ball of wax? I got to spend some time thinking about that one, chroot. Lean back in the old bean bag chair, ...

 

[chroot]

Well, the concept of doing a science fair project on the different methods of getting true randomness into your computer, versus using different kinds of PRNGs, is rather unique.

BTW, most modern computers actually have a hardware random number generator, based on diode thermal noise, integrated into their north bridge chip. Most software doesn't make use of that kind of hardware, but it's still available for your use. It's probably a very good source of very random numbers, and might be useful as a benchmark against which to judge other sources.

- Warren

 

[cDimino]

Some basic features of truly random binary numbers are that the number of ones and zeros is equal over a sufficiently large sample, that the correlation coefficient between digits is very close to zero for a large sample, etc.

I particularly like this idea. I think what I will do is use a few different ways to get random numbers (a list of around 100k numbers, generated by the typical computer Rand() function, 100k numbers from a white noise source, another 100k from a lava lamp random number generator, as well as a random generator of my own creation) and use compare these different ways with the different methods of calculating randomness, one method being the described one above.

I've heard of this thing called a "chi-square" while googling. What is this, and how does it relate to my SciFair project?

 

[berkeman]

I've heard of this thing called a "chi-square" while googling. What is this, and how does it relate to my SciFair project?

I've heard of it but never used it. Here are a couple wikipedia pages in case they help:

http://en.wikipedia.org/wiki/Chi_square

http://en.wikipedia.org/wiki/Chi-square_test