Randomness is a fascinating and yet often misunderstood concept. It seems so simple yet has an incredible degree of complexity both in its capture and in its application. Randomness comes into many aspects of our lives from stock markets and house prices to gambling and opinion polls, drug trials and weather to sickness and health. It also plays in integral role in the security on the net and makes activities like internet banking and privacy.
Randomness in the form of stochastic resonance is utilised by animals to improve the senses at the very limits of our perception. Almost counter intuitively, random signals are added to our vision, touch and hearing which actually improves our ability to detect very faint inputs.
Yet with all this randomness going on in and around us, we humans are notoriously bad at being random and are poor judges of randomness when we see it. This effect is amplified when explicitly asked; a foible employed by magician in the “Think of a number” routine and also demonstrated very effectively in the pilot episode of Numb3rs where Charlie asked a roomful of people to distribute themselves randomly only to watch them all arrange themselves evenly.
Randomness is a very rich subject and in this blog I hope to uncover some of its beauty and tricks and also some of the ways we have come to use it in our modern lives.
Part 1: What’s it all about?
What is Randomness?
The Oxford English Dictionary defines random as “Having no definite aim or purpose; not sent or guided in a particular direction; made, done, occurring, etc., without method or conscious choice; haphazard.”
A central concept of randomness is the inability to predict its detail. Some common random devices like dice, coins and roulette wheels are good sources of random as it is extremely difficult to work out in advance what the outcomes will be if they are used correctly. All that is generally required from a good random device is that each possible outcome from the device should have an equal probability and the probabilities of future outcomes should not depend on earlier ones.
This notion of independence is often a cause of confusion; if a fair coin throws heads ten times in a row, it is an all too human tendency to think that the odds of tails should be higher so that the coin can obey the law of averages but this is a fallacy. The coin knows of no such law and will land with a 50% chance of heads without fail. This is commonly referred to as the gambler’s fallacy after the tendency of gamblers who have had a run of losses, to continue gambling based on the belief that a big win must be just around the corner, the longer the run of losses, the greater the imagined likelihood of a turn of luck.
True randomness is not actually measurable. There is no test you can apply to accurately determine true randomness – it’s just not possible. The problem is; since every value in a random sequence has an equal probability then every possible sequence that can be imagined is a potential output from a random number generator. Even a sequence containing the number 1 repeated every time is potentially random – imagine rolling a dice and getting a 1 every time, it’s highly unlikely but it is possible.
There do exist so called “tests for randomness” that analyse the values in a sequence and give a score on how erratic the values are but what these tests are measuring is not true randomness but statistical properties associated with randomness like an even distribution of values, non repetitiveness and so on.
Entropy
You can’t look far into randomness without encountering entropy.
The term “entropy” is used as a measure of the uncertainty of random values. The entropy of a value is typically related to two things: the range – how many potential states the value could have – and how predictable the particular state of the value is.
Entropy is measured in bits and the entropy value is calculated as the number of bits required to describe a value in a sequence. For example a fair coin where each throw has an equal chance of heads or tails will require 1 bit for each throw. On the other hand, a four sided die throw will have entropy of 2 bits since 2 bits are required to reliably store all the possible outcomes from the four sided die. Similarly an eight sided die throw will have 3 bits of entropy.
Unlike normal “traditional” bits, the bits used in entropy can have fractional values. Take a six sided die throw. It has fewer potential outcomes than the eight sided die but more than that of a four sided one. So how many bits of entropy do you get from a six sided die? The answer is based on the powers of two. For example: with the eight sided die, the answer – x – comes from solving 2x = 8. Turning this equation around results in x = log2(8) giving us x = 3. Similarly with the four sided die log2(4) = 2, so for the six sided die, the number of bits of entropy per throw is simply log2(6) which gives us approximately 2.58.
Entropy is cumulative, or in other words, it can be added together. If throwing one six sided die gives 2.58 bits of entropy, throwing a second will increase the total to 5.17 bits and so on. This is useful when a certain quantity of entropy is needed for some purpose; entropy can be gathered from multiple sources – for example mouse movements, keyboard presses, network traffic or even accelerometer and magnetometer readings in modern mobile phones – and then merged together to reach the required total.
TL;DR
- Randomness is all about unpredictability
- True random has no memory of past throws or values
- Entropy is a unit of randomness
- Entropy is measured in bits but can also come in fractions
Upcoming Topics
- Sources of Randomness
- More on Entropy
- RNG vs PRNG
- Tests for Randomness
- Security Basics
- Hashes vs Ciphers
- Cracking Passwords
- Securing Passwords
- HTTPS
- Humans and Randomness
I’m currently working with Jason Roberts on a new startup – AppIgnite, a web tool that creates data-driven web apps in minutes instead of months. We’re recruiting beta testers right now, if you’d like to participate or just like to learn more, then please leave your email address here and you’ll hear from us when we launch!
