A Drunkard’s Walk in Manhattan

One of the most cherished mathematical learning moments of my youth came from an old and very funny math book, whose name I have sadly forgotten. It was through a cartoon in that book that I first learned how to figure out the distance covered by a completely random form of movement — the drunkard’s walk. The first panel of the cartoon showed a disheveled man near a lamppost. His future path was represented by a series of wild zigs and zags on the path in front of him, shown as a dotted line. “I know how to figure out how far I’ll be from this point on average,” he says. “All I have to do is to measure the average length of my zigs and zags, and multiply by the square root of their number.” Then, in the second panel, he pulls out a bottle from his coat pocket, lifts it toward his mouth, and says, “But first, I’ll have a little drink!” Now, where are the funny math books today?

Randomness is an inextricable and essential aspect of our world. Combined with selection, randomness can do incredible things: It has powered evolution and created the entire biological world. Yet randomness is commonly underestimated and misunderstood. Certain observed phenomena prompt many people to attribute magical causes to events and imbue people with supernatural abilities, when the workings of randomness are all we need to explain their observations. Of course, probability theorists have always known that randomness, to a large extent, rules our lives, as the author Leonard Mlodinow explains in his delightful book The Drunkard’s Walk. Recently, researchers have penetrated deeper into the intricacies of randomness, as Kevin Hartnett reports in the Quanta article “A Unified Theory of Randomness.” Hartnett’s article explains how this unified theory of randomness is informed by variants of the same random phenomenon we alluded to earlier: the random walk, or, as it is more colorfully named, the drunkard’s walk. This phenomenon explains the diffusion of fluids and also describes Brownian motion, which Einstein famously analyzed to determine the existence and size of atoms.

But back to our drunkard. When an object or a person moves randomly, the average distance it will be from its starting point can be predicted to be approximately $latex x \sqrt n$, where x is the average length of each step and n is the number of steps. The more the drunkard walks, the farther he gets from his starting point. Why should this be when his steps are random? Here’s a very nice informal argument presented by Marty Green, that helps to understand this result for equal-size steps. In the figure at left, which has been reproduced from Green’s blog, let us suppose that the drunkard started from the lamppost (center of the circle), took several one-meter steps, and by chance found himself on the circumference of the circle, say, five meters away. After the next step, he will be on the circumference of the smaller circle of radius one meter centered on the point where he had been. More than half of this circle (the green part) is outside the five-meter circle. So the next step will be more likely to take him farther away from the lamppost rather than closer, and this is true no matter where he is at a given time. How much farther will he go? In order to determine the new average distance we will have to integrate all his possible distances around the circumference of the circle. Some points on it are closer to the origin than before, and a larger number are farther. The most “neutral” step he could take is perpendicular to the big circle’s radius:  one meter along the tangent. Coincidentally, considering just this one neutral direction gives the right answer. One meter along the tangent would place him, by Pythagoras’ theorem, $latex \sqrt 26$ meters away. Since his previous location at a distance of five meters is the square root of 25, we see that this little trick gives us exactly the answer that we sought: The mean distance is proportional to the square root of the number of steps.

Our first problem applies this technique to a drunkard taking a walk in a city laid out like a grid, such as Manhattan. The second problem requires you to settle a bet between two friends walking in the same city.

1. Imagine that the drunkard is in the middle of a city laid out like a grid, with numbered streets running east to west and numbered avenues running north to south. The lamppost is at the corner of 5th Avenue and 5th Street, which we will designate as (5,5). The drunkard is sober enough to navigate a whole block before making a random choice at the next intersection. Let us say that after several such random block-length walks, he is now at (8,8). If we try to apply the circle argument shown above, we find that he can proceed to (9,8) or (8,9) or (8,7) or (7,8). Two of these are closer to, and two are farther from, his starting point. Does this mean that the calculation for the drunkard’s walk doesn’t work on a rectangular grid? What’s wrong with this argument? Once you’ve found the fallacy, can you derive the analogous distance formula for the drunkard’s walk on a rectangular grid using city block units?
2. Assume that the above city has a 0th Street and 0th Avenue (it was designed by computer scientists!). Two coin-collector friends, Sally and Al, arrive in the city by subway, each carrying a stack of silver dollars. They emerge at the corner of 6th Avenue and 5th Street and play the following game. At each intersection they toss two coins to determine randomly which direction they should walk next, out of the four choices available to them. Sally’s goal is to reach 0th Street or 8th Street. Al’s target is 0th Avenue or 8th Avenue. If the random direction chosen gets either Al or Sally closer to their respective targets, the other person pays him or her a dollar. Conversely, if either person’s distance from his or her target increases, that person has to give the other person a dollar. If the random direction is neutral with respect to the distance from either target, no money is exchanged. The game ends when one of them reaches his or her target. Notice that at the beginning, Al is closer to 8th Avenue than Sally is to 8th Street, but if he reaches it directly with two lucky westward walks, he will win only $2. Sally is farther from her targets but can potentially win more by the end of the game, because she can improve her position more times. Whom does this game favor in the long run?

There are many ways to solve the second problem. Try to do it using pen and paper if you can, and only use modern aids if you cannot make progress the old-fashioned way. I have given two general hints below.

(Click on “Hint 1” and “Hint 2” to make them visible.)

Hint 1 Use the idea of symmetry and mirror-image intersections. What would the probabilities be when the street and avenue numbers are equal?

Hint 2 How is the probability at a given intersection related to the probabilities at the four adjacent intersections?

For those who want to explore random walks further, many questions present themselves. What is the average number of blocks the friends will have to walk before one of them reaches his or her target? This is possible to figure out on paper, but feel free to uncork more powerful tools: simulations in a spreadsheet, online tools like Wolfram Alpha, programming using math software ­— whatever you prefer. Hartnett explains in his article how there are some types of random walks in which it is forbidden to cross your own path. How does that affect the number of blocks walked, and the random walk formula? What other mathematical techniques can be applied, and how does this relate to diffusion?

I am sure Quanta readers will find many other avenues (and streets!) to explore. As for me, I think I’ll have that drink now.

Editor’s note: The reader who submits the most interesting, creative or insightful solution (as judged by the columnist) in the comments section will receive a Quanta Magazine T-shirt. And if you’d like to suggest a favorite puzzle for a future Insights column, submit it as a comment below, clearly marked “NEW PUZZLE SUGGESTION” (it will not appear online, so solutions to the puzzle above should be submitted separately).

Note that we may hold comments for the first day or two to allow for independent contributions by readers.

Correction: This column was revised on Sept. 5, 2016, to reflect that Al would be walking westward from 6th Avenue to 8th Avenue.

Update: The solution has been published here.