Jan 02 2012

Randomness

One concept that is important to being a scientist or critical thinker is that terms need to be defined precisely and unambiguously. Words are ideas and ideas can be sharp or fuzzy – fuzzy ideas lead to fuzzy thinking. An obstacle to using language precisely is that words often have multiple definitions, and many words that have a specific technical definition also have a colloquial use that is different than the technical use, or at least not as precise.

Recently on the SGU we talked about randomness, a concept that can use more exploration than we had time for on the show. The term “random” has a colloquial use – it is often used to mean a non-sequitur, or something that is out of context. It is also used colloquially in the mathematical sense, as a sequence or arrangement that does not have any apparent or actual pattern. However, people have a  generally poor naive sense about what is random, mathematically speaking.

There are at least two specific technical definitions of the term random I want to discuss. The first is mathematical randomness. Here there is a specific operational definition; a random sequence of numbers is one in which every digit has a statistically equal chance of occurring at any position. That’s pretty straightforward. This operation can be applied to many sequences to see if they conform to a statistically random sequence. Gambling is one such application. The sequence of numbers that come up at the roulette table, for example, should be mathematically random. No one number should come up more often than any other (over a sufficiently large sample size), and there should be no pattern to the sequence. Every number should have an equal chance of appearing at any time. Otherwise players would be able to take advantage of the non-randomness to increased their odds of winning.

Computer simulations are another area where a truly random sequence of numbers is valuable.  Random numbers may provide the input necessary for the simulation to run.

It is very difficult (perhaps impossible) for a person to generate a truly random sequence of numbers from their brain. Here are three sequences of numbers, try to find the one that is mathematically random:

0 4 4 7 2 0 6 0 2 3 8 9 9 3 0 2 0 5 3 3 8 6 8 4 9 3 3 8 9 2 4 2 2 1 3 6 4 7 9 7 4 0 2 4 9 9 3 4 5 0

9 4 8 5 7 6 0 9 4 7 3 6 5 2 9 1 7 3 5 7 8 5 4 8 0 2 9 3 8 7 5 1 0 2 5 2 3 5 5 5 0 2 9 8 9 7 7 2 0 3

8 5 5 7 0 3 0 9 2 9 9 2 8 4 7 5 6 6 2 0 3 9 4 8 7 5 0 3 0 9 4 8 7 5 0 3 0 3 8 4 7 5 9 8 7 7 0 3 9 8

The top sequence was generated by a random number generator, the bottom two I produced by typing chaotically (I won’t say “randomly”) on my number pad. The top sequence is statistically random, while the bottom two are not. It’s hard to tell the difference just by looking. Also we tend to underestimate the clumpiness of randomness (called the clustering effect). So, for example, in a mathematically random sequence of numbers, the same digit should occur twice in a row with a certain frequency, and even three, four, five or more times in a row. But such clusters make the sequence look naively non-random.

The top number is what is called pseudo-random. As I said, random numbers are very useful to computer programmers. There are a number of operations that can generate mathematically random number sequences. But they are not truly random because the operation will generate the same sequence of numbers given the same input or seed. There therefore needs to be some way to create a random seed, which can be based upon some physically noisy process, or the time, or something else that changes regularly.

Another example of a pseudo-random sequence is pi. The number pi (3.1415926535897932384626433832795028841971693993751058209 7494459230781640628620899862803482534211706798214808651…) is a statistically random sequence of digits, but of course it is not truly random because it is one specific sequence.

This brings us to the second technical definition of random – true physical randomness. I can throw dice to generate a statistically random sequence of numbers, assuming the dice are fair and I am sufficiently “randomizing” each throw. But from a physical point of view, the result of each throw is not random, but determined by the laws of physics. The number that results on the die must occur given all the physical parameters of the throw. Once the die is cast, the number that will result is determined and not random. In this sense “random” also means “unpredictable.”

The only truly random physical system known to science results from quantum effects. Certain quantum properties are undetermined and unpredictable – they are truly random. In fact, researchers last year developed a random number generator based upon quantum properties – the first truly random number generator.

As with many concepts in science and elsewhere, even seemingly basic or simple concepts can become very detailed and complex when explored deeply. That is one lesson I have thoroughly learned from studying and teaching science  - it’s always more complicated than it seems. In fact, it’s always more complicated than your current understanding. The above discussion of randomness is a quick overview, but there are layers of complexity and detail I did not get into. There are also limits to our current understanding – the universe is more complicated than we know.

It is very helpful, however, to at least understand that there is likely more depth to an issue than one’s current knowledge. But we can still use terms and concepts that are accurate and precise as far as they go, even if there is always a deeper complexity.

Share

20 responses so far

