views:

290

answers:

10

How is exactly that we talk about "true random" numbers when we are actually measuring something. I mean, isn't measuring almost the opposite of randomness.

Som articles says that, for example, throwing a dice is "true random". Of course it isn't Pseudo-random, but is it even random?? If you could have a machine that throw dices from de exactly same position and always in the same direction with the exact same force always: woudn't it always turn out the same number? (I thing it does).

Please, can someone help me understand "true random" numbers??

+1  A: 

On computer (Quartz) you can't generate true random because 2+2 is always 4. Then your random can be only pseudo random better or not better depends on how good this is hashed.

Svisstack
Yes, I know a computer can not generate random number, but I thing before thinking "the best" pseudo-random number generation it would be good to understand the REALLY (true) random numbers even that they can not be generated by computers
Diego
Huh ? Maybe it's just me, but I can't make any sense of this...
DarkDust
You just can't get a true random number from such a logical device as a computer. A computer is per definition expected to do exactly what you ask it to do. If it doesn't, then it's a bug, and a pretty serious one..
Onkelborg
+4  A: 

I think that when some talks about "true random" numbers in IT this is always from measuring/observing something that is thought to be random in contrast to the pseudo-random algorithms that will always return the very same pattern (given the same starting point or after wrapping around after a certain length). For example, I've heard about devices that measure the electric noise produced by some components like transistors. This is indeed "more" random than a deterministic algorithm.

To increase the "randomness" I know that for example Linux tries to incorporate various external events into its random number generator, for example mouse movements, key presses (AFAIK even duration of key presses), timings from the HD, etc. pp. That is, they try to improve the deterministic algorithm by adding indeterministic sources to it.

DarkDust
+3  A: 

For true randomness you'll need to observe physical events. Try this.

mdrg
+2  A: 

I suppose, theoretically, a precise machine could be built that could skew the results of a die throw. In practice, though, there is always some level of variation that can't be predicted. That's where the randomness comes from. Certainly when a person throws a die, there is so much variation in each throw that the result is "truly random".

Computers can generate "true random" numbers by making use of random phenomena like quantum mechanical effects, or electro-magnetic noise.

Andrew Cooper
+2  A: 

True randomization is a problem when you are working with logic, logic isn't random (at least not if it's working correctly..) That's the reason to why some cryptographic programs ask you to move your mouse in a random pattern since it's hard to reverse engineer you ;)

Anyway, as @DarkDust said, and @mdrg mentioned, you have to rely on physical observations, an example would be to hook up a radition meter and observe when some radioactive materia falls apart. Or measure the wind speed outside. Or measure the noise in some transistor. With some mathematical transformation it's impossible (apart from brute force..) to reverse engineer that random number then.

Onkelborg
+1  A: 

Experiments have shown that coin tossing by a human is not random - it appears that there is roughly a 51% chance that the face upwards when the coin is tossed will show when it lands.

Any physical event that is based on very large numbers is likely to generate true random numbers - examples are white noise or the last few digits of the number of transactions in a day on a major stock market.

Measurement is not the opposite of randomness. Measuring randomness can only be done on very large numbers of the random event, and is statistical in nature. What measuring randomness does is look for patterns in the event at different levels - single events, runs of two events, runs of three events etc. A pseudo random generator will generate patterns, if only the full cycle of the generator, but the better generators show fewer patterns.

Chris Walton
Do you have any link to the experiments about coin tossing?
Diego
@Diego - sorry I don't. I got the information from QI (Quite Interesting) - a UK quiz/entertainment show that concentrates on "things that you think you know that just ain't so".
Chris Walton
+3  A: 

True random numbers are those impossible to predict even when you have all the information you can currently collect. For example, the decay of radioactive atoms, wind direction and velocity at different places in the world or even the noise generated by a webcam (this list is in decreasing degrees of impossibility to predict.) There is no guarantee that what's random now will be random a thousand years from now.

Pseudo random numbers are totally possible to predict with the right information, either exploting flaws or knowing the seeds.

To get as close as possible to true random numbers in a computer, you'd need some special hardware.

The crucial difference is that we currently don't know how to predict stuff considered random, but we do currently know how to predict pseudo random numbers.

See this question for all the information you could possibly want about this.

