Thought Experiment On Randomness

Was discussing pseudo-random number generators with a colleague, around desirable attributes of the distribution, periodicity, etc — all fun and important stuff.

It reminded me of a chain of thought ranging from complexity theory to the philosophical.   Pardon the armchair physics and philosophy.

As we know from information theory, any sequence generated by an algorithm with no exogenous input, except perhaps an initial state, cannot be random.   There are multiple measures of randomness in theoretical computer science around measuring the degree of pattern in a given sequence (or string).    One that appeals to me, is the Kolmogorov complexity measure (I was reminded of this by recent posts on Shtetl-Optimized) which is approximately:

for some string x (say a random sequence we are testing), what is the shortest possible program in some universal computer language K(x) that prints x and halts.

Intuitively, if a sequence is truly random, there is no algorithm that can generate it short of the sequence literal itself.  Assuming we a looking at very long sequences of  X (our random sequence), the program to produce that must also be very large (as long as the literal) and hence have a very high K(x) measure.  A long pseudo random sequence may look to be quite complex at first glance, but can be described by a short program generating the sequence, and hence has a low K(x) measure.

Not being a complexity theorist, I’m playing pretty loose with the definition, but you get the idea.

Going further, one thing I’ve often thought about, is whether randomness truly exists in the universe.   This may be equivalent to asking, is the universe computable.  This question and theory around this has been proposed and discussed since the 1950s.   Are the random distributions we see in quantum states, for example, just manifestations of a complex computable function, probably one with many dimensions and long periodicity.

If the fabric of the universe is computable, then it stands to reason that what is contained within is also.  In this scenario, we being computable machines made of this macro-stuff called matter, are just very complex functions of our initial states;  Not just our initial state (our conception and program therein), but the state vector of all influences in the universe, our surroundings, and other automata.

Well you can see where this goes.   Free will is a function of our reason and environment, but our reasoning function is also predetermined by this astronomical state vector / ongoing computation.

Anyway, I was reluctant to post this for a while, but thought it would be fun for a change.  Starts with science and ends with philosophical possibility.

I should add, the data we receive from “random” physical processes appears to be random.  If we assume a computable universe, the generating function for these random processes could be vast given the possibility of an “astronomical”, but finite, number of inputs (or dimension).   i.e.  Our approximation of the K(x) function appears to be large just because we do not know how to determine the generating function.   Hence in a short life-time of observation and computation, such a function would have the appearance of randomness (as in maximal complexity) and infinite period.



Filed under strategies

