##### Drunken Walks (But Not the Pubcrawl Variety)

Imagine a drunk standing in the middle of a field. Every time he tries to walk a step, he winds up staggering in a random direction: north, south, east, or west. How long will it take him to get to the edge of the field?

We can look at it intuitively, and say that he’s as likely to stagger north as south, as likely to go east as west. So after 100 steps, he will most likely have made 25 steps north and 25 steps south, which cancel out; and 25 steps east and 25 west, which also cancel out. So he’ll just keep staggering around his spot in the middle of the field until he sobers up.

### Stagger Stagger Crawl Crawl Stagger

But how good is our intuition? Here’s a simple piece of Perl code that implements the drunken walk described above:

$x = $y = 0; $steps = 10000; for (my $i = 0; $i < $steps; $i++) { my $dir = int(rand(4)); if ($dir == 0) { $x++; } elsif ($dir == 1) { $x--; } elsif ($dir == 2) { $y++; } else { $y--; } print "$xt$yn"; }

You don’t need to know Perl to understand this. Just read the description above. Here, `x` and `y` are the drunk’s coordinates, and the `steps` variable is the number of steps to take. At each step, the program picks a random number between 0 and 3, and depending on the value of that number, increases or decreases the X or Y coordinate.

(There’s also a drunken-walk module for XScreensaver. See a screenshot here; scroll down to “Wander”.)

Let’s run this program ten times, plot the path taken by our drunks, and see what it looks like:

Notice that some of these drunks have managed to stagger quite a ways from where they started at (0, 0). If they started 100 steps from each of the four edges, several of our drunks would have made it out of the field: #3 (blue), #4 (purple), #6 (brown), #7 (yellow); and #9 (orange) got to the eastern edge pretty early and could have slept it off by now.

So we know that just by a random walk, a drunk can get pretty far from where he started. But how far?

Let’s say that a drunk started at (0, 0) and wound up at (10, 5), that is, 10 steps east and 5 steps north. Normally, we’d calculate the straight-line distance using the pythagorean theorem by adding the squares of the east-west distance and the north-south distance, then taking the square root of the sum: 10^{2} = 100; 5^{2} = 25; 100+25 = 125; square root of 125 = 11.18; so the drunk is 11.18 steps from where he started, as the crow flies.

But in this case, for simplicity, we’ll just add the north-south distance and the east-west distance. The reason for this is that since our idealized drunk can only walk north, south, east, and west, the shortest path from (0, 0) to (10, 5) is to walk 10 paces east, then 5 paces north. So the distance is 10 + 5 = 15.

### Summon the Drunken Horde!

So just how far *should* we expect a drunk to get? To answer this, we’ll summon 100 drunks, have each one walk 10 paces. Then we’ll see how far each one wound up from the starting point (using the distance measure described above), and calculate the average. Then we’ll do the same thing with 100 drunks walking 11 paces, then 12 paces, and so forth, all the way up to 10000 paces. (Okay, we’ll skip a few in the middle: 100 paces, then 110, 120, 130, up to 1000; then 1100, 1200, 1300, etc. up to 10000.)

Lucky for me, I just happened to have 28100 drunks available. Here’s what I got when I plotted the result of their inebriated random staggering:

Along the horizontal axis, we have the number of steps taken by each drunk. Along the vertical axis, we have the distance from the starting point (as defined above).

Each red cross represents a drunk who has walked X paces and wound up at distance Y from his starting point. As one might expect, they don’t travel anywhere near as far as they would if they’d just pick a direction and keep going that way: the drunks who have walked 1000 paces have almost all wound up less than 100 paces from where they started. On the other hand, there’s a pretty wide distribution of distances. Our intuitive reasoning above suggested that all of the red crosses should be bunched up near the bottom of the graph, and clearly they’re not.

The green line (which is a little hard to see; sorry about that) is the average eventual distance for all drunks who have walked a certain number of paces. As you can see, it jogs up and down somewhat, which is only to be expected any time randomness is involved. It should be possible to make this line smoother by using more than 100 drunks in each run.

The blue line on top of the green line is a best-fit curve of all the points in the green line. It’s just the square root of the number of paces taken, times 1.13196 (or 1.13196 * √x). (I don’t know what this 1.13196 is, nor what it represents. It doesn’t seem to be the square root, inverse, logarithm, etc. of anything interesting. Then again, given the amount of “wobble” in the green line, it’s probably only an approximation to something.)

So now we know that drunken walks can wind up far from where they started, and that this distance is, on average, approximately the square root of the number of steps taken. So much for intuition.

**Update, just a few minutes later:** I said above that the green line showing average distance should have a lot less wobble with larger numbers of drunks. I just reran the same plot with 1000 drunks per run, and got the following:

And, indeed, the green line now has a lot less wobble. (It looks thick, especially on the left. But that’s just because of the crosses through the line, that you can see in the legend at the top right.) Oh, and the best-fit line is now 1.12837 √x.

All this drunken staggering and naturally my brain leaps to Jack Sparrow, and his tendancy to fall on his face in the sand after a few steps, but I’m not sure a 5th alternative, “stay there” is useful unless one is searching for a moving target- in which case, falling down occasionally might help.

The distance is interesting, but I wonder how many random drunks you need to push off from the middle of the field to get decent coverage of the field as a whole, as opposed to just how far the drunk gets before being picked up for vagrancy. (For a field of area N^2, if you sent N drunks staggering N steps before being reaped by the Cop process, how much will get covered?) Certainly one drunk is going to cover a subregion reasonably well (although we don’t know which subregion) but is it going to perform differently in the long run than just pulling coordinates of the field out of a grab bag and checking them?

If nothing else, this is going to prove an interesting thing to think about today, as I go to the Zoo in the company of several silly children likely to act this sort of algorithm out, even without me asking!

Actually, I was thinking of Yellowbeard, but yeah.

True. I considered standing still, but since I wanted to talk about distance, standing still was beside the point.

As for searching for moving targets, there’s the Anemotaxis module for XScreenSaver. The odor particles come from the left and disperse randomly, while bees (or whatever) come from the right and do a methodical search to find where the odor is coming from. You’ll have to imagine what it would look like with drunken bees.

If I may engage in

argumentum ad saverum screenionce more, try running the Wander XScreenSaver module, and see how long it takes to fill your window. Or get a Roomba and watch it.Except, of course, that the Roomba doesn’t stagger: it runs in a straight line until it bounces off of something, and occasionally goes around in circles, which means that it’s best modeled by a toddler rather than a drunk.

Can you publish a overhead plot of where the 28100 drunks ended up? You’ve shown how far each one went, but it’d be interesting to see how much they are huddled around the center when looking at the field itself…

Well, from the graph I’d expect them to be distributed throughout an area around the middle (though there seem to be fewer close to the center than I’d expect).

Or, they would be distributed in an image of Henry the VIII. Another question, what happens after 10000 steps? It appears to be approaching an asymptote.

I actually conducted this study in a High Performance Simulation class some time ago, and WTGAHG is right. If you have enough computing power, using a higher step count (50000, 300000, or even a million), we can see that the best fit line nears 1.414√x, or √2x.

Drunk Walker:

Thanks for the update.

I beleive this pattern is less tjen random as the drunk only has three choices so always moves forward, He never turns around and goes back a step to do so requires at least 2 steps ii nthe same direction. So to go from borth to south requires two lefts or two rights in a row which is less likely.