advertisement

Print

Examining Random Events

by Owen Densmore
07/29/2002

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

Author's note: This is the first in a series of short articles 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 that the way ants discover near-optimal short paths to food can help run a data center.

I always think of random numbers as "uniform;" sort of an uninteresting fog-of-zero structure; the wave spread out across the numeric spectrum. Let's experiment with that idea. First, let's grab a bunch of random numbers between 0 and 1 and plot them. (I'll use Java, because 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

plot of random points
Figure 1. Plot of random points.

Figure 1 shows the "wave" aspect of random events ... a uniform spread across the spectrum of available values.

But now let's look at using this random generator to tease out the 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 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. Figure 2 is the picture the first 80 of them make. (See the Homework section of this article to download the file used to create the simulation and run it yourself.)

First 80 Walkers
Figure 2. First 80 walkers.

Recall that the red dot is the current position of the walker, and the yellow is where she has been. Averaging all of the positions, including the +/- sign, we get something near 0 (-4.4, to be exact). We also get lots of walkers at 0. The surprise, however, is just how far the walkers wander away from the point of 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. Figure 3 below is a chart showing the average of all 251 walkers over time, in red, with the theoretical distance drawn in black. The histogram of all of the walkers is shown in Figure 4.

Average of all walkers over time.
Figure 3. Average of all walkers over time.


Figure 4. Histogram of all of the walkers.

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 that is proportional to the square root of the number of steps).

This is fanciful, I admit, but I hope to convince you in 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 the 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 lifelike 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. Download the walk.nlogo file used in this article and use it as an input file to NetLogo, and then run the simulation.

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.

The title for Gary William Flake's book, The Computational Beauty of Nature, sounds a bit odd, but it's one of the best how-to books, and includes lots of code samples.

Owen Densmore is an independent researcher/scientist who hopes to get billions of small devices to work well together, while hopefully not annoying the folks that depend on them.


Return to the O'Reilly Network.