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.
Addendum
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.
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.
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.
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.
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.
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.
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?
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.