March 13, 2005
The virtues of playing dice
In physics, everyone (well, almost) assumes that true randomness does exist, because so much of modern physics is built on this utilitarian assumption. Despite some people being very determined to do so, physicists have not determined that determinism isn't the rule of the universe; all they have is a bunch of empirical evidence against it (which for most physicists, is enough). So-called "hidden variable" models have been a popular way (e.g., here, here and here) to probe this question in a principled fashion. They're based on the premise that if in, for instance quantum mechanics, there was some hidden variable that we've just been too stupid to figure out yet, then there must be regularities (correlations) in physical reality that betray its existence. Yet so far, no hidden variable model has prevailed against quantum mechanics and apparent true randomness. (For an excellent discussion of randomness and physics, see Stephen Hawkings' lectures on the subject, especially if you wonder about things like black holes.)
In computer science, everyone knows that there's no way to deterministically create a truly random number. Amusingly, computer scientists often assume that physicists have settled the existence of randomness; yet, why hasn't anyone yet stuck a black-body radiation device inside of each computer (which would be ever-so-useful)? Perhaps getting true randomness is trickier than they have come to believe. In the meantime, those of us who want randomness in computer programs have to make do with the aptly-named pseudo-random number generators (some of which are extremely sophisticated) that create strings of numbers that only appear to be random. (It can be very dangerous to forget that pseudo-random number generators are completely deterministic, as I've blogged about before.) It frequently surprises me that in computer science, most people appear to believe that randomness is Bad in computer programs, but maybe that's just the systems and languages people who want machines to be predictable. This is a silly idea, really, as with randomness, you can beat adversaries that (even extremely sophisticated) determinism cannot. Also, it's often a lot easier to be random than it is to be deterministic in a complicated fashion. These things seem rather important for topics like oh, computer security. Perhaps the coolest use for pseudo-random number generators is in synchronization of wireless devices via frequency hopping.
There are a couple of interesting points derived from Shannon's information theory about randomness and determinism. For instance, my esteemed advisor showed that when a technologies uses electromagnetic radiation (like radio waves) to transmit information, it has the same power spectrum as black-body radiation. This little result apparently ended up in a science-fiction book by Ian Stewart in which the cosmic microwave background radiation was actually a message from someone-or-other - was it God or an ancient alien race? (Stewart has also written a book on randomness, chaos and mathematics, which I'll have to pick up sometime.)
Here's an interesting gedanken experiment with regard to competition and randomness. Consider the case where you are competing against some adversary (e.g., your next-door neighbor, or, if you like, gay-married terrorists) in a game of dramatic consequence. Let's assume that you both will pursue strategies that are not completely random (that is, you can occasionally rely upon astrology or dice to make a decision, but not all the time). If you both are using sufficiently sophisticated strategies (and perhaps have infinite computational power to analyze your opponent's past behavior and make predictions about future behavior), then your opponent's actions will appear as if to be drawn from a completely random strategy; as will your own. That is, if you can detect some correlation or pattern in your opponent's strategy, then naturally you can use that to your advantage. But if your opponent knows that you will do this, which is a logical assumption, then your opponent will eliminate that structure. (This point raises an interesting question for stock marketers - because we have limited computational power, are we bound to create exploitable structure in the way we buy and sell stocks?)
The symmetry between really complicated determinism and apparent randomness is a much more universally useful property than I think it's given credit for, particularly in the world of modeling of complex systems (like the stock market, navigation on a network, and avalanches). When faced with such a system that you want to model, the right strategy to pursue is probably something like: 1) select the most simple mechanisms that are required to produce the desired behavior and then 2) use randomness for everything else. You could say that your model then has "zero intelligence", but in light of our gedanken experiment, perhaps that's a misnomer. Ultimately, if the model works, you have successfully demonstrated that a lot of the fine structure of the world that may appear to matter to some people doesn't actually matter at all (at least for the property you modeled), and that the assumed mechanisms are, at most, the necessary set for your modeled property. The success of such random models is very impressive and begs the question that does it make any difference in the end if we believe that human society (or whatever system was modeled) is not largely random? This is exactly the kind of idea that Jared Diamond explores in his recent book on the failure of past great civilizations - maybe life really is just random, and we're too stubborn to admit it.
posted March 13, 2005 12:26 AM in Thinking Aloud | permalink