Random Numbers, true random?

[FunkyChicken]

Hi there,

I'm trying to understand how a computer generates a random number, i cannot simply think of any mathematical calculation that would give a TRUE random number.

Because the computer is a contained machine i cannot understand how the number can be random? If i ran a random number generator for say 24 hours and logged the results would i start to notice some strange outputs, i.e. some numbers appearing not at all, some alot more than others?

For a true random number would the computer need to have some kind of input from the "real" world? By this i mean something physical/biological that we can grasp, this would then allow for true measurement (but only to the degree of accuracy of the measuring device).

Im really stumped by this, its driving me nuts, last nyt i was awake in bed trying to figure this out, no luck.

So, my question is, can a computer give me a real honest random number? If so how?

Cheers in advanced guys

[converge]

That is quite a philosophical question. what exactly is a TRUE random number. If I walked up to you, you asked me to picked a number from 1 to 10, and I told you 3... is that random, or was I predispositioned to tell you that number?

From my small understanding of the subject, most random functions obtain their seed through the RTC or some similar differing but predictable source. In recent years I have heard of more pushes to base the functions off of environment readings like CPU temperature at a given time, etc. All this, of course, trickling down from years of mathematics nerds in Universities that are undertaking the subject matter with very interesting approaches.

Do a google for 'random number generators'. You'll find more info on the matter than most people care about for implementing a high-scale, high-grade solitaire applet.

[astcell]

Good topic here. I used to have a Texas Instruments calculator that generated random numbers as an extra feature. The numbers were from .00 to .99 though, I do not know the math or algorith it used or why it could not give a 7 digit random number if you so wanted.

Could a mathematical solution such as "pi" be considered a random number? Even though there is no known repetitive pattern or end to the numbering, since the number is the solution to a problem I wonder if it may be instrinsicly buried into other math questions.

And if you decide to purchase a randon number generator, how do you decide on which one out of all the options? Would using thought and humna judgment therefore not make the numbers truly random, but make them random inside of a smaller scale? I suppose you'd need to use a random number generator to pick the one to buy for you...

[TheCotMan]

I'm trying to understand how a computer generates a random number, i cannot simply think of any mathematical calculation that would give a TRUE random number.

Such things are quite difficult. The subject of generation of numbers that appear to be random is actually part of crypto as well as games.

Consider ssh and the key generation process. The use of /dev/random vs /dev/urandom.

I like to think of there being 4 random number generators (though there could be more)
* Random number generators that do not work (bad distribution of value over time or they can be predicted (For example if we assume single digits beyond the decmal place with "pi" are evenly distributed, once someone is able to identify how we are coming up with our random numbers, then to that person they are not true random numbers.))
* Random number generators that are just software and may include a seed to get started.
* Random number generators that are a combination of software and hardware (where system hardware is used to provide entropy in generation of random numbers or use things like "the entropy gathering daemon." -- egd)
* Hardware designed to generate random number (there are cards designed to help with this. One example could be the use of radioactive decay in time to generate entropy, but others exist outside of software, and use dedicated hardware.)

Because the computer is a contained machine i cannot understand how the number can be random? If i ran a random number generator for say 24 hours and logged the results would i start to notice some strange outputs, i.e. some numbers appearing not at all, some alot more than others?

This is one of the two parts for a good random number generator... the values produced should be evenly distributed over time-- meaning, the chances for any single digit should be the same as any other digit each time a digit is selected.

This means a good random number generator may have times where, out of 10 digits, all end up being "1" or all different, or a few repeated and sequencial or not.

Think of it like flipping a coin or rolling dice-- it is possible to get the same result over and over, but the chances of that happening are small if you assume that is desired a certain number of time in a row before they dice are thrown, or the coin is flipped.

The chance of Heads three times in a row is 1 in 8. The chances of three heads in a row assuming the first two were heads is only 1 in 2-- each throw is independent of the last, but still should approach even distribution with enough time.

For a true random number would the computer need to have some kind of input from the "real" world? By this i mean something physical/biological that we can grasp, this would then allow for true measurement (but only to the degree of accuracy of the measuring device).

In software random number generators, it can be a "Seed" while in others it can be from entropy generating devices. Consider interrupts , I/O, and hardware use on a system. How they are used, and when they are used can help with generating entropy.

Compare /dev/random to /dev/urandom and how one can become a blocking event when your system runs out of entropy on Linux.

So, my question is, can a computer give me a real honest random number? If so how?

When you consider devices on your system, and when they come on, or go off, you have multiple seeds for software-based random number generators. Use of the value of the clock is an older source that is still used today, and sometimes with other devices.

