

%%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



