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