[bascule]

Quantum phenomena seem to be our most reliable entropy source for random numbers. Consider the Aspect experiment, where the spin of an electron is checked and generates a perfectly random 50/50 distribution between clockwise and counterclockwise. Modern random event generators can use quantum tunneling or "thermal noise" to generate truly random numbers.

I think the coolest application of quantum recently is streaming OTP using entangled electrons (just like the Aspect experiment). Both sides will get true random numbers, but because the electrons are entangled they will be the same. It's not going to be too long before truly unbreakable encryption is commonplace...

[Ridirich]

Great post! Honestly, in my own opinion a computer does not trully generate "random" numbers. It uses software which has a mathmatical odds calculator to determine which set of numbers to use, and in which order they go.

Simplest example would be "winamp". Load 300 songs in there. Press "random". You will notice the songs never play twice(unless you have 'repeat all' on and it has gone through all 300). Now, if it were random it would be possible to stop on the same song twice, if you watch which songs it plays, there is usually a method to the madness, and random implies a sort of controlled chaos.

Another good example is the oldschool computer boardgames like risk or monopoly. When you roll the dice, it is not trully random. For the game it has a list of numbers of 1-6 per dice that are predetermined to be used, and it runs off that script; if you roll two dice it used 1 of the numbers per die on the list, and so fourth depending on how many die you roll.

Think of roulette. You call "black 21", or "red 18" or what have you. You have a 50/50 chance of landing on the color of your choice(as there is only red or black). When you spin the wheel, it is "random" where it stops, and you could theoretically hit the same number 8 times in a row.

[astcell]

If WinAmp will play one of 300 songs at random then pull it out of the mix and select a random song out of the remaining 299, yes that may be truly random, or as random as the programming logic allows. If it keeps the song in the mix it may play the song 300 times, or it may play it just once. The randomness is there to a point.

Now if the song is about 3-4 minutes long, then another random song comes on, is the number truly random since it is selected at 3-4 minute intervals? Or would it be consistently random?

Someone go get Mr. Schroedinger's cat, please.

[TheCotMan]

Simplest example would be "winamp". Load 300 songs in there. Press "random". You will notice the songs never play twice(unless you have 'repeat all' on and it has gone through all 300). Now, if it were random it would be possible to stop on the same song twice, if you watch which songs it plays, there is usually a method to the madness, and random implies a sort of controlled chaos.

A better term, used on some CD players is "random shuffle" or "shuffle" for playing songs in random sequence.

This is more appropriate, since the effect is similar to cards.

Randomization can be applied to items in a set and still be called randomization. One of the purposes of randomization is to decrease the level of certainty for the next event.

Usually when people state something like this:
I will make a random selection there is an implication of of an item from the given set.
Is it proper to be ambiguous? Nope. Is it acceptable? Depends on the person who is listening; are they a mathematician? (heh-heh)

This is like:
"Pick a number from 1 to 10."
"pi" || "SQRT(2)" || "SQRT(3)" || 2.1337 - e^(SQRT(-1) * pi)
"Smartass."

"digit" or "integer" or "whole number" is implied even though it is not stated-- of course if digit was used, maybe "10" could not be selected. ]:>

[astcell]

We had a CD player that, when set to random, was supposed to play randomly from the entire CD collection as well as track. But it tended to choose one CD for 2-3 songsbefore moving on. Random? Well, maybe. I guess what we wanted was for the odds of choosing a specific CD to go down if it had been played before. Hence, not really random.

[lil_freak]

Quantum phenomena seem to be our most reliable entropy source for random numbers. Consider the Aspect experiment, where the spin of an electron is checked and generates a perfectly random 50/50 distribution between clockwise and counterclockwise. Modern random event generators can use quantum tunneling or "thermal noise" to generate truly random numbers.

I think the coolest application of quantum recently is streaming OTP using entangled electrons (just like the Aspect experiment). Both sides will get true random numbers, but because the electrons are entangled they will be the same. It's not going to be too long before truly unbreakable encryption is commonplace...

Bascule, what are your thoughts on using Macroscopic processes to obtain/generate random numbers?




On an other note, I got to thinking about this question while reading all of the posts that have been made under this topic: Has anyone thought about the process that occurs when using an array to generate random numbers?