Vinko Vrsalovic
"For example, the decay of radioactive atoms, wind direction and velocity at different places in the world or even the noise generated by a webcam". What you are saing is that those things are random and can not be predictable with right information. I'm not an specialist in any of those things but I think any of them with the right info. is predictable.
Diego
@Diego: The critical thing here is that by "the right information" of course I'm referring to information that can currently be obtained. There's no way to tell what will we be able to predict 100 years from now, but currently, and for the foreseeable future, it's not possible.
Vinko Vrsalovic
In fact, for many random processes we don't even know what the right information **would be**.
Vinko Vrsalovic
@Diego: Wrong. Specifically, radioactive decay is an example of something that quantum physics (which has been proven to model this kind of small-scale event very well) says cannot be, and never will be, predictable. Electrical noise is a related phenomenon, though I think the unpredictability is not as firmly grounded in basic physics. Wind is a different matter - an example for a chaotic system where over time any inaccuracy in starting parameters cause models to deviate exponentially. That means you'd need a virtually infinite amount of information to make long-term predictions.
Michael Borgwardt
Wow.. never thought it that way!
Diego
+8  A: 

Randomness is essentially a measure of how much we don't know. The universe may or may not be truly deterministic, it doesn't matter - we don't know (and have no foreseeable way of knowing) what the exact time between 2 cosmic ray impacts will be. For pseudorandom numbers, we do, in principle, have a way of knowing, because we can recreate the initial conditions and get the same output again.

mokus
Which is very important for testing. If your code uses random numbers, it's nice to be able to seed your generator with a known number and get the same sequence of "random" numbers again.
TMN
One interesting irony is that the amount of 'unknown' information is often difficult to measure. If one has a free-running high-speed counter and clocks it at some arbitrary moment, having not paid any attention to it recently, the result is for all practical purposes random. If one checks the counter once per day, thermal and other variations will probably make the result completely unpredictable and thus random. If one checks it more often, the results may start to be somewhat predictable, but there's no way of knowing how often one can safely use it.
supercat
Indeed. The fact that we don't know how much we don't know is what makes statistics so fun :)
mokus
+5  A: 

Quantum effects are the source of this "True Randomness". E.g. the Heisenberg Uncertanity Principle says that your dice thrower can't exactly define both impulse and location of its throwing arm. (Reading up on pop-sci quantum physics can be scary - the predictability and stability of our world seems to be no more than a great feat of statistics.)

There are - as mentioned in other replies - appliances that turn quantum effects into observable random number generators. There are algorithms to "extract" the randomness of any stream of data. There are test algorithms to check if a stream of data "behaves" like a random stream.


OTOH you can argue rather successfully that "random" is a man-made concept, i.e. something that isn't integral part of the objective world, but our limit of understanding (though the uncertainty principle is considered to be not just an observer effect).

When someone asks for any random number generator, the counter question should be: for what application? In the context of this discussion: who do you need to fool? Pseudo vs. True are just generation mechanisms, not fundamental opposites.

In that sense, chaotic beahvior is often "random enough" for most purposes, and can be cretaed with few degrees of freedom already.

peterchen
reason for downvote would be interesting on this one.
peterchen
+1 Good food for thought.
John Isaacks
AFAIK, the uncertainty principle applies to particles, not dice nor robotic arms.
Vinko Vrsalovic
@Vinko: Because dice and robotic arms aren't themselves particles? Just because the quantum mechanical effects are *really* small doesn't mean they're gone.
Nick T
@Nick The effects are so small that other models are better suited to predict the behavior of dice and robotic arms.
Vinko Vrsalovic
@Vinko: I've cited quantum effect as what I understand is the physical source of what we call "true" randomness. I know that it's not *useful* to describe such a dice-throwing roboter, but in my (undoubtly limited) understanding of the Copenhagen interpretations, it's a non-circumventable limit to reproducability. In practice, other, more significant effects - like tolerance and use - will likely introduce most randomness, however, they are (in classic description) shortcomings of the machine, our knowledge, and our math.
peterchen
+2  A: 

Randomness is really important for a large set of problem solving techniques in AI, economics, physics etc. The need to impose a probability distribution over a set of possible outcomes drives the need for better and better random number generation.

That said, true randomness is probably a debatable concept. Deterministically speaking it shouldn't happen - a la your dice tossing example. I think this is kind of a sensitive argument for philosophers. In reality we can take 'random' measurement with a geiger counter and some radioactive material. In an ideal setting this gives us a pretty good result made by measurement.

From a human perspective the randomness of our number generators only needs to achieve a certain probability of being random given a priori knowledge of the desired complexity of the outcome the random numbers are going to be required for.

If you think about using Bayes principle given the degree of true randomness measured by some arbitrary notion about how good your random numbers are (In the form of a probability distribution) then you can say something about 'trueness' of man-made random number generation. In fact the 'trueness' will approach zero as the period of a truely random number generator is infinite. This only matters when you get that far but we can't - so 'truely random' is a pretty useless distinction for computer scientists who know how to design a nice pseudo-random (everything is pseudo-random relative to some scale) number generator.

everybodyelse
For a related (opposite) sort of idea look herehttp://math.stackexchange.com/questions/6196/the-pseudoness-of-pseudorandom-number-generators
everybodyelse