RANDOM WALKS, a Mathematical Simulation

Annual Budget of Ministry of Silly Walks: 348,000,000 pounds sterling In a conversation on the newsgroup talk.origins with regards to evolutionary algorithms, the assertion had been made that a random walk is equivalent to random sampling. We will test this proposition with a simple, open source simulation.

Oh no! Dr. Pitman lost his keys on the playing field. But it's nighttime, and in order to find the keys, he will have to search by walking blindly in the dark.

Many have offered suggestions for the best way to conduct the search:

Look under the lamppost where the light is better.
Finite steps, then quit. (Dr. Pitman gets tired and walks home.)
Drop off edge of field. (Dr. Pitman takes wrong turn at Albuquerque. Never heard from again.)
Bounce off edge of field. (Dr. Pitman keeps wandering in field until he finds his keys. Mutters each time he reaches edge.)
Wrap around field. (Others would like to help look, but only if the playing field is some futuristic sphere like Thunderdome.)

Well, let's face it. Our tenacious Dr. Pitman won't just give up and walk home.

Mr. Teabags: Good morning. I'm sorry to have kept you waiting, but I'm afraid my walk has become rather sillier recently, and so it takes me rather longer to get to work. Now then, what was it again?

Mr. Pudey: Well sir, I have a silly walk and I'd like to obtain a Government grant to help me develop it.

Mr. Teabags: I see. May I see your silly walk?

Mr. Pudey: Yes, certainly, yes.

May I see your silly walk?

Mr. Teabags: That's it, is it?

Mr. Pudey: Yes, that's it, yes.

Let's represent the playing field as a rectangular box divided into squares. Dr. Pitman can step randomly into any of the four adjoining squares. He keeps walking randomly until he stumbles across the keys. Each step takes the same time and travels the same distance.

