How Random is REALLY Random
Statuary Warning : Long and Technical entry..
Random is a beautiful word and randomness, a strikingly beautiful concept. The most intriguing thing about” randomness” is probably that it is virtually impossible to generate something TRUELY random ourselves or by a computer program
(However this line of thought is debatable), the reason being we have ‘Memory’ and so do most of our modern day computers (They are something called ‘State Machines’ which again can be memory-less but in general are not so.). To be able to generate truly random sequences, we have to be ‘memory-less’, that is we should be ignorant of what we did at a time just before now! Sure there are random sequence generator programs, but when I say random I mean “REALLY random”. Before this article goes any further, I believe its best I define ‘random’. Specifically I will define “Random Numbers” since that’s the prime focus of this article.
Two often quoted definitions are one due to J. M. Franklin which says – “A sequence of numbers is random if it has every property that is shared by all infinite sequences of independent samples of random variables from the uniform distribution” and the other credited to D. H. Lehmer which goes the following way – “ A random sequence is a vague notion embodying the ideas of a sequence in which each term is unpredictable to the uninitiated and whose digits pass a certain number of tests, traditional with statisticians and depending somewhat on the uses to which the sequence is to be put.” The above two definitions don’t obviously mean the same thing. However the second definition appears to be a rather practical definition in that it means that the random numbers that are practically used in communication and information theory need only be approximately random in the domain over which they are used. A sequence satisfying the first definition is a lot harder to generate ( I call it harder because I don’t like the word impossible).
Before I commit the heresy of making this all too abstract let me give you an example of a sequence a layman would probably generate if asked to generate a sequence of random numbers involving only 1s and 0s –
110010010110010001101010011010010101101100
110111010010011010011011001101011001110010
010100010101010101011001001011001001
It probably looks good but fact is that the above sequence is far from random. In fact it can be shown mathematically that the sequence written above fails miserably when tests are conducted. For instance it can be shown that the probability of getting a sequence of consecutive 1s or 0s in a sequence of 120 bits is a surprising 0.9865 ( ~1 ) ! Likewise the probability of getting random numbers having less than 3 or more consecutive bits of same type is just 0.000053!
A more acceptable sequence would be –
111000111010111111101000110011010100111010
011101000010111011001110110011111101101011
100000000110111011110111101011011010
People tend to put bits looking at what they have written previously and tend to put a 0 for every 1 since that’s what appears to be intuitively right. But intuition fails in domains we have never been to. Intuition cannot tell you how to move or eat in space unless you have seen it. Intuition cannot imagine how things work in the submicroscopic domain unless you are a physicist. Similarly intuition cannot really tell you what really a random sequence is unless you study it.
Mathematically a very simple test for randomness is the correlation function. Any correlation with another random sequence should give you a zero. Practical algorithms like Lehmer’s Algorithm (nth term = (n-1) th term mod (m))use the modulus function to generate RNs. However they are periodic functions that repeat after some interval, ‘m’ in the example given above. Making the interval larger makes the sequence tend towards being more and more random. But to be truly random this interval has to be the unattainable infinity!!
For instance it will give us a very good random sequence if we ask a crowd of people to just say 1 or 0 as they wish and record what they say. Even here it will give us a better result if we make sure that no one hears what the others said! One simple way of generating a random sequence is to toss a coin and record the heads and tails as they appear. However if the generator involves anyone or anything that has memory then, my friends, generating a random sequence is going to be hard (again I say hard because I don’t like the word impossible).
So I ask again - How random is REALLY random?
My answer : Oh, really RANDOM
Random is a beautiful word and randomness, a strikingly beautiful concept. The most intriguing thing about” randomness” is probably that it is virtually impossible to generate something TRUELY random ourselves or by a computer program
(However this line of thought is debatable), the reason being we have ‘Memory’ and so do most of our modern day computers (They are something called ‘State Machines’ which again can be memory-less but in general are not so.). To be able to generate truly random sequences, we have to be ‘memory-less’, that is we should be ignorant of what we did at a time just before now! Sure there are random sequence generator programs, but when I say random I mean “REALLY random”. Before this article goes any further, I believe its best I define ‘random’. Specifically I will define “Random Numbers” since that’s the prime focus of this article.
Two often quoted definitions are one due to J. M. Franklin which says – “A sequence of numbers is random if it has every property that is shared by all infinite sequences of independent samples of random variables from the uniform distribution” and the other credited to D. H. Lehmer which goes the following way – “ A random sequence is a vague notion embodying the ideas of a sequence in which each term is unpredictable to the uninitiated and whose digits pass a certain number of tests, traditional with statisticians and depending somewhat on the uses to which the sequence is to be put.” The above two definitions don’t obviously mean the same thing. However the second definition appears to be a rather practical definition in that it means that the random numbers that are practically used in communication and information theory need only be approximately random in the domain over which they are used. A sequence satisfying the first definition is a lot harder to generate ( I call it harder because I don’t like the word impossible).
Before I commit the heresy of making this all too abstract let me give you an example of a sequence a layman would probably generate if asked to generate a sequence of random numbers involving only 1s and 0s –
110010010110010001101010011010010101101100
110111010010011010011011001101011001110010
010100010101010101011001001011001001
It probably looks good but fact is that the above sequence is far from random. In fact it can be shown mathematically that the sequence written above fails miserably when tests are conducted. For instance it can be shown that the probability of getting a sequence of consecutive 1s or 0s in a sequence of 120 bits is a surprising 0.9865 ( ~1 ) ! Likewise the probability of getting random numbers having less than 3 or more consecutive bits of same type is just 0.000053!
A more acceptable sequence would be –
111000111010111111101000110011010100111010
011101000010111011001110110011111101101011
100000000110111011110111101011011010
People tend to put bits looking at what they have written previously and tend to put a 0 for every 1 since that’s what appears to be intuitively right. But intuition fails in domains we have never been to. Intuition cannot tell you how to move or eat in space unless you have seen it. Intuition cannot imagine how things work in the submicroscopic domain unless you are a physicist. Similarly intuition cannot really tell you what really a random sequence is unless you study it.
Mathematically a very simple test for randomness is the correlation function. Any correlation with another random sequence should give you a zero. Practical algorithms like Lehmer’s Algorithm (nth term = (n-1) th term mod (m))use the modulus function to generate RNs. However they are periodic functions that repeat after some interval, ‘m’ in the example given above. Making the interval larger makes the sequence tend towards being more and more random. But to be truly random this interval has to be the unattainable infinity!!
For instance it will give us a very good random sequence if we ask a crowd of people to just say 1 or 0 as they wish and record what they say. Even here it will give us a better result if we make sure that no one hears what the others said! One simple way of generating a random sequence is to toss a coin and record the heads and tails as they appear. However if the generator involves anyone or anything that has memory then, my friends, generating a random sequence is going to be hard (again I say hard because I don’t like the word impossible).
So I ask again - How random is REALLY random?
My answer : Oh, really RANDOM
Comments
Post a Comment