
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. 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!) 

The Results 
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. 
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.
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!


Mr. Teabag: Yes, yes, yes. It's not particularly silly, is it? Mr. Pudey: Well, ahah... 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. 
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 twentyfive 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 twentyfive 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. 


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 AngloFrench. Mr Pudey: La Marche Futile? 


Monty Python 
It's Silly (Wav, 20KB) I Have a Silly Walk Ministry
of Silly Walks 