How Likely Is Pólya’s Drunkard to Return to the Pub Without Getting Mugged? (In d-Dimensional Manhattan [d ≥ 2])

Doron Zeilberger ^{1}

In 1921, George Pólya[P] (see also [DS], ch. 7) famously proved that if a drunkard leaves a pub situated at the origin, in a d-dimensional Manhattan (w/o Broadway), and where he is allowed to only walk on streets and avenues, then he will return to the pub with probability 1 if d ≤ 2, but with probability < 1 if d > 2. Later writers (see [F], sec. 5.9) computed (calling this probability p_{d}), that p_{3} = .340537 …, p_{4} = .193201 …, p_{5} = .135178 …, p_{6} = .104715 …, etc.

But Pólya unrealistically assumed that it is safe to walk everywhere in Manhattan. As we all know, in some areas, a person-especially if he looks drunk-is guaranteed to get mugged.

In 1989, Jet Wimp and I ([WimZ]) determined that, in a 3-dimensional Manhattan, where it is only safe to walk in {(x_{1}, x_{2}, x_{3}) ∈ Z^{3} | x_{1} ≥ x_{2} ≥ x_{3}}, the probability of returning to the pub, without getting mugged, is .0648447 . . ..

But what about other dimensions and other regions? In this note, we will answer the following questions.

What are the probabilities of a simple random walker, starting at the origin of Z^{d}, and walking with unit positive steps, to return to the origin and stay in:

(a) {(x_{1}, …, x_{d}) ∈ Z^{d} | x_{1} ≥ 0 , x_{2} ≥ 0 , …, x_{d} ≥ 0 } ,

(b) {(x_{1}, …, x_{d}) ∈ Z^{d} | x_{1} ≥ … ≥ x_{d} } ,

(c) {(x_{1}, …, x_{d}) ∈ Z^{d} | x_{1} ≥ … ≥ x_{d} ≥ 0 } ?

Calling these quantities a_{d}, b_{d}, c_{d}, we found, using the Maple package DRUNKARD accompanying this article, that

a_{2} = 0.1731362517 …, b_{2} = 0.2146018366 …, c_{2} = 0.07422872309 …,

a_{3} = 0.1019012545 …, b_{3} = 0.064844715377 …, c_{3} = 0.0295951553088 …,

a_{4} = 0.072168388084 …, b_{4} = 0.0336123617 …, c_{4} = 0.01615664624 …,

a_{5} = 0.05590880956867 …, b_{5} = 0.020894826887 …, c_{5} = 0.01021082007 ….

1 Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen

Rd., Piscataway, NJ 08854-8019, USA. zeilberg@math.rutgers.edu, http://www.math.rutgers.edu/~zeilberg/ .

Dec. 17, 2007. Accompanied by the Maple package DRUNKARD downloadable from Zeilberger’s website. Exclusively published in the Personal Journal of Ekhad and Zeilberger http://www.math.rutgers.edu/~zeilberg/pj.html.

Supported in part by the NSF.

(Note that b_{3} was the subject matter of [WimZ].)

DRUNKARD

The Maple package DRUNKARD “accompanying” this article (to be fair, this article accompanies the package) has lots of interesting related features.

One thing it can also do is compute the probability of making it home from the pub without getting mugged. See procedures Pr0, Pr1, Pr2, Pr3. Pr0 handles the unrestricted case, while Pr1, Pr2, Pr3 take care of the above-mentioned regions (a), (b), (c) respectively. For example, “Pr3([3,2],[6,4]);” computes the probability of leaving point [3, 2] and eventually making it to point [6, 4] without ever going outside of {(x, y)|x ≥ y ≥ 0}. By the way, it happens to be %6.887 . . ..

