Drunken Walks (But Not the Pubcrawl Variety)

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² = 100; 5² = 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.