A Random(ness) Post

Does randomness exist?  It sounds like a pretty straight forward question.  Is there an easier task that I could challenge you with than, say for example, to ask you for a random date?

Is a human better at imagining something random than a computer?  In providing my opinion in answer to this question I will discuss a few computer science concepts and do a hatchet-job on human psychology. ;-)

Randomness in computers

First let’s consider what randomness means to a computer. I’ve been thinking about the concept of computational “randomness” for quite a long time.  It all started with cryptography, you see, I’m quite interested in the maths behind it all (but not that interested that I would sign-up for a course in number theory – that would be punishment) and also the concepts behind non-computational cyphers.  So for years I have read about cyphers, cryptanalysis and secure keys.

One of the greatest weaknesses in computer-based cryptographic systems is the quality of the random numbers which are generated and form the keys for the securing of data.  If there is even the slightest hint towards the possible next “random” number that the computer generates, then the cryptography is substantially weakened.  As an example; the SSL component of Netscape was cracked in 1995 by exploiting the poor quality of the random numbers.

So what’s the big deal?  Why can’t a computer just give a random number when you ask for one?  The answer here lies at the lowest level of the computer.  A computer is hardwired to perform a finite number of mathematical functions, these mathematical functions always have a correct answer and we know that for all possible inputs there is an equal number of possible outputs, these are the correct answers.  So what is the “correct answer” when we ask for a random number?  To overcome this problem, computers can have software-based PRNGs (Pseudo-random number generators) or hardware-based RNGs (Random number generators).

Software PRNGs will use one of two techniques;

  • Software maintained entropy pools.  Operating systems keep a pool of select information gathered about the state of the computer while it is running and provide numbers from this stream of unrelated data.  For example; the Linux operating system has a software device called “/dev/random” which provides software developers with a place to find a stream of pseudo-random digits at any time.  The operating system constantly feeds information about the computer and the user’s activity (such as the mouse position and keys pressed) back into the entropy pool.
  • “Converting” a rather normal, non-random number to a pseudo-random number.  There are many examples of this as it has been the most commonly used technique for generating PRNs.  The quality of the PRN is based on how much information was fed into the algorithm.  As an example which we can all do with a pen or calculator, suppose that we want a PRN between zero and one and our computer uses as input for our algorithm the number of milliseconds which have passed since the computer was turned on.  In my case, right now as I write this, the input is approximately 85 221 250 (give or take 300 000).  We can convert it to a number between negative 1 and positive 1 (inclusive of both) if we use the Sine function, so no mater how large or how small the input number the output will always be between -1 and 1.  Further, if we want to eliminate the negatives (because we want a number between 0 and 1) we can take the absolute value of the result.  For our earlier example, my “random” number is 0,9396926208 (rounded to 10 decimal places).  At the end of writing this section, the “random” number for 85 816 127 was 0,7313537016 (rounded to 10 decimal places).  This method I have described (using the Sine function) is extremely insecure, even if you increase the variety of input data, but I won’t go into that now.

Software PRNGs, therefore, cannot be seen as truly random in the usual sense of the word.  The number that you get is calculated, determined, not imagined.

Hardware Random Number Generators will use techniques of gathering entropy from the real-world environment (perhaps measuring the exact temperature of the CPU, the decay of a radioactive material, the wind-speed outside, the radio frequency noise of the world around the device or whatever).  The information is combined at the moment that it is requested to generate a “random” number.  The result is added back into the entropy to form part of the randomness for the next number.  It is a fixed logic that is used so the computer still always generates a “correct” answer.  But I am sure that you can see the problem here, the number – in real terms – is not completely and independently random.  The computer is influenced by the world in deciding the next number.

Asking a computer for a truly random number is impossible, however, these computational methods can provide very high quality pseudo-random numbers.  Is the situation any better for human beings?

Randomness in humans

“Well, that’s easy,” you might say, “humans have free will, so of course we generate better random numbers than computers”.  Not so fast there sunshine, I’ll get to the problem with free will in a moment but first I will make a bit of a prediction.  Take a look at the following …

