%%drunkard.tex: %%a Plain TeX file by Doron Zeilberger (3 pages) %begin macros \def\L{{\cal L}} \baselineskip=14pt \parskip=10pt \def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height 0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule height0.15cm width 0.01cm}} \font\eightrm=cmr8 \font\sixrm=cmr6 \font\eighttt=cmtt8 \magnification=\magstephalf \def\P{{\cal P}} \def\Q{{\cal Q}} \def\1{{\overline{1}}} \def\2{{\overline{2}}} \def\Tilde{\char126\relax} \parindent=0pt \overfullrule=0in \def\frac#1#2{{#1 \over #2}} %\headline={\rm \ifodd\pageno \RightHead \else \LeftHead \fi} %\def\RightHead{\centerline{ %Title %}} %\def\LeftHead{ \centerline{Doron Zeilberger}} %end macros \bf \centerline { How Likely Is P\'olya's Drunkard to Return to the Pub Without Getting Mugged? } \centerline { (In $d$-Dimensional Manhattan [$d \geq 2$]) } \rm \bigskip \centerline{ {\it Doron Zeilberger} \footnote{$^1$} {\eightrm \raggedright Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA. %\break {\eighttt zeilberg@math.rutgers.edu}, {\eighttt http://www.math.rutgers.edu/\Tilde zeilberg/} . Dec. 17, 2007. Accompanied by the Maple package {\eighttt DRUNKARD} downloadable from Zeilberger's website. Exclusively published in the Personal Journal of Ekhad and Zeilberger {\eighttt http://www.math.rutgers.edu/\Tilde zeilberg/pj.html}. Supported in part by the NSF. } } In 1921, George P\'olya[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 \leq 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 \dots$, $p_4=.193201 \dots$, $p_5= .135178 \dots$ , $p_6=.104715 \dots $, etc. But P\'olya 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 {\it 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) \in Z^3 \, \vert \, x_1 \geq x_2 \geq x_3\}$, the probability of returning to the pub, {\it without getting mugged}, is $.0648447 \dots$. 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, \dots, x_d) \in Z^d \, \vert \, x_1 \geq 0 \, , \, x_2 \geq 0 \, , \, \dots \, , \, x_d \geq 0 \, \}$ \quad , (b) $\{(x_1, \dots, x_d) \in Z^d \, \vert \, x_1 \geq \dots \geq x_d \, \}$ \quad , (c) $\{(x_1, \dots, x_d) \in Z^d \, \vert \, x_1 \geq \dots \geq x_d \geq 0 \, \}$ \quad ? Calling these quantities $a_d,b_d,c_d$, we found, using the Maple package {\tt DRUNKARD} accompanying this article, that $a_2=0.1731362517\dots \quad , \quad b_2=0.2146018366 \dots\quad , \quad c_2=0.07422872309 \dots \quad ,$ $a_3=0.1019012545 \dots \quad , \quad b_3=0.064844715377 \dots \quad , \quad c_3=0.0295951553088 \dots \quad ,$ $a_4=0.072168388084 \dots \quad , \quad b_4=0.0336123617 \dots \quad , \quad c_4=0.01615664624 \dots \quad , $ $a_5=0.05590880956867 \dots \quad , \quad b_5=0.020894826887 \dots \quad , \quad c_5=0.01021082007 \dots \quad . $ (Note that $b_3$ was the subject matter of [WimZ].) {\bf DRUNKARD} The Maple package {\tt 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 {\it home} from the pub without getting mugged. See procedures {\tt Pr0, Pr1, Pr2, Pr3}. {\tt Pr0} handles the unrestricted case, while {\tt Pr1, Pr2, Pr3} take care of the above-mentioned regions $(a),(b),(c)$ respectively. For example, ``{\tt 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) \vert x \geq y \geq 0 \}$. By the way, it happens to be $\%6.887 \dots $. {\tt 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 {\it 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 {\it ab initio}, without actually entering their formulas. All we used were the {\it ideas}, that we taught to our computer). They all agree! Which means that the probability that they are all correct is very high. {\bf Mathematics} Strictly speaking, there is no {\it new} mathematics in this note, its novelty is in the (hopefully) {\bf 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 {\it source code} of {\tt DRUNKARD}, read the documentation, and experiment with it. Let me just briefly describe how {\tt 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 {\it expected number of visits}, $m$, is $\int_{0}^{\infty} 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):=\sum_{k=0}^{\infty} {{t^k} \over {k!(m+k)!}}$ (see [GrM]), and that expression is computed automatically by our Maple package. {\bf Sample Input and Output} The webpage of this article {\tt http://www.math.rutgers.edu/\Tilde zeilberg/mamarim/mamarimhtml/drunkard.html} has some input and output. The readers can generate much more on their own. {\bf 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, \dots, x_d) \in Z^d \vert x_1 \geq 0, \dots, x_d \geq 0 \}$, $\{(x_1, \dots, x_d) \in Z^d \vert x_1 \geq x_2 \geq \dots \geq x_d \}$, and $\{(x_1, \dots, x_d) \in Z_d \vert x_1 \geq x_2 \geq \dots \geq x_d \geq 0\}$, respectively, for fixed $d$, and as $n \rightarrow \infty$, we have the asymptotics $$ {{M_0(d; n)} \over {(2d)^{2n}} } \sim C_0(d) \cdot n^{-d/2} \quad , \quad {{M_1(d; n)} \over {(2d)^{2n}} }\sim C_1(d) \cdot n^{-3d/2} \quad , \quad $$ $$ {{M_2(d; n)} \over {(2d)^{2n}} }\sim C_2(d) \cdot n^{-d^2/2} \quad , \quad {{M_3(d; n)} \over {(2d)^{2n}}} \sim C_3(d) \cdot n^{-(d^2+d/2)} \quad . $$ 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. {\bf References} [DS] P.G. Doyle and J.L. Snell, {\it ``Random Walks and Electric Networks''}, Math. Assoc. of America, 1984. [F] S.R. Finch, {\it ``Mathematical Constants''}, Cambridge University Press, 2003. [GeZ] I. Gessel and D. Zeilberger, {\it Random Walk in a Weyl chamber}, Proc. Amer. Math. Soc. {\bf 115}, 27-31 (1992). [GrM] D. Grabiner and P. Magyar, {\it Random Walks in a Weyl Chamber and the decomposition of tensor powers}, J. Alg. Combinatorics {\bf 2} (1993), 239-260. [P] G. P\'olya, {\it \"Uber eine Aufgabe der Wahrscheinlichkeitsrechnung betreffend die Irrfahrt im Stassennetz}, Math. Annalen {\bf 84} (1921), 149-160. Also in {\it ``Collected Papers''}, v. 4, ed. G. -C. Rota, MIT Press, 1984, 69-80, 609. [WimZ] J. Wimp and D. Zeilberger, {\it How likely is Polya's drunkard to stay in $x \geq y \geq z$? J. Stat. Physics {\bf 57} (1989), 1129-1135. \end