20 Responses to “Randomness”

  1. Eric Thomsonon 02 Jan 2012 at 11:25 am

    Good topic, stepping back to a more general view, I’d add that randomness doesn’t necessarily mean equiprobable. The uniform distribution is just one family of probability distributions. E.g., a Gaussian process is also random.

    Also of interest is the definition of randomness in terms of the length of the computer program required to reproduce the sequence (Kolmogorov randomness). This often is about detecting, not generating, randomness. If the program is shorter than the sequence, then the sequence is not random.

    I used to be really into arguing about quantum mechanics, and whether the indeterminacy is in reality, or our limited knowledge of reality. Consensus has always leaned toward the former, but the latter still has Bohmian Mechanics to fall back upon.

  2. ChrisHon 02 Jan 2012 at 12:15 pm

    In my former life before I had to quit working due to having a baby with medical issues I was a structural dynamics and loads engineer dealing with random vibration. Though structures each have inherent natural frequencies, so there is a limit on how they would vibrate, doing a Fourier transform from the time to the frequency domain would pull out dominant frequencies (spectral frequency). Of course the forcing function (like road roughness) would be random, but within certain parameters.

    Oh, I have nothing to contribute. It just made me think that this is real problem that is part of your everyday life, from the shaky wheel on a shopping cart, the flutter of an airplane wing, the reaction of a building to an earthquake and everything that we think of is chaos. There is a statistical model in all of them.

  3. ChrisHon 02 Jan 2012 at 12:58 pm

    It occurred to me that there are several disciplines that work to find some kind of order in randomness. One of your former guests could talk about it in a future podcast, Seth Shostak. Since the radio signals received can be considered random, what do they do to find one that is “unnatural”, and what kind on natural patterns are found in what many of think of as white noise?

  4. Rikki-Tikki-Tavion 02 Jan 2012 at 1:10 pm

    I think the machine you describe is not the first truely random number generator. Others have been built based on atomic decay, which is also perfectly random (although not equally distributed).

    Like so: http://www.fourmilab.ch/hotbits/hardware3.html

  5. rfhickeyon 02 Jan 2012 at 2:47 pm

    I remember a professor of mine talking about randomness in the universe along a timeline leading from the big bang to the present moment. His point was that from the time that matter came into existence 14 billion years ago and the four fundamental forces as described by the Standard Model emerged, that everything since has been ‘determined’ and therefore not random. Going from the macro to the micro, this seemed like the dice example you give above (once they leave the gamblers hand being akin to the big bang and essentially any event afterwords being the time that the dice stop) or even the moment a life is conceived. These are essentially one and the same as these micro-events are simple part of the larger determinism in the universe. Everything that has happened since had to happen as they were governed by the physical laws and the initial properties of all particles in the universe . In such a view, everything is inevitable and randomness is only illusory. I make no claim to even begin to understand random quantum effects, or how it is shown that they are truly random. But the two ideas are, to me, hard to reconcile. Are we, or are we not completely at the mercy of these laws? Claiming that we are not, seems to me to be more like wishful thinking of the human ego than critical thinking/skepticism…

    Sorry if this post sounds like the rantings of a student in a Philosophy 101 class.

  6. mvoetmannon 02 Jan 2012 at 3:37 pm

    Your definition of mathematical randomness seems to be about digit frequency, rather than predictability or entropy. I think that is not quite precise. Some number sequencies may be predictable to some degree, even though the frequency of all numbers are the same.

    I am not aware that anyone has ever proven that the digits of pi are pseudorandom, ie. have no individual predictability. It seems plausible, but is there a proof ?

    As for physical random systems, if quantum level events are truly random, then arguably any chaotic large-scale physical system is also truly random, since the definition of a chaotic system is one where very small (unpredictable, quantum) effect quickly can change the state of the entire system significantly.

    Even if we don’t accept that quantum systems are truly random, there are other situations in physics, where we know that complete knowledge is impossible to get, and so they can be used to generate truly random data, data that we know that the laws of physics will not allow us to predict. For instance, in thermodynamics we know, that there can not be a creature such as Maxwell’s demon, with a full understanding of a heat system. Entropy makes it impossible. So thermodynamic events are in this sense somewhat unpredictable, and can be used as a source of true randomness.

  7. cwfongon 02 Jan 2012 at 4:13 pm

    Consider however that the randomness being described here always has a probability factor. True or complete randomness will not be found in a lawfully probabilistic universe.

  8. eeanon 03 Jan 2012 at 3:25 am

    @cwfong, erm but if you can ever find (for examples) two options with the same probability of occuring, then which of them actually occur is random.

  9. Steven Novellaon 03 Jan 2012 at 7:23 am

    mvoetmann – I wrote that mathematical randomness requires that any digit can occur at any position with equal frequency – that is about more than total digit frequency. It also requires the absence of pattern. I like what Eric said, that a random sequence also cannot be compressed, because there are no patterns.

    Also – chaos theory does involve extreme sensitivity to initial conditions, but that does not extend down to the quantum level. So even chaotic systems are not truly random in the quantum sense. Chaotic systems can still be classical.

    An unpredictable system can be used to generate pseudorandom results which are perfectly useful, but they are still not truly random.

  10. Murmuron 03 Jan 2012 at 10:49 am

    rfhickey – your comment got me thinking… strange to hear an actual scientific theory on how it may actually be that the die was cast for the universe the moment it was created. It is obviously something that cannot ever be proven or dis-proven as far as I can see. We would need two parallel universes, created at exactly the same time, at exactly the same spot in order to see if they would diverge or not.

    However, it does make you wonder, if what your professor is postulating is true, then true randomness cannot be possible, and this leads me to think that our concept of “choice” is actually a myth. And this actually would give some kind of scientific basis to the concept of “destiny”. Is the very thought process I am having now, and the act of typing these words something that were set in stone since the universe was born?

    The more I think about it, the more it makes sense, while it would be a massively complex formulation, it could be possible to predict just about anything… Maybe Asimov was on to something…

  11. Rikki-Tikki-Tavion 03 Jan 2012 at 10:54 am

    I beg to differ in some points:

    1. Randomness does not imply uniform distribution. There are plenty of other random distributions:
    http://en.wikipedia.org/wiki/Discrete_probability_distribution#Discrete_probability_distribution
    Also there is no rule, that random numbers cannot contain patterns. They only (usually) contain less patterns than non-random values. Whether they have patterns or not is independent of the question whether they are uniformly distributed.

    2. If the system is unpredictable, then the numbers it generates are by definition truly random. Where the randomness comes from has no bearing of whether something is random or not. Quantum phenomena are just useful, in that they are known to be perfectly unpredictable.

    I don’t know if maybe quantum effects can affect how solid objects bounce off each other. Do we have a physicist here, who can answer that?

  12. Rikki-Tikki-Tavion 03 Jan 2012 at 10:57 am

    @Murmur:

    Even if everything where in principle perfectly predictable, you couldn’t predict it (in real time or faster), because you would need a computer larger than the universe itself.

  13. ChrisHon 03 Jan 2012 at 11:26 am

    Dr. Novella:

    I wrote that mathematical randomness requires that any digit can occur at any position with equal frequency – that is about more than total digit frequency. It also requires the absence of pattern.

    If you made a bar graph of a numbers of times each number (0 to 9) showed up, the “spectral density” would be the same level across the graph. Each number would appear about the same number of times. But that would happen to a sequence of 01234567890123456789…. Which is not random.

    One would have to count the frequencies of all possible two number combinations, then three number combinations, etc. Until the the factorial sizes literally become ad infinitum. At that point I give up as it involves the kind of mathematics dealing with various kinds of infinity other than the engineering interpretations of “Okay, so even if you say one half step of the previous step does not get you there, there is a limit to this and you are there already!” (I like math, but I have my limits, especially when they involve infinite sets).

  14. cwfongon 03 Jan 2012 at 1:39 pm

    eeanon 03 Jan 2012 at 3:25 am
    *@cwfong, erm but if you can ever find (for examples) two options with the same probability of occuring, then which of them actually occur is random.*

    That comment makes no sense whatsoever. If two options had the same probability, the one that occurred would only offer evidence of the necessity for assigning probability, erm.

  15. jt512on 03 Jan 2012 at 3:19 pm

    Steve Novellawrote:

    [m]athematical randomness requires that any digit can occur at any position with equal frequency…

    I think you’ve got a problem if you’re trying to apply that definition to the digits of pi. In the frequentist sense, the probability of the ith digit in the decimal expansion of pi being one of the digits 0,1,…,9 is 1 for one of those digits and 0 for the rest. So it is clearly not the case that “any digit can occur in any position with equal frequency.”

    When mathematicians colloquially talk about whether the digits of an irrational number, like pi, are “random,” what they mean is that the number is a normal number. This essentially means that the long-run relative frequency of all finite sequences of digits of length n is the same, say p_n, for n=1,2,….

    And, since the question keeps coming up, it has not been proved that the digits of pi are random in the above sense; however, no statistical test performed on the digits of pi has provided any evidence that they aren’t.

    (Now, given that I can’t preview my post, what is the probability that all my HTML formatting is correct?)

  16. Nikolaon 03 Jan 2012 at 6:45 pm

    @Steven Novella on 03 Jan 2012 at 7:23 am

    Saying that random sequences cannot be compressed contradicts your earlier description of random sequences in the text (clustering), no?
    In fact, any random sequence (given enough length) should be compressible to some extent.

  17. Armcieon 03 Jan 2012 at 9:25 pm

    Shannon entropy is an interesting concept associated with randomness. Shannon entropy is a measure of the predictability of the next value in a sequence, given previous values, and is also described as a measure of information content. Returning to the discussion in the podcast, a totally random sequence has minimal entropy, providing a scale upon which things could be judged to be more, less or extremely random.

  18. mvoetmannon 04 Jan 2012 at 3:03 am

    @Steven Novella
    “I wrote that mathematical randomness requires that any digit can occur at any position with equal frequency – that is about more than total digit frequency. It also requires the absence of pattern. I like what Eric said, that a random sequence also cannot be compressed, because there are no patterns.”

    Yes, randomness is about more than digit frequency. And it is about more than pattern, too.
    If a number sequence has maximal mathemathical entropy (and consequently is uncompressable) it may or may not be random. There is no way to tell. All randomness-tests try to do is to find redundancy in a number sequence, but even when there is no redundancy, the sequence may still have a meaningful interpretation, and so be non-random. A number-sequence generated from a one-time pad is, for instance, not random. It contains information. But there is no way to tell it apart from a random sequence without knowing the key.

    “Also – chaos theory does involve extreme sensitivity to initial conditions, but that does not extend down to the quantum level. So even chaotic systems are not truly random in the quantum sense. Chaotic systems can still be classical.”

    Why do you think it does not extend to the quantum level? I know of no theoretical reason it should not.
    Obviously there is no way to determine this by experiment, but consider for instance the chaotic system of a ball jumping in a trench. Normally, in a computer, you just model this classically in a perfectly deterministic manner. But if you introduce an uncertainty of position at well below the Planck level (quantum level) in the model, it still affects the behaviour of the ball very quickly. The “butterfly effect” is in a sense a bit of an understatement. A chaotic system is sensitive to arbitrarily small changes in initial conditions. If the change is smaller, it just takes slightly longer to affect the system measurably.
    In fact, on two different computers, that do real-number representation differently, the difference in real-number precision will quickly dominate the model results, unless you make a special effort to prevent it, such as using a system with unlimited precision.

    “An unpredictable system can be used to generate pseudorandom results which are perfectly useful, but they are still not truly random.”

    I need to think this through. I don’t believe it is meaningful to call something pseudo-random, if it is truly theoretically unpredictable.

    Btw. forget my mention of Maxwell’s demon i my previous posting. Some reflection made me realize, that Maxwells demon is only impossible, if you insert it in the system itself. If you keep the “demon” in a parallel system, where you do not care about the entropy increase, there is no problem. So that was a bad example.

  19. rfhickeyon 04 Jan 2012 at 8:07 am

    @murmur – I remember Steve posting about psychohistory before in the context of another topic (here: http://theness.com/neurologicablog/index.php/how-dedicated-minorities-become-majorities/ )

    He wrote that:

    ” We can develop computer models and see how certain variables influence the system, but ultimate it follows the laws of chaos and cannot be predicted beyond a certain point.

    Hari Seldon’s psycho-history ran afoul of this as well. His plans to control future history with the mathematical precision of psycho-history ultimately failed because of one quirky individual that could not be predicted. (The story is actually more complicated than that, but I won’t include any spoilers for those who have not yet read the series.)”

    The problem with psychohistory seems that predicting future human events using human psychological principles is too crude of a way to do it. Psychological principles are based on biological and chemical processes, which in turn are based on the physical processes and interactions between bits of matter. You need to go deeper, to the atomic level or even deeper into the structure of matter (quantum level) it would seem in order to get some precision. Iam just too illiterate in physics to know (or even if it is known among physicists) if the randomness at the quantum level would prevent us looking forward or backward in time because they would muddle the ‘classical’ nature of matter and therefore prevent us from ‘rewinding’ or ‘fast forwarding’ through time. Assuming we had a computer that could compute it.

    @Rikki-Tikki-Tavi – Which brings me to my next point. Of course the computer would need to be unimaginably powerful…but where does the idea that it would need to be ‘bigger than the universe’ come from?

    Am I still on topic here? =)

  20. Rikki-Tikki-Tavion 05 Jan 2012 at 11:49 am

    rfhickey

    @Rikki-Tikki-Tavi – Which brings me to my next point. Of course the computer would need to be unimaginably powerful…but where does the idea that it would need to be ‘bigger than the universe’ come from?

    {Still trying to figure out how quotes work, this probably won’t have worked}

    http://www.edge.org/3rd_culture/lloyd2/lloyd2_p4.html

    That’s just something a quick google search turned up. I’ve originally read it elsewhere, but I’m not sure where. Where are physicists when you need them?

Trackback URI | Comments RSS

Leave a Reply

You must be logged in to post a comment.