How Likely is Polya's Drunkard to Return to the Pub Without Getting Mugged?
(In d-Dimensional Manhattan [d ≥ 2])
By Doron Zeilberger
.pdf
.ps
.tex
Exclusively published in the Personal Journal of Ekhad and Zeilberger.
Written: Dec. 18, 2007.
Polya told us that it is safe to get drunk in two dimensions, but in three dimensions
we have about 66% chance of never making it back home. Sadly, if some parts of the
plane are dangerous, then it is not even safe to get drunk in
two dimensions, and in three and higher dimensional space, the chances of returning home safely
are much smaller than 34%. So stay sober!
Important: This article is accompanied by the Maple
package
DRUNKARD,
that computes sequences, and Polya-constants for Restriced (simple) random walks.
Sample Input and Output
To get the first fifty terms sequences enumerating the number of 2n-step walks from the
origin back to the origin, unrestricted, and restricted to the three
domains
- (a) x1 ≥ 0, ... xd ≥ 0,
- (b) x1 ≥ x2 ≥ ... ≥ xd
- (c) x1 ≥ x2 ≥ ... ≥ xd ≥ 0
for d=2,3,4,5,
as well as the Polya constants, and when feasible, recurrence relations and asymptotics,
the
input would
yield the
output.
-
To just get the probabilities of return for the unrestricted case and the above
three regions
input would
yield the
output.
Personal Journal of Ekhad and
Zeilberger
Doron Zeilberger's Home Page