Post by: thedoc on 17/05/2013 09:25:18
Listen to this Show (http://www.thenakedscientists.com/HTML/podcasts/specials/show/20130517/)
or
If you want to discuss this show, or ask a question, this is the place to do it.
Post by: damocles on 03/05/2013 11:48:19
Post by: evan_au on 03/05/2013 12:05:45
Quote
Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin.
Using predictable circuits (such as we want to use in a computer) always produces a predictable result - if you know the program and the inputs to the program.
To generate "truly" random numbers you need a "non-predictable" hardware circuit (http://en.wikipedia.org/wiki/Hardware_random_number_generator), such as:
- measuring the voltage of a Zener diode, which generates random noise
- quantum effects like measuring the rate of radioactive decay
- using a number of unstable circuits, like a ring oscillator
- measuring the "shot noise" as single electrons travel through a semiconductor
- recording the instants in time that someone types a character on a computer keyboard
- recording the instants in time that a computer disk returns data to memory
Some new computer chips have hardware to generate random numbers built in (like 3 above), which will help them generate an unlimited supply of random numbers for these purposes.
Most computer languages have a built-in random number generator which is purely software. This depends on having a "random" seed, and then repeatedly applying a program which modifies it to produce a new number which looks quite different from the previous number (and which can be mathematically proved to be randomly different in every bit position). A good random number generator will not generate the same sequence of numbers for a very long time.
One of the more traditional arithmetic methods (http://en.wikipedia.org/wiki/Linear_congruential_generator) takes a starting seed number X0, and applies the formula Xn+1=(Xn*A + C) modulo M
By carefully selecting the numbers A, C and M (eg they must be relatively prime), it is possible to quickly generate a sequence which does not repeat for billions of numbers, and passes many tests for randomness - unless you happen to know A, C and M (http://en.wikipedia.org/wiki/Linear_congruential_generator#Parameters_in_common_use).
There are schemes which combine two or more random number generators in a table of numbers to make a sequence which will not repeat within the lifetime of the Earth.
To ensure that the numbers collected from many sources appear more random, some schemes scramble the numbers they generate. Unfortunately, if the random number generator source suddenly stops generating new random numbers (eg your Zener diode short-circuits), this "whitening (http://en.wikipedia.org/wiki/Randomness_extractor)" process may give the illusion that it is still working properly.
Post by: chris on 03/05/2013 12:59:29
"In terms of random numbers… It is a whole field of study, and random numbers are never truly random*. Even rolling dice in theory could be deterministic, if you can account for all the physics. Similarly computerised random numbers are called pseudo-random, as most random number generators works with a seed, meaning that if you insert the same seed, you will have the exact same sequence.
Measuring if they are “random enough” is done just by rolling your dice several million times, and seeing if you have a fairly (but not perfect) even distribution among your results.
*: a very simple almost truly random way is to take the current time at nano second level (or lower) and take that as your number between 0-1, other more sophisticated ways include listening to radio static, thermal noise etc. though those could have a bias depending on the surrounding environment.
Regards,
-Reenen"
Post by: distimpson on 03/05/2013 22:27:31
Post by: RD on 04/05/2013 04:28:50
http://www.fourmilab.ch/hotbits/
http://www.random.org/
http://www.random.org/randomness/
[ "random" = outcome is determined by unfathomably complex mechanism.]
Post by: chris on 04/05/2013 10:41:14
I'm now looking for someone to record me a short answer for the radio to explain this and also to demonstrate who we can prove, to the satisfaction of a mathematician, that a generated number sequence really is random.
Can anyone help or volunteer?
Post by: wolfekeeper on 04/05/2013 16:35:06
One notable test is Kolmogorov randomness:
http://en.wikipedia.org/wiki/Kolmogorov_complexity#Kolmogorov_randomness
Pretty sure you can never prove numbers to be random, the best you can do is find a pattern in the numbers that prove they aren't!
(That's basically what the Kolmogorov complexity test is for, if you can write a short program to generate the numbers then you've found a pattern and it's not random.)
Also compression, if you can compress it, then it's not random.
And of course for any finite length, occasionally a random sequence will appear to be non random!
(But that gets less likely for longer sequences.)
Incidentally, it's theorised that quantum mechanical processes can give truly random results, but extreme care needs to be exerted to avoiding accidentally biasing the number, and to exclude external interference from radio and similar.
Post by: evan_au on 05/05/2013 11:59:08
- "Alice" has to use a sequence of apparently random numbers to modify a message that has to be transmitted securely, often using the Exclusive-Or (XOR) function.
- The receiver, "Bob" has to use exactly the same sequence of numbers in the same sequence to modify the message back into readable form, using XOR.
- In this case, the numbers used by Alice can't be truly random, as Bob needs exactly the same numbers, so a pseudo-random number sequence is actually desirable.
This produces some tougher requirements on pseudo-random number generators:
- The sequence of pseudo-random numbers must be at least as long as the sum of all possible messages without repeating, as any repeats in the number sequence helps in breaking the code.
- There must not be any detectable patterns in the number sequence, as this helps in cracking the code
- It may be possible to determine part of the pseudo-random sequence by sending a known file over an encrypted link. However, knowing this part of the number sequence must not allow determination of the internal state of the algorithm, or the next or previous numbers in the sequence.
- You should assume that any intruder knows the encryption algorithm (or can get a copy by reading the computer hard disk or stealing a device which implements the algorithm)
- Installing spyware on a computer may allow determining the internal state of the algorithm and all future states, but should not allow determining any previous states.
Post by: AndroidNeox on 12/05/2013 23:37:26
Post by: damocles on 13/05/2013 05:22:14
Whether randomness exists is a metaphysical question that I've yet to see addressed, convincingly. The best we can do is unpredictable sequences of maximal entropy (no identifiable pattern). Even perfectly well defined sequences can be effectively random. E.g. if you started listing the digits of pi, beginning with the 100 trillionth digit... the sequence would appear random to anyone who didn't realize the source of the info.
I think you are very close to answering your own question, Android. Take the example of the 100 trillionth digit of pi and work from there. For anyone who did not know the secret of how the random sequence was generated, it would appear "random". But in fact it is highly ordered. On the other hand if you came up with a random sequence of digits (of finite size) then you might think that it is not truly random because you recognize a sequence of digits from the decimal expansion of pi beginning with the 66,542,013,278,934th. So ultimately the question is an epistemological one rather than a metaphysical one. Of course there are metaphysical aspects in the generation of random numbers -- it would be difficult to argue against the fact that the last digit of the microsecond timer of reception of a gamma ray from the decay of U-238 was not properly random, for theoretical reasons.
Post by: CliffordK on 13/05/2013 06:21:32
to the some very long digit sequence. But there would be no shortage of irrational numbers that one could calculate to a long digit sequence. Perhaps a bit more complex if one wanted multi-digit numbers, although I suppose with zeros in the sequence, one could just say take 10 digit blocks from your decimal expansion of your favorite irrational number. Now, the original question was:
"How can we prove that a number's really random?"
There is no random test for a single number.
I've heard a single random number be compared to an uninteresting number.
Say you wanted to find the first uninteresting number between 0 and 1000.
Certainly one would exclude 0, 1, 2, & 3.
Perhaps exclude all prime numbers.
Exclude all multiples of 5 & 10.
Also exclude multiples of 11.
Anyway, once you find the first uninteresting number....
Well, being the first uninteresting number is something, isn't it?
Better exclude that one too.
As far as random numbers, the number ONE could be just as valid of a random number as any other number in the range. The only way to demonstrate randomness then would be with a sequence, and not a specific number. And, if you exclude certain numbers because they just don't look random, then you are introducing a bias into the system, something that could be very bad with something like the lottery.
Post by: dlorde on 13/05/2013 14:36:46
Anyway, once you find the first uninteresting number....That way, we end up with no uninteresting numbers at all, which is interesting... ;)
Well, being the first uninteresting number is something, isn't it?
Better exclude that one too.
Post by: confusious says on 14/05/2013 21:20:00
Post by: dlorde on 14/05/2013 21:44:41
You cannot prove that a number is really random, if someone picks out a numbered card from a pack, that is not random, because whoever shuffled the pack, left them in a certain order, however chaotic, and the person picking out a card does this in some kind of order, wether it be the top, the bottom, the middle or somewhere inbetween. A computer cannot randomly select a number, because it has to start it's next random shuffle from a set point, which is the point it stopped at on the previous random selection. I suppose the more random tries before a random selection might allow you to gaining a more random number, but in reality it is still not random.You could equally well say that since a random number can take any value, all the methods you mention give as-good-as-random numbers.
Which suggests that randomness is more to do with sequences. There's no way to tell one number is random, but you can estimate the probability of a sequence being random by looking at value frequency, distribution, etc. People seem to be poor intuitive judges of of it, preferring homogeneity over the sequences and duplications of genuine randomness (see Perceived & Real Randomness (http://www.learner.org/courses/learningmath/data/pdfs/session6/numbers.pdf)).
Post by: confusious says on 16/05/2013 11:50:48
Post by: dlorde on 16/05/2013 15:28:36
What're we like, eh?
Post by: chris on 17/05/2013 09:10:17
I played this on 702 / 567 CapeTalk in South Africa this morning, and we've published it as a "specials" podcast out today - http://www.thenakedscientists.com/HTML/podcasts/specials/show/20130517/
Chris
Post by: AndroidNeox on 24/06/2013 00:36:55
So ultimately the question is an epistemological one rather than a metaphysical one.
Isn't metaphysics concerned with the nature of causality? If reality is perfectly causal then there are no random numbers... merely unpredictable sequences.
Post by: damocles on 24/06/2013 03:32:26
So ultimately the question is an epistemological one rather than a metaphysical one.
Isn't metaphysics concerned with the nature of causality? If reality is perfectly causal then there are no random numbers... merely unpredictable sequences.
If by "perfectly causal" you mean that physical laws may only be definitive rather than probabilistic, then you are quite correct. You are, however, flying in the face of the usual Copenhagen view of quantum theory. I guess that in interpreting it as an epistemological question my emphasis was more on the word "unpredictable".
Post by: AndroidNeox on 24/06/2013 20:06:29
It's probably time we discard the Copenhagen Interpretation. Quantum mechanics is our first scientific theory developed without any physical model. It's was intended as a means to calculate the probability of observing a specific outcome. To get that, the result had to be normalized, forced to to yield a probability. I have often wondered if the pre-normalized result describes populations of outcomes rather than probability of one outcome.
All the problems/weirdness of QM and its incompatibility with relativity can be eliminated by multiverse cosmologies. They explain all the observations of QM in terms of local processes... no instantaneous effects over distance.