# A Drunkard’s Walk in Manhattan

Why is it that when you walk randomly, the more you walk, the farther you get from your starting point?

Olena Shmahalo/Quanta Magazine; Processing code by Masatake Hirao

A random walk, generated with Processing.

Save Save Save Save Save Save Save Save Save
26

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?

A monthly puzzle celebrating the sudden insights and unexpected twists of scientific problem solving. Your guide is Pradeep Mutalik, a medical research scientist at the Yale Center for Medical Informatics and a lifelong puzzle enthusiast.

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 $$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, $$\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. (Drag your mouse to highlight the empty spaces below the hints 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. (Update: The solution is now available here.) 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. View Reader Comments (26) Leave a Comment ## Reader CommentsLeave a Comment • Ken Pfeiffer says: Was the book you refer to One, Two, Three … Infinity by George Gamov? That was a book that had a serious impact on me as a child. • Enrique Treviño says: Just a comment on the Marty Green argument. It is very cute and a nice illustration of why the distance increases, but saying that you get square root of 26 there is deceiving. The expected value of the square of the distance would be 26, but the expected value of the distance (which comes from integrating as you suggest) is not sqrt(26), it is roughly 5.05. As explained in https://math.stackexchange.com/questions/103142/expected-value-of-random-walk, the expected value of the distance is roughly sqrt(2N/pi) not sqrt(N) (as N goes to infinity). • Pradeep Mutalik says: Thanks, Enrique. You are right. We will change the text. I guess the example, as you describe, is cute but should not be taken too literally. • Pradeep Mutalik says: @Ken, I do remember Gamov's "One, Two, Three … Infinity" very fondly. It does discuss the drunkard's walk and has cartoon illustrations, but a version of it I found on the web doesn't seem to have the particular cartoon I described. Gamov also uses the Pythagorean argument to derive the approximate most probable distance of the drunkard's walk. Another highly recommended book with funny and memorable illustrations from that time is "How to Lie with Statistics" by Darrell Huff. • Alex R says: I'm pressed for time, so I'll just answer the first part of the first question. The fallacy is that a "circle" in Manhattan is a square rotated by 45 degrees; because of this, there are 4 points on every circle which have a 75% chance of moving away, while all other points have a 50% chance, still netting an outward drift. • Pradeep Mutalik says: Update The sentence describing the distance now reads, "When an object or a person moves randomly, the average distance it will be from its starting point can be predicted to be approximately x sqrt(n)." The distance described is the most probable root mean square distance as the link provided by Enrique clarifies. • Marty Green says: I'm going to address the second question, which is simply: whom does the game favor in the long run? As I see it, at every given coin toss, each player has an equal chance of winning or losing a dollar. It doesn't matter who reaches their destination first. Throughout the game the odds are equal at every single step, so neither player is favored. • Marty Green says: Interesting point by Enrique Trevino about the discrepancy between the rms and absolute value distances. I did not know that. But I'm not surprised that the calculation turns out to be a mess when you try to integrate the absolute values. In physics, when you're dealing with vector quantities, the sensible average is always going to be the rms average (or the vector average, which is trivially zero in this case). If you have an ideal gas and you ask for the average velocity of a molecule, the rms average will obviously be the one that comes from the average energy. The average of the absolute values will be a slightly different number with (I'd bet good money) no physical significance. • Keith Tinkler says: There is a possible complication though for the Irish drunkard : on one occasion he came out of the Pub, grasped and circled the lamppost shouting "Let me out!, Let me out!" • Shlok Nahar says: It is easier to look at this puzzle as a 8×8 grid confined by the targets and then dividing it into 4 equal regions. Each point in each of the regions has an equal chance for both Sally and Al to win and lose a dollar. However, if Sally is anywhere on 4th Street (except 4th Street and 4th Avenue), three of the directions will give her a dollar and only one will cause her to lose a dollar. Similarly, if Al is on 4th Avenue he will most probably win a dollar. 4th Avenue and 4th Street has equal probabilities again. So, the most profitable places to be are 4th Avenue, and 4th Street for Al and Sally respectively. Sally is closer to 4th Street than Al is to 4th Avenue. So, it is more probable for Sally to reach 4th Street than for them to get to 4th Avenue. Besides, Al would have to pay 2 dollars to reach there and stand to gain at most 1 dollar, whereas Sally would have to pay just 1 dollar. So I think that the game would favor Sally in the long run since they start closer to 4th Street than 4th Avenue. • Karan Bhuwalka says: 1) Original distance is (2*3^2)^.5 =(18)^.5 If moves closer to 5,5 the distance is (3^2+2^2)^.5=(13)^2 If moves farther from 5,5 distance is (4^2+3^2)^.5=(25)^2 Average distance Increases if moves further, so moves away from 5,5 Can be shown that for an a, (a+1)^2 – a^2 is greater than a^2 – (a-1)^2 2) Assume Al has A budget. Sally has S. Lets say Al moves 2 steps closer/further to/from goal (avg takes 4 moves) Al moves to 4 or 8 with equal chance . If Al moves to Av.8 (probability is half) then game ends with Al having A+2 If Al moves to Av.4 (probability is half) Al having A-2 but now Al has an equal chance of ending the game in either direction. In the same interval, Sal can equally move to St.7 or St.5 If she moves to St.7 she has S+2,if she moves to St.5 she has S. (Note, if Al ends the game he always has A+2, If Sal ends it she has S+3 in all cases) CASE 1-Now if Al has finished the game in this interval by moving to Av8 he has either won or drawn with equal probability (say 1/4) because Sal either has S or S+2 for Als A+2 CASE 2- If he has moved to Av4, conversely. Sal has an advantage. If she has moved to St7, she has S+2 and is more likely to end&win the game. If she has moved to St5, she has S(>A-2) and is more likely to end&win the game. [From St7 she can move to 9(assume) or 5 with equal chance, one gives her S+3, one gives her S[same as initial state]; from 3 she can move to 1 or 5 with equal chance , 1 gives her S+2 (same as the 7 case), 5 takes her back to initial state. All of these are likely to be closer to win than Al who in the same interval gets A and is at either 2 or 6(same as initial case).] So Al likely wins in 1 of these cases, draws in another and loses in 2. Sally is more likely to win • Dev says: Was the book 'It's a Chancy Chancy World' by L. Rastrigin? • Tom Nichols says: Problem #1: The fallacy in the argument given for no increase in the drunkard’s distance from his starting point is that steps outward and steps inward do not change the squared distance by the same amount. Moving from (n, n) to (n+1, n) increases the squared distance by [(n+1)^2 + n^2] – [n^2 + n^2] = 2n + 1. Moving from (n, n) to (n-1, n) decreases the squared distance by [2^n +2^n] – [(n-1)^2 + n^2] = 2n – 1. The average increase is squared distance is [2(2n + 1) – 2(2n – 1)] / 4 = 1. Generalizing this result, suppose that the drunkard is at an arbitrary location on the grid (x, y) at squared distance x^2 + y^2 from his starting point. At the next step he will be at one of four locations: (x+1, y), (x-1, y), (x, y+1), or (x, y-1), and his average distance from his starting point will be: {[(x+1)^2 + y^2] + [(x-1)^2 + y^2] + [x^2 + (y+1)^2] + [x^2 + (y-1)^2]} / 4 = (4x^2 + 4y^2 + 4) / 4 = x^2 + y^2 + 1 That is, independent of where he is in the grid, the drunkard’s squared distance from his starting point increases by 1 with each step on average. If follows that his mean squared distance increases by 1 at each step. If we note that after his first step, he is a distance of 1 away from his starting point, then we have a proof by induction that the drunkard’s mean distance squared from his starting point at step k is equal to k. • Tom Nichols says: Problem #1: I can.t leave this one alone. Think about the number of paths to each point on the grid after each step. To get to a point on the grid, you have to take one step from an adjacent point, so the number of paths to that point at step n+1 is the sum of the paths to adjacent points at step n. When you do this, you get a sequence of diagrams representing the number of paths to each point. Note that any given point can only be visited on every other step. Step 0: ……………………………1 Step 1: ……………………………1 ……………………….1…0…1 ……………………………1 Step 2: …………………………….1 …………………………2..0..2 …………………….1…0..4..0..1 …………………………2..0..2 …………………………….1 Step 3: …………………………….1 …………………………3..0..3 ……………………..3..0..9..0..3 ………………….1..0..9..0..9..0..1 ……………………..3..0..9..0..3 …………………………3..0..3 …………………………….1 If you turn these diagrams on their sides (leaving out the zeros), they look like this: Step.0: …………………………1 Step 1: ………………………1….1 ………………………1….1 Step 2: ……………………1….2….1 ……………………2….4….2 ……………………1….2….1 Step 3: …………………1….3….3….1 …………………3….9….9….3 …………………3….9….9….3 …………………1….3….3….1 Notice that the first row of each matrix looks like a row of Pascal.s triangle: …………….1 …………1……1 ……..1……2……1 ….1……3……3……1 That is not surprising when you consider that you construct that row by adding together the numbers in the two adjacent positions from the previous array. This is exactly the rule for constructing Pascal’s triangle. The right- and left-hand and botttom rows of each array are constructed in the same way. The other elements are the products of the corresponding elements on the edges, that is n_rs = (n_0s)(n_r0). That also makes sense when you consider that you are constructing those elements by applying the Pascal’s triangle rule in two directions. Let’s number of the rows and columns of the rotated array for step n = 3: ……………r.=..0….1….2….3 ……..s.=..0…..1….3….3….1 …………..1…..3….9….9….3 …………..2…..3….9….9….3 …………..3…..1….3….3….1 and then consider the squared distance from the center of each element: ……………r.=..0….1….2….3 ……..s.=.0……9….5….5….9 …………..1…..5….1….1….5 …………..2…..5….1….1….5 …………..3…..9….5….5….9 In these rotated arrays the squared distances are sqdist (r,s) =2[(r-n/2)^2 + (s-n/2)^2 ] It is easier to see that these are the square distances by looking at the original unrotated array. Step 3 paths: …………..x.=..-3.-2.-1..0..1..2..3 ………..y.=.-3…………..1 ……………..-2……….3..0..3 ……………..-1……3..0..9..0..3 …………….. 0..1..0..9..0..9..0..1 …………….. 1……3..0..9..0..3 …………….. 2……….3..0..3 …………….. 3…………..1 Step 3 squared distances: …………..x.=..-3.-2.-1..0..1..2..3 ………..y.=.-3…………..9 ……………..-2……….5……5 ……………..-1……5……1……5 ………………0..9……1……1……9 ………………1……5……1……5 ………………2……….5……5 ………………3…………..9 The squared distances are x^2 + y^2. Now we can find the mean squared distance by summing up squared distances multiplied by their probabilities. Realizing that the probabilities are proportional to the number of paths (in the path array), and that they are binomial probabilities, we can write the mean squared distance at step n as MSD(n) = sum {n_choose_r n_choose_s (1/2)^2n sqdist(r,s)} …………… r,s Using the facts that the probabilities of any distribution sum to 1, and that the variance of this binomial distribution is: sum {n_choose_j (1/2)^n (j-n/2)^2} = n/4 ….j a little algebra gives us MSD(n) = n • Michael says: Problem 1: One fallacy is that the moves towards and away from the start are not equal: the two moves that bring him closer to the start only do so by ~0.63, while those that take him further away do so by a larger amount ~0.76. This holds more generally. Another less important factor is that there are no "circles" on a square grid. So, I guess to apply a similar simple argument, one would suppose he has moved by (m,n) to a reasonably large distance d=sqrt(m^2+n^2) after N moves. On the next move his displacement from the start is (m-1,n), (m+1,n), (m,n-1) or (m,n+1) with equal probabilities 1/4. Using the approximation sqrt{d^2 + x} = d sqrt{1 + x/d^2) ~ d(1+(1/2)x/d^2) = d + x/(2d) for each of the 4 displacements (which is accurate for large d), with x=1-2m, 1+2m, 1-2n, 1+2n respectively, one has <x>=1 and so the new average distance is d' = d + <x>/(2d) = d + 1/(2d). Assuming d=f(N) for some smooth function f, and approximating f'(N) = [ f(N+1) – f(N) ] / [N+1 – N ] = d' – d = 1/(2d) = f[N] for large N, gives the differential equation 2 f'(N) f(N) = 1, which has the solution d = f(N) = sqrt(N + c) for some constant c. Finally, since we would like f(0)=0, we must take c=0, and so end up with the average distance after N blocks being approximately d = sqrt(N). One nice aspect of the above argument is that it is trivial to generalise to an n-dimensional rectangular grid. There are 2n possible moves at each step, and again <x>=1 (by considering each of the n dimensions in turn), yielding the same answer. Getting the same answer in any number of dimensions surprised me at first, but it makes sense. The drunkard is really doing n 1-dimensional walks, taking N1 steps in the first dimension, N2 in the second, etc. On average he takes N/m steps in each dimension (randomly + or – each time), so the total distance moved on average, d_n(N), will satisfy, using Pythagoras, d_n(N)^2 = d_1(<N1>)^2 + d_1(<N2>)^2 +…. = m d_1(N/m)^2, which gives d_n(N) = sqrt{N} if d_1(N) = sqrt{N}. Other generalisations seem fairly easy too. Suppose the blocks are not squares but rectangles, with horizontal sides h and vertical sides v. Then following the same argument gives 2 f'(N) f(N) = <x> = (h^2+v^2)/2, leading to d = sqrt{ <length^2> N}. So, one just scales by the average square of the block size. Further, even if the horizontal block lengths vary according to some p(h), then one can 'bin' them into representative sizes, and carry out the same argument for each size to replace h^2 by <h^2>. This leads to the exactly the same formula as above for rectangular grids in n dimensions: d = sqrt{ <length^2> N } where <length^2> is the average square block size (averaged over all dimensions).. Finally, I wanted to think about generalising to non-rectangular grids. It seems easiest to keep them regular, e.g., triangular or hexagonal in 2D. So, then at each point one has m directions to move in, given by vectors v1,…,vm say (these can be in any number of dimensions we like). If the move is in the first direction, the drunkard will change from location vector v to v+v1, and hence from d=sqrt{v.v) to d1'=sqrt (v.v + 2v1.v +v1.v1) ~ d + (2v1.v + v1.v1) /(2d) using the same approximation as before. Hence, on average over all the m directions, the new distance from the start is d' = d + d' = 1 + <x>/(2d) by the same argument as before, where now <x> = (v1.v1 + v2.v2 + … ) /m and I am assuming that <v.(v1+v2 +…)>=0 (either by assuming that the vectors add to zero – guaranteed for regular grids – or instead that over the whole grid the location vectors v for a given distance average to 0). So again one gets back the formula d = sqrt{ <length^2> N }. Pretty robust formula! This has made me realise if one can go to the limit of a "grid" that has all possible directions? This would require the limit of infinitesimal steps, and should correspond to diffusion. I'll leave that for now though. • Jon Gerdes says: "Now, where are the funny math books today?" Nearly everything by Ian Stewart, "A Random Walk in Science" by RL Weber, "Gödel Escher Bach". Hmmm, "today" …. • Michael says: Problem 2 This seems quite hard! First, streets 0, 1, 2, 3 are equivalent to 8,7,6,5 for Sally, respectively, so we can consider her confined to streets 4, 5, 6, 7, 8, where if she moves to 4 then she will either stay at 4 (prob 1/2) or move to 5 (prob 1/2). So 4 acts like a mirror. Similarly, Al can be considered confined to avenues 4, 5, 6, 7, 8. So the problem is reduced to them walking on the same set {4,5,6,7,8}, and their positions at any time are coded by (S,A) where each of S and A are in this set. But it doesn't seem very symmetrical due to the 'mirror' at 4. Second, if Sally moves from 5 to S, she will gain S-5 coins from Al. Similarly, if Al moves from 6 to S, he will have received A-6 from Sally. So, their net gains for moving to configuration (S,A) are, respectively: Sally(S,A) = (S-5) – (A-6) = S – A + 1, Al(S,A) = (A-6) – (S-5) = A – S -1. These sum to zero since there is no source or sink of money. Third, if they "meet", i.e., S=A, at some point in a game, then from this point symmetry clearly implies they have equal chances of winning, and the same average win/loss of 0. But to get to this meeting, it follows that their net gains to this point are Sally(S,S)=1 and Al(S,S)=-1, and so this advantage will be preserved. So, <Sally>_meet = 1, <Al>_meet = -1. Conversely, if they never meet during a game, then at every stage A>S and so Al must win, with an expected net gain <Al>_0 = 8 – <S>_0 -1 = 7 – <S>_0 , where <S>_0 is Sally's average position at the end when they never meet. Hence, if the probability of never meeting in a game is p, then Al's probability of getting to 8 first is (1/2)(1-p)+p=(1+p)/2, i.e, he can expect to get to 8 before Sally, and his overall expected gain is <Al> = (1-p) (-1) + p (7 – <S>_0) = p ( 7 – <S>_0) – 1. (*) This is strictly positive if and only if p (7 – <S>_0) > 1. Note that since <S>_0 > 4, then it is only possible for Al to have a net advantage if p > 1/3. I get some better bounds below. Clearly, for the last result, Eq. (*), to be useful, one would like to get some bounds on p and/or <S>_p. For example, if S=5 at the end, which is, say, at n moves, then she moved from exactly one of S=4, 5 or 6 in the (n-1)th move (while Al must have been safely at 7 so he could win on the nth move), giving p(S=4,n) = (1/2) p(S=4,n-1) + (1/2) p(S=5,n-1) + (1/4) p(S=6,n-1) < 1/2. One can also show, by going back two moves, that p(S=4,n) < 3/8. Hence, <S>_0 > (3/8)4 + (1/2)5 + (1/8)6 = 19/4 =4.75 and so <Al> < p(2.25) – 1 = 9p/4-1. Hence, Sally is guaranteed to have an advantage if p <= 4/9. Similarly, if they haven't met in a game, then Sally could not be at position 7 just before the last move (since Al must be there to win on the next go), and hence her probability of being at 7 on the last move is p(7,n) = p(7,n|6,n-1) p(6,n-1) = (1/4) p(6,n-1). But to get to 6, and Al to be at 7 on move n-1, they must have come from (6,7), (5,7) or (5,6) two moves before the last move (since they didn't meet and Al hasn't won yet), and so p(6,n-1) = p(6,7,n-1) = p(6,7,n-1|6,7|n-2) p(6,7,n-2) + p(6,7,n-1|5,7|n-2) p(5,7,n-2) + p(6,7,n-1|5,6|n-2) p(5,6,n-2) = (1/4) p(6,7,n-2) + (1/8) p(5,7,n-2) + (1/6) p(5,6,n-2) < 1/4 . Thus, the probability of Sally being at 7 at the end of the game is bounded by p(7,n) < (1/4) (1/4) = 1/16. Similarly, if Sally is at position 6 at the last move, then she must have been at position 5 or 6 on move n-1 (since Al is at 7 and they cannot meet), and so p(6,n) = p(6,n|6,n-1) p(6,n-1) + p(6,n|5,n-1) p(5, n-1) = (1/2) p(6,n-1) + (1/4) p(5,n-1) < (1/2) p(6,n-1) < 1/8, using the bound for p(6,n-1) above. Putting these bounds together then gives <S>_0 < (1/16)7 + (1/8)6 + (13/16)5 = 21/4 = 5.25. Hence from Eq. (*), <Al> > p (7 – 5.25) – 1 = 7p/4 – 1. Hence, Al is guaranteed to have a net advantage if p>= 4/7. The above two paragraphs tell us that Sally has the advantage for 0 <= p <= 4/9, and that Al has the advantage for 4/7 <= p <= 1, where p is the probability that they do not meet during the game. This does not help if p is in the range 0.444444 to 0.571428. So, the next thing to do is to either (i) estimate p and find that it is in one of the two ranges that tell us something, or (ii) take a different approach (such as using 25×25 matrices of conditional probabilities, which has the advantage of giving all desired information about everything, or perhaps looking at the "mirror effect", the number of times that Sally hits 4). But I think I'll leave it for now (although my current guess is that Sally has the advantage). Maybe I should take a look at those hints! • Pradeep Mutalik says: Update – Problem 2 I realized that I missed adding a variant of Problem 2 that I had meant to. What if only the person who reaches his or her target gets the money? So if their moves were 6,5 -> 7,5 -> 7,6 -> 8,6 reaching 8th avenue, Al gets 2 dollars, Sally gets nothing. • Michael says: Problem 1 – Diffusion I see now there is another 'fallacy' re problem 1 – that the drunkard is always at the mean position. In practice there will be a spread about this. To get a more accurate estimate of the approximate distance, one has to estimate the probability of being at a given distance. Let p(m,n,s) be the probability that the drunkard has moved (m,n) from the starting point at step s. Then, since he will move away from (m,n) with probability 1 if he is at (m,n), and he will come to (m,n) with probability 1/4 if he is at any of (m+1,n), (m-1,n), (m,n+1) or (m,n-1), then the change in his probability of being there is p(m,n,s+1)-p(m,n,s) = – p(m,n,s) + (1/4)[p(m+1,n,s)+p(m-1,n,s)+p(m,n+1,s)+p (m,n-1,s)] = { [p(m+1,n,s)-p(m,n,s)] – [p(m,n,s)-p(m-1,n,s)] }/4 + { [p(m,n+1,s)-p(m,n,s)] – [p(m,n,s)-p (m,n-1,s)] }/4. If p(m,n,s) is approximated by a smooth probability p(x,y,t), with each step being of length L and taking time T, this becomes T dp/dt = (1/4) L^2 [ d^2p/dx^2 + d^2p/dy^2], which is a diffusion equation. The solution will be a Gaussian, which I've tried to derive below. We know that the drunkard moves independently in the x and y directions at each step. Hence, we expect p(x,y,t) = p(x,t) p(y,t) = f(x^2,t) g(x^2,t) for some functions f and g (the squares are because the problem is invariant under swapping x to -x or y to -y, so p(x,y,t) can't depend on the sign of x or y). We also expect, since the drunkard starts at (0,0), that f=g, but this doesn't have to be assumed at this point. Also, there is no preferred direction from the starting point, and so the probability should only depend on the distance r =sqrt{x^2+y^2} from the starting point, i.e., p(x,y,t) = h(r^2,t) for some function h, where r^2 is as good as r as a parameter. Hence f(x^2,t) g(y^2,t) = h(x^2+y^2) for all x and y, i.e., h(u+v,t) = f(u,t) g(v,t) for all positive u and v. Differentiating with respect to u or with respect to v gives h'(u+v,t) = f'(u,t) g(v,t) = f(u,t) g'(v,t), and so f'(u,t)/f(u,t) = g'(v,t)/g(v,t). Since the left hand side does not depend on u and the right hand side does not depend on v, then they must be equal to some function of t, -K(t) say. Solving f'(u)=-K(t) f(u) and similarly for g then gives f(u) = C1(t) exp[-K(t)u], g(v) = C2(t) exp[-K(t)v] for some functions C1 and C2. Putting this all together gives the form p(x,y,t) = C(t) exp[ -K(t) (x^2 + y^2) ], which is a Gaussian. Since probability must integrate to 1, changing to polar coordinates and then to w=r^2 gives 1 = int dx dy p(x,y) = int dr dtheta r C(t) exp[-K(t)r^2] = 2 pi C(t) (1/2) int dw exp[-K(t)w] =pi C(t)/K(t), and so C(t)=K(t)/pi, i.e., p(x,y,t) = K(t)/pi exp[ -K(t) (x^2 + y^2) ]. It follows that dp/dt = K'(t) [1/K – x^2 – y^2] p d^2p/d^x^2 + d^2p/dy^2 = -4K^2 [ [1/K – x^2 – y^2] p, and substituting into the diffusion equation then gives K'(t) = – (L^2/T) K^2, which has solution K(t) = (T/L^2) / (t + t0) for some t0. Finally, to get the average distance from the start, d(t), then similarly to the integration-to-one calculation, and using Wolfram alpha, d(t) = int dx dy sqrt[x^2+y^2] p(x,y,t) = int dr dtheta r r K(t)/pi exp[-K(t) r^2] = K(t) int dw sqrt{w} exp[-K(t) w] = (1/2) sqrt{pi / K(t)} = (1/2) L sqrt{ pi (t+t0)/T }. Since the average distance must be d(0)=0 at the start, then t0=0, and so the final expression is d(t) = (1/2) L sqrt{ pi t/T }. Taking L=T=1 this gives, in terms of the number of steps, N=s=t/T, d(N) = sqrt{pi}/2 sqrt{N} ~ 0.886 sqrt{N}. This is a remarkably small modification of the "naive" calculation that gave sqrt{N}. It would be interesting to see if there is a dependence on dimension. • Tom Nichols says: Problem #2. I want to outline an approach to an analytic solution of this problem. Let’s look at the game from Al’s point of view. His winnings at the end of the game depend on which intersection it ends on. If we recognize (as others have already done) that the final winnings are symmetric about 4th St and 4th Ave, then we can collapse the problem down to a grid of 5 streets by five avenues. Let’s number them 0 through 4 and assume that the game starts the intersection of 2nd Ave and 3rd St (equivalent to 6th Ave and 5th St). Then Al’s dollar winnings at the end of the game are s – a – 1, where s is the final street and a is the final avenue, irrespective of the path Al and Sally took to get there. Note that either s = 0 or a = 0 at the end of the game. The process of moving about the street grid can be represented as a Markov process with 25 states, each state representing an intersection. A 25 state Markov process is a bit difficult to work with, so let’s decompose it into two identical Markov processes, one representing North-South movement and the other East-West movement. This is possible because any given move is restricted to the N-S axis or the E-W axis. There is never motion along both axes at the same time. The same 5-state Markov transition matrix can be used for N-S and E-W motion P = _ . . . . . . . . . . . . . . . . . . . . . . . . . . . _ | . . 1.0. . . 0.5. . . . . . . . . . . . . . . . . | | . . . . . . . . . . . . . 0.5. . . . . . . . . . . . | | . . . . . . . . 0.5. . . . . . . 0.5. . . . . . . | | . . . . . . . . . . . . . 0.5. . . . . . . 1.0. . | |_ . . . . . . . . . . . . . . . . . 0.5. . . . . . ._| Before we go farther, observe that once the Markov process enters state 0, it can never leave. This allows us to eliminate state zero (the first row and column of P). We can still find the probability of entering state 0 after j steps as the ½ the probability of being in state 1 after j-1 steps. Our new transition matrix is then Pd = _. . . . . . . . . . . . . . . . . . . . . _ | . . . . . . . 0.5. . . . . . . . . . . . | | . . 0.5. . . . . . . 0.5. . . . . . . | | . . . . . . . 0.5. . . . . . . 1.0. . | |_. . . . . . . . . . . 0.5. . . . . . ._| We can represent the probabilities of being in states 1 through 4 after j moves as the vector S_j. Then S_j = Pd S_j-1 After j N-S moves and k E-W moves, Al and Sally end up at some intersection (s, a). The probability of j N-S and k E-W moves after a total of j+k moves is B(j,k) = (j+k)_choose_j (1/2)^(j+k) so the probability of being at location (s, a) after j+k moves is: R_jk(s, a | 3, 2) = E’_s Pd^k E_3 B(j,k) E’_a Pd^j E_2 where E_i is a unit vector whose ith element is 1.0, meaning that the probability of state i is 1.0 and the probabilities of the other states are zero. I am using the apostrophe to represent the matrix transpose. So the above expression represents the probability of starting at (3, 2), executing j N-S moves and k E-W moves, and ending at state (s, a). To get the probability of ending the game at a = 0 we must sum over j and k to find the probability of being at a = 1 and then multiply by ¼ to get the probability of entering state 0 after the next move. (This probability is ¼ because the players have four possible moves when a = 1.) Prob(s, 0 | 3, 2) = …..sum{R_jk(s, 1 | 3, 2)} / 4 …………………………j=0, 1, 2 . . . …………………………k=0, 1, 2 . . . Similarly, Prob(0, a | 3, 2) = …..sum{R_jk(1, a | 3, 2)} / 4 …………………………j=0, 1, 2 . . . …………………………k=0, 1, 2 . . . Now, Al’s expected winnings are W = …..sum{(s-1)Prob(s, 0 | 3, 2)} / 4+ …..sum{(-a-1)Prob(0, a | 3, 2)} / 4 …..…s=1, 2, 3, 4……………………………………a=1, 2, 3, 4 You might notice that I have not counted the final state (0, 0). There is no way to reach that state, so its probability is zero. Now, admittedly, this looks like an ugly calculation, but there are a couple of things we can do to make it less ugly. We can represent the transition matrix Pd using an eigendecomposition Pd = Q D Q_inv where D is a diagonal matrix of eigenvalues and the columns of Q are the corresponding eigenvectors. Then Pd^j = Q D^j Q_inv This makes it possible to collapse the sum Prob(s, 0 | 3, 2) = …..sum{R_jk(s, 0 | 3, 2)} / 4 …………………………j=0, 1, 2 . . . …………………………k=0, 1, 2 . . . to ….sum{ .5^k E’_s Q D^k Q_inv E_3 E’_1 Q (I-.5D)^(-k-1) Q_inv E_2} / 4 k=1, 2, 3 . . . Now we can form a 4X4 matrix M_k = .5^k D^k Q_inv E_3 E’_a Q (I-.5D)^(-k-1) with elements M_k(r,c) = Q_inv(r,3) Q(1,c) [.5D(r,r)]^k [I-.5d(c,c)]^(-k-1) Then Prob(s, 0 | 3, 2) = …..sum{ E’_s Q M_k Q_inv E_2} / 4 …………………………k=0, 1, 2 . . . ………………………= E’_s Q sum{M_k} Q_inv E_2} / 4 ……………………………….k=0, 1, 2 . . . Define M = …..sum{M_k} …………………k=0, 1, 2 . . . Then M(r,c)= ….sum{M_k(r,c)} = Q_inv(r,3) Q(a,c) [I – .5D(c,c) – .5D(r,r)]^(-1) …………..k=0, 1, 2 . . . Now we have a closed form solution for W, Al’s expected winnings. We can also solve Pradeep’s variant of the problem by changing the winnings function from (s-a-1) to 2 if a = 0 -3 if s = 0 Note that the eigenvectors and eigenvalues of Pd are (relatively) easy to compute, even by hand, by solving Pd X = d X for four pairs of values d and X, where X’ = [1, x_2, x_3, x_4], and then dividing each X by its normalizing constant ||X|| to get the eigenvector corresponding to the eigenvalue d. When I do this I get values for d of +/- sqrt[1/2 +/-sqrt(1/8)] I have not done the full calculation using this method, yet. I have done a quick implementation of the random walk with successive arrays of spreadsheet cells representing the probabilities of being at the different intersections at each step. This results in Sally winning by about 37 cents on average, if she does not get tired of walking first. • Wiley says: I am puzzled by Michael's version of problem 2. Just to clarify, Al and Sally always move together, no? I also find the following sentence confusing: "If the random direction is neutral with respect to the distance from either target, no money is exchanged.". Don't they exchange money for all the corners? Since there are two targets for each person, I assume by "distance", it means, e.g., for Al, the minimum of the distance of his position to 0th Avenue and the distance to 8th Avenue? The only tricky situation seems to be when they are on either 4th Avenue or 4th Street (but not on both). For instance when they are on the corner of 5th Avenue and 4th Street, then there is 50% probability (i.e., walking along 5th Avenue) that Al always loses$1 while there is 50% probability (along 4th Street) that Al would win $1 (to 6th Avenue) or lose$1 (to 4th Avenue).

If the interpretation above is correct, here is the standard one-step analysis:
http://i.imgur.com/vXkeVeT.png

where the blue variables are the expected win for Al. Note the expected win
(1) is zero along the diagonals due to symmetry;
(2) is zero on the edges as the game ends;
(3) has mirror symmetry with respect to 4th Street.

The linear system results d=-25/68, i.e., Sally expects to have a long term edge of roughly 37 cents.

• Wiley says:

For the variant of problem 2 in Pradeep's update, since the payouts are constant: either Al wins $2 or he loses$3, all we need is each player's winning probability.

We can apply the similar one-step analysis (see the graph in an earlier post), except the blue variables are now the winning probability for Al, and the probability
(1) is 1/2 along the diagonals due to symmetry;
(2) is 1 along 8th Avenue, as it's a winning position for Al;
(3) has the same mirror symmetry with respect to 4th street.

The linear system results d=327/544~60.11%, i.e., Al expects to have a long-term edge (albeit small) of d*2-(1-d)*3~0.55 cents.

• Tom Nichols says:

I did the calculations for the Markov process method. My results agree exactly with Wiley's

• Michael says:

Problem 2:
I should, in my previous analysis, have defined p to be the probability of not meeting OR crossing (since they can swap places on some moves). This is strictly larger than When this is the case, Al must win as before, since A>S always. But one must further consider the case where they never meet but do swap places, in calculating <Al>. So my previous bounds are down the gurgler. 🙁

For fun, since it only requires a 10×10 matrix of conditional probabilities, I worked out the probabilities of Sally being at 4, 5, 6, 7 and 8 at the end of the game, if they never meet or swap. They are given by 0.237, 0.425, 0.263, 0.075, and 0, respectively. So, her average position at the end is at 5.2 in this case, giving Al a corresponding average payoff of 1.8. But this has little to do with the actual problem, of course.

• Søren Lassen says:

I think Marty Green's informal argument is somewhat misleading, as the average distance also increases when taking steps in only one dimension: if the drunkard is standing on a road running north-south, and taking equal length steps either to the north or to the south, his average distance distance from the origin will also increase with the number of steps taken, proportionally with the square root of the number of steps.

When he is away from the point of origin, the next step he takes will not change his average distance from the origin. But when he is standing on the origin, the next step is bound to increase his distance by one step. So the first step will increase his average distance by 1. The second step will not increase his average distance, as he cannot be standing on the point of origin after an odd number of steps. The third step will increase his average distance by 1/2, which is the probability that he starts on the point of origin, where he is bound to increase his distance. The fifth step will increase his average distance by the probability that he is on the point of origin after 4 steps (6/16), etc.

The real point here is that when you sum a large number (let's say N) of stochastic variables with the same distribution (and well-defined mean and variance), you will approximate a normal distribution with a variance that is N times the variance of a single variable. Which means that the standard deviation is the square root of N times the standard deviation of a single variable. And the average distance from the center point in a normal distribution is proportional to the standard deviation.

• Henri LeGrand says:

Sally always wins because she is the one with the gun.