In most code when you use an array to generate random integers you should be able to see whether each possible value is generated approximately equally as often, telling the coder if the randomness is fair or not. Thinking about this I was perplexed by the “what ifs”. With that in mind I got to thinking about happens when you use multiple arrays? Would the randomness still be the same even if the assign process was changed? Plus what happens when you throw a complex loop process into the mix, how would one check to make sure that the IF condition was pulling random numbers from the arrays?

Oh my!!! Too much information to think about all at once, then again this day seems to be slow so maybe I can put my questions to good use and write some code to test my questions.

[astcell]

I would guess that with an infinite amount of numbers a pattern would eventually emerge since there are only so many ways to arrange, say, a million numbers. Those million numbers will appear again, eventually, solely due to the many other patterns which will have been permutated. Hence with ten digits to use, we are less random than, say, if we had 12 digits.

[dYn4mic]

Good thread.
I don't have a great understanding of computers and random numbers but im working on it... I think its a pretty important thing to understand. You can see this working when you have people type on the keyboard or move the mouse or disk access when your creating GPG keys. Some people also use the signals from a microphone thats just 'on'. I'm sure the NSA has some intresting methods. Also the amout of entropy in TCP sequence number generation led to some TCP RST attacks because of a lack of entropy in ISNs.
see: http://lcamtuf.coredump.cx/newtcp/

Dan Kaminsky took it to the next level and did some fun stuff with bash's $RANDOM and graphed them in a 3d cube.
You can take almost any dataset and use phentropy to plot it.

"Phentropy plots an arbitrarily large data source (of arbitrary data) onto a three dimensional volumetric matrix, which may then be parsed by OpenQVIS. Data mapping is accomplished by interpreting the file as a one dimensional stream of integers and progressively mapping quads in phase space. This process is reasonably
straightforward: Take four numbers. Make X equal to the second number minus the first number. Make Y equal to the third number minus the second number. Then make Z equal to the last number minus the third number. Given the XYZ coordinate, draw a point.

It turns out that many, many non-random datasets will have extraordi-narily apparent regions in 3-space with increased density, reflecting common rates of change of the apparently random dataset. These regions are referred to as Strange Attractors, and can be used to predict future values from an otherwise random system.

Cool stuff. As you can see $RANDOM isn't competely random...
http://www.doxpara.com/pics/picKLE-c...rand1_1024.jpg
http://www.doxpara.com/pics/picKLE-c...rand2_1024.jpg

More info can be found on doxpara.com ooorrr he could elaborate more himself, hopefully with an elbow thats all fixed up.

Anyone test how random the ipod shuffle is?

[lil_freak]

Anyone test how random the ipod shuffle is?

Kinda, but after three hours I got tired and moved on to doing other stuff. As far as I can tell thou it did a good job with playing random songs from my random stored albums.

[Macavity]

My answer: Yes, and no.

Yes, because if you're using a number generation program, you don't know what number it'll come up with.

No, because if you understand how the program works and what inputs it uses to generate a random number, it's theoretically possible to discover a way to predict what number the program is most likely to generate based on the knowledge of the program's method of number generation.

[bascule]

Okay, here's my definitive answer: no, I don't believe there are truly random numbers. Here's my purely hypothetical reasoning behind that:

The probabilistic nature of QM is merely an artifact of the observational nature of our inquiry into its inner workings. Because all of our observations take place in the theater of a temporospatial "background" whose state is unprobable via direct observation, its behaviour to us appears random in certain aspects. This is the cause of the Heisenberg Uncertainty Principle.

When a background independent theory of the universe is constructed, it will be both deterministic (i.e. conforming in all ways to a definable set of mathematical operations) and discrete (i.e quantifiable in integral terms). For example, insofar as I understand it, Loop Quantum Gravity presupposes such a universe.

Given these qualities, the universe will be expressible as a Turing-complete algorithm, and we will discover that time is a mere artifact of the operational structure of the underlying algorithms (i.e. when the universe isn't "working" on "you," it's "working" on everything else.

If we were to further analyze the entropy data, and perhaps correlate it in temporospatial terms, higher level patterns would emerge which would give us clues into the higher level state. Princeton's Global Consciousness Project attempts to do just that, and has noticed some astounding correlations in entropy data collected from random event generators (dubbed "eggs") that use quantum tunneling or "thermal noise" to generate "truly" random numbers. For example, a graph of variance in the temporospatially correlated egg data surrounding the 9/11 terrorist attacks makes the pattern dramatically clear.

These patterns would seem to suggest higher level deterministic machinery working in the "background" whose state can be probed and ascertained by enough analysis and correlation of seemingly-random quantum events.

If you have the algorithm and enough of the state, you can figure out the causation behind the generation of any "random" number.