True Random Number Generator Functions?
“Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin.” — John Von Neumann
Random means unfamiliar or unspecified. We use this word to describe unidentified people, unintentional incidents etc. Random number sequences act a vital role in many areas of science. Talking about random number sequences, what is truly random? Cant we really predict the next number of a or cant we calculate what might have been the next number? It’s not that simple. Once I started studying these methods of generation of random numbers, I found a large number of published papers and sites dedicated to this area of study. In the history of computer science and Mathematics scientists have build hundreds of random number generators. But still they are not unpredictable.
Random number sequences are frequently used in art, statistics, gaming, cryptography, gambling, politics, lottery services, simulations etc. These use have different levels of complexity. Computers normally cannot generate truly random numbers, but frequently are used to generate sequences of pseudo-random numbers. There are two principal methods used to generate random numbers.
- One measures some physical phenomenon that is expected to be random and then compensates for possible biases in the measurement process. (Hardware (true) random number generators (TRNGs))
- The other uses computational algorithms that produce long sequences of apparently random numbers called pseudo-random (Pseudorandom number generators (PRNGs)).
Source- ( Senthilnath, Ankur raj, S.N. Omkar, V. Mani, Deepak kumar.: Quasi-based hierarchical clustering for land cover mapping using satellite images (2013))
There are 2 main sub methods of the second type of randomization as Pseudo-Randomization and Quasi-Randomization because different applications require different levels of restrictions. For example, applications in cryptography have higher restrictions than choosing the word of the day in a dictionary app.
About two years ago I stumbled upon something interesting in a PDF which was written about learning python by creating simple games. From that point onward it caught my interest and I searched about that from time to time. It was about how random the random functions really are in programming languages. As an example the “randi” we use function in matlab, or “random.rand()” in python.
Even though we use the random functions in these languages to generate random numbers in programs they are not truly random. They are also functions and there’s a well optimized mechanism(formula) to generate these random numbers; yet still being somewhat predictable if you know what’s behind the function. This kind of random number generation is called “Pseudo-Randomization” and PRNGs (Pseudo random number generator) are used. These type of predictions are good enough for most computational applications.
PRNGs
Pseudo-Randomization
A pseudo-random process is a process that appears to be random but is not. Pseudo-random sequences typically exhibit statistically randomness while being generated by an entirely deterministic casual process. These are generated by some algorithm, but appear for all practical purposes to be random. A common pseudo-random number generation technique is called the linear congruential method . The pseudo-random numbers are generated using following equation.
A_n is the previous pseudo number/Z -a constant multiplier/I - a constant increment/M - a constant modulus. These Random Numbers tend to have Higher discrepancy.
Discrepancy is the property of measure of the uniformity in a point for the distribution; mainly for the multi-dimensional case.
Quasi-Randomization
The quasi-random numbers have the low-discrepancy property that is a measure of uniformity for the distribution of the point mainly for the multi-dimensional case. The main advantage of quasi-random sequence in comparison to pseudo-random sequence is it distributes evenly hence there is no larger gaps and no cluster formation, this leads to spread the number over the entire region. The concept of low-discrepancy is associated with the property that the successive numbers are added in a position as away as possible from the other numbers that is, avoiding clustering (grouping of numbers close to each other). The most fundamental LD sequence for one dimension is generated by Van der corput method, further to continue random sequence in higher dimension Faure and Halton methods are used.
Fig-1 shows the distribution of 100 particle in the search space of [-2,2]. Two dimensional Faure sequence has been taken for quasi-random number. It can be seen that in Fig-1a quasi sequence is very uniformly distributed in space (each grid has at-least one point) whereas pseudo sequence as shown in Fig1b which is generated by matlab random number generator (rand() function) is not very uniform.
Now when you observe these two images you should identify that even though quasi-randomization has low discrepancy it looks less random. I found a document on this issue posted by matlab.
“ In certain circumstances, the common methods of random number generation are inadequate to produce the desired samples. Statistics and Machine Learning Toolbox™ offers several alternative methods to generate pseudorandom and quasirandom numbers. Quasirandom numbers, also known as low discrepancy sequences, generate each successive number as far away as possible from existing numbers in the set. This approach avoids clustering and can speed up convergence, but quasirandom numbers are generally too uniform to pass randomness tests. Pseudorandom numbers are less uniform than quasirandom numbers and may be more appropriate for applications that require greater randomness. Use the slice sampler, the Hamiltonian Monte Carlo sampler, or the Metropolis-Hastings Markov chain sampler to generate pseudorandom samples by drawing from a statistical distribution.
If the available parametric probability distributions do not adequately describe your data, you can use a flexible distribution family instead. The Pearson and Johnson flexible distribution families fit a model based on the location, scale, skewness, and kurtosis of the sample data. Once you fit a distribution to your data, you can generate pseudorandom numbers from that distribution.”
Vast number of researches have been done on these algorithms and Monte Carlo Algorithm, Karger-Stein Algorithm, Randomized algorithm are some of those most famous random number generating algorithms. Some other approaches combine a pseudo-random number generator with an external source of randomness such as mouse movements, delay between keyboard presses etc. Examples —
- CryptGenRandom — Microsoft Windows
- Intel RdRand instructions (available in Intel x86 CPUs since 2012 /AES generator built into the CPU)
- Yarrow
- Fortuna
- /dev/random — Linux and Unix
- True Random Number Generator using Corona Discharge.
For almost all practical applications this system works perfectly well, but since it’s a predictable system it isn’t truly random.
TRNGs
A hardware (true) random number generator is a piece of electronics that plugs into a computer and produces genuine random numbers as opposed to the pseudo-random numbers that are produced by a computer program. The usual method is to amplify noise generated by a resistor (Johnson noise) or a semi-conductor diode and feed this to a comparator or Schmitt trigger. If you sample the output (not too quickly) you (hope to) get a series of bits which are statistically independent. These can be assembled into bytes, integers or floating point numbers as expected by the user. A lot of research and tests have been done on these hardware (true) random number generators and I expect to write a separate article on those later in future.
Random Number Servers
Out of all these methods mentioned above these sites on the internet are the only groups who claim that they can generate true random numbers! For this task they use random and deterministic process in the nature and calculate the numbers with measurements and threshold values. The following are some of the most interesting sites which deliver additional randomization services.
HotBits
“Given knowledge of the algorithm used to create the numbers and its internal state, you can predict all the numbers returned by subsequent calls to the algorithm, whereas with genuinely random numbers, knowledge of one number or an arbitrarily long sequence of numbers is of no use whatsoever in predicting the next number to be generated…HotBits is an Internet resource that brings genuine random numbers, generated by a process fundamentally governed by the inherent uncertainty in the quantum mechanical laws of nature, directly to your computer in a variety of forms. HotBits are generated by timing successive pairs of radioactive decays detected by a Geiger-Müller tube interfaced to a computer. “ ( Source- fourmilab)
Australian National University
“This website offers true random numbers to anyone on the internet. The random numbers are generated in real-time in our lab by measuring the quantum fluctuations of the vacuum. The vacuum is described very differently in the quantum mechanical context than in the classical context… By carefully measuring these fluctuations, we are able to generate ultra-high bandwidth random numbers.” (Source- Australian National University)
Random.org
“Perhaps you have wondered how predictable machines like computers can generate randomness. In reality, most random numbers used in computer programs are pseudo-random, which means they are generated in a predictable fashion using a mathematical formula. This is fine for many purposes, but it may not be random in the way you expect if you’re used to dice rolls and lottery drawings. RANDOM.ORG offers true random numbers to anyone on the Internet. The randomness comes from atmospheric noise, which for many purposes is better than the pseudo-random number algorithms typically used in computer programs.” (Source- random.org)
Out of these 3 sites hotbits & ANU site seems to give true random numbers whereas the randomness of random.org is very high compared to PRNGs. But still if you have the immense amount of data of atmosphetic noise, you can predict the number by calculations because they use atmospheric noise as the measurement for the calculation of these numbers. As you can see even though random.org does supply random numbers in a higher accuracy it’s still predictable if you are given the accurate weather and other necessary data. But it is not practical to pre-predict the numbers even with the adequate data. So we can consider numbers generated by random.org to be truly random. There are several Random.org radios located in Copenhagen, Dublin, and Ballsbridge, each generating 3,000 bits per second from the atmospheric noise picked up. The generators produce a continuous string of random bits which are converted into the form requested.
Hotbits & ANU are absolutely non-deterministic processes therefore we can say that true random number generation is possible! Apparently they can be generated by measuring using the natural and unpredictable behaviors in nature such as radioactive decay & quantum fluctuations. But still we can only assume that these are truly random because it is theoretically impossible to prove that a random number generator is really random.
Quantum Computing
With the revolution of quantum computing the fuss about true randomness will come to an end because Generation of true random numbers is a feature of even the most primitive quantum computers, today, which cannot be matched by any classical computer, today, or ever. I’ll leave link below if you’re further interested.
(Read more — Programming a quantum computer: generating true random numbers)
Talking about predictability, there’s an interesting book I read when I was in high school about developing formulas for abstract number sequences by renowned Mathematician Dr. W. Ramasinghe. (BSc (Mathematics) Hons(Colombo), PhD( Ohio State University). Senior Lecturer,. Department of Mathematics,. University of Colombo.)
If possible try to read his books. They consist of mathematical knowledge which will change the way you look at this world. His books gave me a whole new insight about the world of mathematics & how to look at the world in a mathematical eye. In that particular book he describes that we can not predict the next value of a sequence easily. But he also proves that it is possible to develop a formula which gives out any random sequence of numbers. That is the most important thing to be extracted from that book. The more arbitrary the number sequence, the better the results of the formula. If we were to write a whole new library or a function to generate random functions this method can be used with great precision! According to Dr. Ramasinghes work, it’s possible to create a formula for any number sequence one might come up with, regardless of the numbers are float, positive int, negative int. It’s a very interesting concept which I used to pondered upon during my high school years. But still, Dr. Ramasinghes work doesn’t tell that we can predict any random number, it only tells us how it could have been predicted after its been put out as the result!
This whole article was about a simple function which we use in coding without putting much thought into that. Now think about what we could learn from that simple function. It truly shows the beauty of mathematical modeling. Mathematics isn’t called the queen of science for nothing. All science ms depend and nurture from mathematics. Without mathematical modeling any of the software, hardware developments could not have happened. Just like that each and everything we learn has its own beauty inside. There’s no such thing as boring subjects. You just have to make it interesting by going after the little things which makes up the big things. Once you go beyond whats being taught inside the classroom, you’ll find a sea of knowledge waiting for you to dive and explore!
