Complexity Note One: On the Wave/Particle Duality of Random Events.

Note: This is the first of a series of chats on complex adaptive systems and how they are beginning to be applied to computing, mainly in the areas of robustness, self organization, and peer (local knowledge) systems. This field is quickly showing us how the way ants discover near-optimal short paths to food can help run a data center.

I always think of random numbers as "uniform"; sorta an uninteresting fog of zero structure.  The wave spread out across the numeric spectrum. Lets experiment with that idea.  First, lets grab a bunch of random numbers between 0 & 1 and plot them. (I'll use Java 'cause later I'm going to use NetLogo, a Java application, to look at other random features.)

public class RanTest {
    public static void main (String args[]) {
        for (int i=0; i < 10000; i++) {
            double r1=Math.random();
            double r2=Math.random();
            System.out.println(r1+" "+r2);
        }
    }
}

We'll compile and run this and then use gnuplot to create an image:

javac RanTest.java; java RanTest > random
gnuplot << EOF 
set terminal png color
set output "random.png"
set size square .5,.5
plot "random" t "" with dots
EOF

This is the "wave" aspect of random events .. a uniform spread across the spectrum of available values.

But now lets look at using this random generator to tease out surprising structure.  We'll take a one dimensional "random walk" by flipping a coin, so to speak .. asking the random number generator to give a random 0 or 1.  On 0, we go right one step, on 1 we go left one step.  We do this a large number of times and notice how far from the initial point we wander over time.  And we repeat this with several "walkers" (agents).

To make this easier to see, I'll use a nifty agent simulation system called NetLogo.  I stack up 251 red walkers on top of each other, and have them paint where they've been in yellow.  Here is the picture the first 80 of them make, click the image to see the full NetLogo simulation:

First 80 Walkers.  Click Image for Complete NetLogo Simulation

Recall that the red dot is the current position of the walker, and the yellow is where she has been. Averaging all the positions, including the +/- sign, we get something near zero (-4.4 to be exact).  We also get lots of walkers at zero.  The surprise, however, is just how far the walkers wander away from the origin, one power walker all the way to 200!.  To be precise, we average the distances (absolute value of location) and find that the walkers wander away proportional to roughly the square root of the number of steps taken.  Here's an explanation of the square root proportionality. Below's a chart showing the average of all 251 walkers over time, in red, with the theoretical distance drawn in black.  The histogram of all the walkers is also shown.

This experiment exhibits both the wave nature of random events: lots of values spread over all possibilities, and the particle nature: a surprisingly ordered tendency to wander proportional to the square root of the number of steps.

This is fanciful, I admit, but I hope to convince you over the next couple of articles that this teasing of structure out of randomness is extremely important to new directions in computing.  From the Small Worlds problem, to mixed strategy game optimization, randomness leads from unordered to ordered solutions.

Why should you care? Because computing is starting to use the techniques of complex adaptive systems to build extremely robust systems composed of many independent but communicating components. The life-like behavior they display is often best understood by teasing out the "particle nature" of their random behavior. This is the story of "complexity".

Homework: Download NetLogo and run several of the included models.  Modify one to do something new and interesting. Here is the walk.nlogo file used in this article.

Further Reading: Mitchell Waldrop's Complexity is a history of the early days in the field and describes the birth of the Santa Fe Institute. Flake's book The Computational Beauty of Nature sounds a bit lame but its one of the best "HowTo" books, including lots of code samples.