(And to make it a bit easier, Dr. Pitman can't accidentally leave the box. If he attempts to move beyond the edge, he steps in the other direction. Otherwise, poor Pitman might never find his keys!)

In our typical example, the box will be 50 x 50. Remembering that Dr. Pitman can't leave the box, and as there are about 2500 squares making up the box; we hope that after no more than a few thousand steps he'll stumble across the keys. Whew!

I'm afraid my walk has become rather sillier recently And what if Dr. Pitman's friend decides to help. They start at the same location and go in their own random directions, one blind step at a time. How long should it take? What if the entire playing team helps, everyone gathering at the same location, then going their separate, random ways?

How long will it take to find Dr. Pitman's keys? In particular, is it proportional to the number of walkers? And will Dr. Pitman ever stop wandering aimlessly?

Walker = Aimless wanderer, Dr. Sean Pitman.
Origin = Where the walkers start, presumably under the lamppost.
Target = What the walkers are looking for, Dr. Pitman's keys.
Time = number of locksteps, faster = shorter time.
Steps = walker-steps, total steps for all walkers, efficiency = fewer steps.
Distance = Direct walking distance.
Budget of Ministry of Silly Walks = £348,000,000

X-axis: number of walkers (1 to 100)
Y-axis: total number of steps (sum for all walkers)
Trials: 1 (more than four hundred thousand steps)

Area: 50 x 50 = 2500
Distance: 10

That's it, is it? Interesting. With just one trial, there is a very high variance in results. Frankly, the results are all over the place. Consequently, we should treat our trend line as very tentative. Once the walkers leave the general area, they tend to disperse, and it might be some time before one finally returns to the target area.

So, let's increase the number of trials.

X-axis: number of walkers (1 to 100)
Y-axis: Time (number of steps by each walker)
Trials: 200 (More than thirty-four million steps!)

Area: 50 x 50 = 2500
Distance: 10

Ah yes! Now that's more like it. A smooth graph, and note that with more walkers, it clearly takes less time. In fact, it looks much like multiple random samplers (Time = Area/Samplers, Y = 2500X^-1). But what about the total number of steps, the efficiency of our walkers?

Definitely not a straight line! Not only does the time decrease with an increase in walkers, but so has the total number of steps. Of note, the graph for the standard deviation [not shown] looks almost identical to the graph for the number of steps. In other words, not only do the number of total steps for all the walkers decrease with increasing numbers of walkers, but they more reliably find the target.

Mr. Pudey, the very real problem is one of finance.

Hmm, with a target distance of ten, random sampling appears to be more efficient. And it appears that the data climbs above our trend line near the end of the graph — as if our efficiency is degrading.

We need more data!

Consider the following image with a hundred walkers. The walkers appear to expand out from their initial starting place, and move inexorably closer to their goal. Each walker moves randomly, yet they seem to have a direction. This is an example of how random events can create a type of order.

But can we continue to increase the numbers of walkers indefinitely without sacrificing efficiency?

Mr. Teabag: Yes, yes, yes. It's not particularly silly, is it?

Mr. Pudey: Well, ah-ah...

Mr. Teabag: I mean, the left leg isn't silly at all and the right leg merely does a forward aerial O'Brien half turn every alternate step.

Mr. Pudey: Yes, but I feel with a federal grant I could make it a lot more silly.

X-axis: number of walkers (1 to 35, 35-100)
Y-axis: Total steps by all walkers
Trials: 200

Area: 50 x 50 = 2500
Distance: 7

This time, the distance to the target is seven. Again, we will gradually increase the number of walkers. For comparison, a random sampling takes about twenty-five hundred steps. A couple of walkers are less efficient than a random sampling, but with about six walkers or so, the walkers take fewer overall steps. They are more efficient.

If there are seven to a hundred walkers, they will find the target more efficiently than a random sampling. However, the optimum for efficiency is about twenty-five walkers. More walkers than that results in a great deal of overlapping searches, though still in less time, with less variance, and more certainty. More than a hundred or so walkers, and our efficiency continues to degrade and is finally reduced to below that of a random sample.

The area of the box stays the same, so a random sample will take an average of twenty-five hundred 'steps' to find the target. On the other hand, the random walkers do better when the distance to the target is small, and worse when the distance to the target is large. When the target is on the edge of the box, then walkers are at their least efficient. The break-even point, in this case, is at a distance of about eight or nine. So unlike random sampling.

If the target is not close to the origin of the walkers, then a random sample is generally faster and more efficient than walkers. With walkers and a distant target, though just a few may take more time than a larger number of walkers, they will be more efficient, or rather, less inefficient. As each walker will waste much of its initial search near the origin, more walkers means more lost steps in the search for a distant and elusive goal.

Mr. Teabag: Mr. Pudey, the very real problem is one of finance. You see, there's defense, education, housing, health, social security, silly walks. They're all supposed to get the same. But last year the government spent less on Silly Walks than they did on industrial reorganisation. We're supposed to get 348 million pounds a year to cover our entire Silly Walks programme. Coffee?

In order to increase our resolution, we have increased the number of trials considerably. We will keep the number of walkers at ten, and the distance to the target at ten, but we will increase the size of the box in increments. We know analytically that the total number of steps for a random sample will increase directly with area, Area^1. But the number of steps for walkers will increase much, much more slowly, on the order of Area^0.3

(We have been using power curves for our trend lines. This is only to indicate an approximate fit, not the analytical solution.)

In a vast search area, then, any reasonably close target can more easily be reached by a random walk than mere random sampling. More walkers will tend to find the target faster, and may even be more efficient overall than fewer walkers.

Random walks do not accurately represent biological adaptation, which relies primarily on selection to guide the search through stepwise changes. In addition, we have shown that random walks have few salient characteristics in common with random sampling.

So Dr. Pitman finally found his keys. But will he ever stop wandering aimlessly? ;o)

Mr. Teabags: Now Mr Pudey. I'm not going to mince words with you. I'm going to offer you a Research Fellowship on the Anglo-French.

Mr Pudey: La Marche Futile?