Now, what I want you to do is not let that number influence you, but I want you to look at the box below and imagine a random positive whole number which is 100 or lower inside that box …

My prediction is that the task involved a little difficulty, that by showing you the eighteen first that you had to carefully think about the number you finally settled-on.  If you did think about it carefully then it is likely that you briefly looked down and to the left while you were thinking through a few options.  If you were thinking for a long time then you might have looked straight up for a longer period, or you actively searched for entropy in your peripheral field of view, but I digress.  Finally you settled on a number that you feel was sufficiently unrelated to eighteen to be a “better” random number.

I won’t be predicting which number you chose but I would like you to think about how you got there.  Ultimately the number you chose actually was related to eighteen, the reason is that you were specifically trying to avoid it and each failed option that you considered had some (personal) mental link to eighteen or to the previous possibility (perhaps it was “too obvious”) that meant that you were not comfortable with the other possibilities.  Each possibility was either drawn from the environment around you (when you looked down and left) or each failed possible number links to the next one that you considered, even if you are not consciously aware of the relationship.  But my question is why you avoided eighteen?  Eighteen is a valid number according to the rules (a positive number equal to~ or less than 100) so why did you avoid it?  If you were using your own mental random number generator in a cryptography situation then the hint that you are probably not going to select eighteen is helpful (if only slightly) in cracking the encryption.

The numbers that you will choose will be based on your current state of mind and the events that have recently occurred that you might not be consciously aware of.  For example; I asked a rhetorical question at the beginning about posing a question to you asking for a random date, I didn’t ask you to provide a date, but you can’t say for certain that the question did not have an impact on the later question about the random number.  At the time that you read the rhetorical question a few dates may have flicked through your head such as an upcoming birthday or an anniversary.  It is these subtle manipulations of your conscious thoughts (poluting the randomness pool) that mentalist magicians utilise to perform their tricks, so it will work when you are asked to think of a card and when you announce “Jack of Diamonds” the curtains behind you reveal a giant playing card with your “random” choice.

As for the idea that free will guarantees that humans can produce better random numbers, it is not true because free will is largely an illusion.  The reason that philosophers and psychologists think that free will is largely an illusion is the experiment from the 1970s which Benjamin Libet performed and has since been repeated.  If you have not read about this experiment then I recommend the NY Times article by Dennis Overby as a brilliant introduction to the experiment and the implications.  I fear that if I start to write about this topic then I would add another 1000 words to an already excessively long post.

So computers may be bad at generating random data, but humans may actually be far worse at the task.  We too cannot select a truly random number and the quality of our pseudo-random numbers is far lower than that of computers.

Are you saying that randomness doesn’t exist?

No, that is not at all what I am saying. Quantum mechanics is all about the randomness (uncertainty). Even if you compare this with Classical physics (which posits that everything is predictable because if the states of all matter and energy in the universe is known then the next moment is predictable, and so is the next moment after that, and so on – i.e. no room for randomness), there are concepts which are indeterminate and must be labelled as “random”. This brilliant example comes from a comment left by “ebaines” on a forum discussing this same topic:

Think about this experiment that shows how randomness is present in every day life – suppose you line up 10 billiard balls, with each ball separated 1 meter from the next. Using a cue ball, is it possible to hit the first ball into the second, so that the second hits the third, the third hits the fourth, and so on for all ten balls? It sounds simple enough – just a very good combination shot. But if you do the math you’ll see that any error in the way two balls collide is magnified by about a factor of 30 when the next ball is hit. So for ten balls any initial error is magnified by 30^10, which is about 6 x 10^15. Stated another way, the initial hit would have to be accurate to better than 5×10^-15 cm. To achieve this level of accuracy the balls would need to be smoother than atomic structure allows. At this level the Heisenberg Uncertainty Principle sets in. So it’s impossible to predict exactly what will happen to the 10 [balls] – the end result is random.

About these ads

~ by James on 4 October 2008.

2 Responses to “A Random(ness) Post”

  1. VERY interesting post, and easy to read. It’s great to read something and learn from it. Well done.:-)

  2. Glad to hear you found it interesting.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
Follow

Get every new post delivered to your Inbox.

%d bloggers like this: