Logo IMG
HOME > PAST ISSUE > Article Detail


The Quest for Randomness

Determining whether numbers truly can have no pattern has implications for quantum mechanics, not to mention the stock market and data security.

Scott Aaronson

A Random Number Complex

Even though Kolmogorov complexity can’t be computed, it still has huge conceptual applications to ensuring something is random. The starting point for those applications is yet another puzzle. How can you produce a string of numbers—even just one—that has high Kolmogorov complexity?

There’s one easy way to do it: Pick a string randomly! If you choose a string of n bits completely at random, then there’s an overwhelmingly good chance that it will have Kolmogorov complexity close to n, because of what’s known in the trade as a “counting argument.” There are 2n strings of n bits (again, base 2, because there are two options for bits, 0 or 1), but it turns out that there are at most 2k+1 1 possible computer programs of k bits or fewer (less, actually, because most strings don’t correspond to any valid program). By definition, each program can produce at most one n-bit string as its output.

But if k is even a little bit smaller than n (say, n 50), then 2k+1 1 will be vastly smaller than 2n. So we conclude that there simply aren’t enough short programs to go around: If you choose an n-bit string x at random, then you’ll almost certainly have K(x) approximately equal n. The crucial point is that picking randomly turns out to be the only way to generate strings with high Kolmogorov complexity.

To give a real-world example of this phenomenon, consider file compression programs such as gzip. These programs make files smaller by exploiting regularities in the data to be compressed, such as the same words appearing over and over. But you can’t compress a random string, because the data are already free of computable regularities (or in other words, the string has maximal Kolmogorov complexity). As an interesting aside, in 2002, a company called ZeoSync made headlines with claims that it had a breakthrough algorithm that could compress arbitrary data. In interviews, however, the company’s founder was never able to answer questions such as: What would happen if you fed a compressed file back into the compression program, and so on ad infinitum? Would the file get compressed to nothing? The company disappeared a few months later.

Do I sense that you’re still underwhelmed by this? Does it all feel circular to you—like a complicated way of saying “if something is random, then it’s random”? Sure, we’ve replaced a “metaphysical” question (i.e., whether events are determined or random) by a purely mathematical question (i.e., whether a description of the events has high Kolmogorov complexity). But it might not be obvious that we gain anything from that trade! Let me give a concrete example that helped convince me that the trade is beneficial.

comments powered by Disqus


Subscribe to American Scientist