11 responses to “Thought Experiment On Randomness

  1. Scott Locklin

    Somehow I missed this post. Google around a bit on the “Ford Paradox.” -actually, scratch that. I’m the only one on the internets who seems to know about it. The idea is, classically chaotic systems generate random numbers in a very “real” sense. Not in a “gee that looks random” sense, more like, “if I had a computer with an infinitely big register, I still couldn’t reproduce this series of numbers my double pendulum makes.” Quantum systems don’t. If QM is the ultimate theory of matter, well, WTF? Maybe I’ll do a blog on the subject. it’s a very deep issue that nobody bothers thinking about. It should be one of the great mysteries of the universe. But people are too busy thinking about shit which will get them tenure to bother. I also think people are mostly unaware of it.

  2. The chaotic systems I am aware of can be explained by understanding the initial conditions (i.e. state vector), the state evolution function(s) that guide it, and any exogenous inputs.

    In your example of a double pendulum, let us assume that to test the randomness of this we must make empirical observations. Our measurements have finite precision and hence at least in terms of measurement, the space of possible values is finite (although astronomical). If the pendulums track through space is discrete in the way our measurements must be, then it will surely repeat itself at some point (of course that assumes that there is some resolution limit in space itself)

    One starts entering the realm of scientific belief here. My personal view (influenced by many others) is that space is discrete and has a finite resolution. This, in my mind, if true implies no true randomness or chaos, unless our universe is influenced by the exogenous.

    I am definitely far away from my main field of study here, but is a perhaps philosophical view that I find fascinating.

  3. Scott Locklin

    Even if you make your measurement with a lot of slop in it: chaotic systems still generate random numbers. One of the ways folks think about it (and also one of the approaches to semiclassical quantization) is they divide up the space into 2/3 partitions, and build a binary alphabet out of it. One can prove for some systems that the binary string generated is random. I think that’s historically how folks made some of this rigorous, though Shannon’s work more or less did the same thing 25 years earlier without the physical framework.
    This is really deep stuff, because, as Ford said, quantum mechanics shouldn’t generate random numbers. QM is just a superposition of periodic orbits. I really need to look at my aging notes and do a blog post on this, because it’s probably the most interesting topic in physics and information theory, and almost nobody cares.

    Downloaded Mono today, FWIIW.

    • tr8dr

      I’d love to see your exploration of this topic. I’ve admittedly only scratched the surface with speculation on my part. I’d be interested in seeing proofs of randomness in systems. I am an unbeliever 😉

      Why should randomness exist? The dimensionality of events or the state system that represents in our universe is vast. For practical purposes our observation of processes (functions) on this state space will appear to be random.

      I don’t see what could truly drive a random process. A truly random process could not be described by a finite function and the information needed to generate it, assuming information takes space, would require an infinite space.

      I may be missing something ,, look forward to more thoughts on this topic.

  4. tr8dr

    I should mention that with the last argument “A truly random process could not be described by a finite function and the information needed to generate it, assuming information takes space, would require an infinite space.” would be true if there is a finite resolution to space-time.

    If in fact space is continuous and has infinitesimal resolution, then a truly random process could be contained in finite volume. Assuming that there is infinite resolution, how such a sequence could come to be without a generating random process somewhere else is beyond me.

  5. Bo Peng

    Scott, chaotic systems are fully deterministic in the strict math sense. There’s nothing random about it. It’s one of the examples where a very short “program” can generate seemingly striking complexity. And if you look at the distribution of the output, with fine enough resolution and the right set of decomposition, it’s usually immediately clear that it’s not random. Now, is there a chaos system with output distribution closely resembling some well-known stochastic distribution, say Gaussian, above certain resolution threshold and in certain transformation (so as to “cover up” the original independent variables)? This I don’t know and therefore have to presume it’s possible. Maybe some PRNGs already use chaos?

    tr8dr, this is fascinating stuff. But I’m not sure what you mean by “info takes space”. In the engineering sense, yes. But otherwise why is this so?

    Philosophically, the scientific world has been trying to reject randomness since forever. Randomness is incompatible with logic. Quantum theory doesn’t generate randomness, either. It just says that, due to the inevitable disruptive nature of observation (it’s impossible to observe a system without interacting with it, therefore changing its state), it’s impossible (in the observability sense) to say a system is in a certain state. It doesn’t introduce randomness; it just says we cannot know beyond certain limit of uncertainty.

    So it leads to another question: if something is unknowable, does it exist? Quantum theory’s answer is no, in the scientific sense. In other words, if a tree falls in the forest and nobody hears it, it didn’t happen. This makes perfect sense, if you understand “hear” means “any observable effect”.

    But this is strictly in the scientific, falsifiable sense. On a more general, philosophical sense, sure, everything is possible — but what does it mean if it’s not falsifiable?

  6. I’ve thought about topic quite a bit. I hate it. It always bugs me. What in this universe could be random? It doesn’t make sense for something to be truly random. And yes, as you mention, if randomness doesn’t exist, then we are living in a deterministic universe. This implies that fate or destiny exists. All of our lives, the world’s history is pre-written. If we were living in “The Matrix”, where the entire world is programmed and data for everything can be extracted, then everything that is going to happen could predicted with 100% accuracy. If we had all the equations and all the data with enough computing power you could extrapolate into the future as far as you desired to see.

    But, the entire argument of the universe being a deterministic one, lies on the very fact that there cannot be one single truly random process in the universe. And how do you prove that? Ask Nassim Taleb how to prove that no black swans exist… You would have to investigate every single process, small to large, in the universe and make sure that it was not random.

  7. Douglas Cook

    If the universe is governed by physical laws that explain all interactions between objects (i.e. bodies, particles, etc.), then all physical interactions are completely deterministic, and hence true randomness cannot exist. Any apparent randomness is simply our conceptualization of behavior we can’t fully explain. In the past 500 years, we have not encountered a single physical system that is not governed by such laws. Physical systems behave according to known laws, and all behavior is governed by these laws and a set of initial conditions. From this standpoint, pure randomness would require the LACK of physical laws and relationships.

    Now there is one major exception to the above: living creatures make decisions that (at least thus far) cannot be explained in a deterministic sense. Although the physical world behaves predictably, individual minds (human or animal) obviously do not – at least not according to any kind of reliable relationship. I’m going to go out on a limb and propose that some decisions do involve some degree true randomness. Most decisions are logically based: run from predator to avoid being killed, slam on the brakes to avoid the car ahead of you, etc., But some of our decisions are quasi-random: What would you like for dinner tonight? What color shirt should I wear today? As a stronger example, imagine that you asked people to choose from one of three identical envelopes. Could there possibly be laws to govern this behavior? There may be minor cultural or personal inclinations for, say, the right-most envelope or the center envelope, but enough people would choose the others to destroy any possibility of forming a law based on this behavior. Physical laws are based on relationships and information. However, living creatures (and humans in particular) frequently make decisions even when there is a lack of information – which is practically a definition of randomness. So is there randomness? Yes, I believe the only true randomness in the universe exists in the decisions of living creatures.

  8. I believe it’s more likely to be deterministic rather than random. If some deterministic physical/natural process can generate randomness, and a lot observable results of the world depends on that, the world can appear to be random in every aspect. Thanks for sharing your ideas on this profound and interesting topic.

  9. Pingback: The enigma of the Ford paradox | Locklin on science

Leave a Reply

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

You are commenting using your 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