DRUNKARD also computes the sequences enumerating the number of n-step walks starting at S and ending at F (for any S and F, in particular where both are the origin) both unrestricted, and staying in each of the above regions. In fact, it computes them in three different ways. The first way is by implementing the obvious recurrences, the second way is by using the Gessel-Zeilberger[GeZ] Constant Term Expressions (equivalent to trigonometric integrals), while the third way is via exponential generating functions, using Grabiner-Magyar-style formulas (the package computes them ab initio, without actually entering their formulas. All we used were the ideas, that we taught to our computer). They all agree! Which means that the probability that they are all correct is very high.

Mathematics

Strictly speaking, there is no new mathematics in this note, its novelty is in the (hopefully) efficient implementation of already existing mathematics, that can be found in [GeZ], [GrM], and in the references of [F], sec. 5.9.

The readers are very welcome to browse the source code of DRUNKARD, read the documentation, and experiment with it.

Let me just briefly describe how DRUNKARD computes the above probabilities of return. Just like in the unrestricted case, if f(t) is the exponential generating function for the sequence enumerating n-step walks, from and to the origin, obeying the restrictions, then the expected number of visits, m, is ∫_{0}^{∞} f(t/(2k))e^{−t} dt (why?). If the probability of return is p, then of course m = 1/(1 − p) and so p = 1 − 1/m. The exponential generating function, in each case, is expressible as a certain polynomial expression in various Modified Bessel functions, J_{m}(t) := ∑_{k=0}^{∞} \frac{t^{k}}{k!(m+k)!} (see [GrM]), and that expression is computed automatically by our Maple package.

Sample Input and Output

The webpage of this article

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/drunkard.html

has some input and output. The readers can generate much more on their own. Asymptotics If M_{0}(d; n), M_{1}(d; n), M_{2}(d; n), M_{3}(d; n) are the number of ways of walking from the origin, back to the origin, in 2n steps, in Z^{d}, {(x_{1}, …, x_{d}) ∈ Z^{d}|x_{1} ≥ 0, …, x_{d} ≥ 0}, {(x_{1}, …, x_{d}) ∈ Z^{d}|x_{1} ≥ x_{2} ≥ … ≥ x_{d}}, and {(x_{1}, …, x_{d}) ∈ Z_{d}|x_{1} ≥ x_{2} ≥ … ≥ x_{d} ≥ 0}, respectively, for fixed d, and as n → ∞, we have the asymptotics

\frac{M_{0}(d; n)}{(2d)^{2n}} ∼ C_{0}(d) · n^{−d/2} , \frac{M_{1}(d; n)}{(2d)^{2n}} ∼ C_{1}(d) · n^{−3d/2} ,

\frac{M_{2}(d; n)}{(2d)^{2n}} ∼ C_{2}(d) · n^{−d^{2}/2} , \frac{M_{3}(d; n)}{(2d)^{2n}} ∼ C_{3}(d) · n^{−(d^{2}+d/2)} .

These can be obtained, using standard asymptotic methods, from the integral representation formulas alluded to at the end of [GeZ]. We leave the details to the interested readers. References

[DS] P.G. Doyle and J.L. Snell, “Random Walks and Electric Networks”, Math. Assoc. of America, 1984.

[F] S.R. Finch, “Mathematical Constants”, Cambridge University Press, 2003.

[GeZ] I. Gessel and D. Zeilberger, Random Walk in a Weyl chamber, Proc. Amer. Math. Soc. 115, 27-31 (1992).

[GrM] D. Grabiner and P. Magyar, Random Walks in a Weyl Chamber and the decomposition of tensor powers, J. Alg. Combinatorics 2 (1993), 239-260.

[P] G. Pólya, Über eine Aufgabe der Wahrscheinlichkeitsrechnung betreffend die Irrfahrt im Stassennetz, Math. Annalen 84 (1921), 149-160. Also in “Collected Papers”, v. 4, ed. G. -C. Rota, MIT Press, 1984, 69-80, 609.

[WimZ] J. Wimp and D. Zeilberger, How likely is Polya’s drunkard to stay in x ≥ y ≥ z? J. Stat. Physics 57 (1989), 1129-1135.