\input amstex
\documentstyle{amsppt}
\magnification=\magstep1
\font\sc=cmcsc10
\hfuzz=10pt
\document
\NoRunningHeads
\TagsOnRight
\topmatter
\title
{Letter to the editor}\\ \phantom{sdfsdf}\\
Some comments on the higher moments of the number of returns of a simple
random walk
\endtitle
\author Peter Kirschenhofer and Helmut Prodinger \endauthor
\affil
Department of Algebra and Discrete Mathematics \\
Technical University of Vienna, Austria
\endaffil
\address \flushpar TU Vienna\newline
Department of Algebra and Discrete Mathematics
\newline Wiedner Hauptstrasse 8--10
\newline A-1040 Vienna
\newline Austria
\endaddress
\keywords random walk, generating functions, moments, singularity analysis
\endkeywords
\email kirsch\@email.tuwien.ac.at, proding\@email.tuwien.ac.at
\endemail
\endtopmatter
\define\kapa{2}
\define\kapaa{3}
\define\awk{4}
\def\flaodl{1}
\def\rkemp{5}
Let $X_k$, $k=1,2,\dots$ be independent and identically distributed
random variables with $\Bbb P\{X_k=1\}=\Bbb P\{X_k=-1\}=\frac12$.
Consider the simple random walk
$$
S_m=\sum_{k=1}^mX_k \qquad \text{with}\quad S_0=0\quad\text{and}\quad S_{2n}=0,
$$
i.e. a simple random walk starting at 0 and leading to 0 after $2n$ steps.
To this random walk the random variable $T=[${\sc number of visits to the
origin}$]$ is associated.
In \cite\kapa\ the higher moments of this random variable were expressed as
sums where the number of terms increases with $n$. The authors also
gave asymptotic formul\ae\ by means of a Mellin transform approximation
of the sums. In a following paper \cite\awk\ the higher moments are
described by certain recurrence relations with ``full history''.
The aim of this note is, motivated by a comment in \cite\kapa,
to give closed form expressions (i.e. the number of terms is
independent of $n$) for the moments in question. Also we
perform a generating functions approach that allows to get the
asymptotics in an elementary and easy way and add two more problems
where this kind of approach can be used.
\define\W{\Cal W}\redefine\O{\Cal O}
In order to get a well suited generating function we decompose the family
$\W$ of random walks in question according to their returns. Noting
that between any two consecutive returns a walk is either positive ($\W_+$)
or negative ($\W_-$) we have
$$
\W=\Big(\W_++\W_-\Big)^\ast.\tag1
$$
It is well known that the generating function of $\W_+$ (resp. $\W_-$)
involves the {\sc Catalan} numbers. Counting the upward steps by the
variable $z$ and the returns by $u$ we find the bivariate generating
function
$$
W(z,u)=\frac{1}{1-2uC(z)},\tag2
$$
where
$$
C(z)=\frac{1-\sqrt{1-4z}}{2}.
$$
The reader should observe that the origin
is not counted as a return.
The generating function of the $s$--th factorial moments multiplied by
$\binom{2n}n$ is given by
$$
M_s(z)=\frac{\partial^s}{\partial u^s}W(z,u)\bigg|_{u=1}
=s!\frac{\Big(1-\sqrt{1-4z}\,\Big)^s}{\Big(\sqrt{1-4z}\,\Big)^{s+1}}.\tag3
$$
Expanding the numerator by the binomial theorem we rewrite \thetag3 as
$$
M_s(z)=s!\sum_{i=0}^s\binom si(-1)^i(1-4z)^{\frac{i-s-1}{2}},\tag4
$$
so that the factorial moments $m_s(n)$ fulfill
$$
\binom{2n}nm_s(n)=[z^n]M_s(z)
=s!\sum_{i=0}^s\binom si(-1)^i(-4)^n\binom{\frac{i-s-1}{2}}n.
$$
Converting the binomial coefficient and substituting $i$ by $s-i$ we
finally get
$$
m_s(n)=\bigg\{s!(-1)^s4^n\sum_{i=0}^s\binom si(-1)^i
\binom{\frac{i-1}{2}+n}n\bigg\}\bigg/\binom{2n}n\tag5
$$
We note that for even values $i=2j$ the binomial coefficient in \thetag5
reads
$$
\binom{\frac{i-1}{2}+n}n=\frac{(2n+2j)!j!}{4^nn!(2j)!(n+j)!},
$$
so that \thetag5 can also be rewritten as
$$\aligned
m_s(n)=\bigg\{&s!(-1)^{s+1}4^n\sum_{j\ge0}\binom{s}{2j+1}\binom{n+j}{n}\\
&+
s!(-1)^s\sum_{j\ge0}\binom s{2j}\frac{(2n+2j)!j!}{n!(2j)!(n+j)!}\bigg\}
\bigg/\binom{2n}n.\endaligned\tag6
$$
The main advantage of formul\ae\ \thetag5 resp. \thetag6 is that the number
of terms only depends on $s$ (despite of $n$ in \cite\kapa).
Furthermore from \thetag4 a full asymptotic expansion of the moments follows
immediately by Darboux's method (or `singularity analysis'), compare
\cite{\flaodl}.
By means of the Stirling numbers, these formul\ae\ can easily be rewritten
in terms of the usual moments, still comprising only about $s$ terms.
\medskip
\def\G{\Cal G}
In order to demonstrate the advantages of our approach we also investigate
the number of returns for general random walks $\G$, leading
from $(0,0)$ to $(n,i)$, where $i$ is arbitrary. Naturally, we must
consider general $n$, and not only {\sl even} $n$, as before.
With $\W_+$ and $\W_-$ from above and $\O_+$ \ ($\O_-$) the family of
positive (negative) open walks ending above (below) the $x$--axis
we have
$$
\G=\Big(\W_++\W_-\Big)^\ast\cdot\Big(\varepsilon+\O_++\O_-\Big)
.\tag7
$$
In order to get the generating function of the extra term $(\varepsilon+\O_++\O_-)$
we factorize this part of the walk according to the last visits of each
level between the $x$--axis and the final level $i$. In this manner we
achieve
$$
1+2\frac{\frac1zC(z^2)}{1-\frac1zC(z^2)}=\frac{z+C(z^2)}{z-C(z^2)}
=\frac{\sqrt{1+2z}}{\sqrt{1-2z}}=\frac{1+2z}{\sqrt{1-4z^2}},\tag8
$$
and thus
$$
G(z,u)=W(z^2,u)\cdot\frac{1+2z}{\sqrt{1-4z^2}}.\tag9
$$
The extra factor does not depend on $u$, whence we see
$$M_s(z)=
s!\frac{\Big(1-\sqrt{1-4z^2}\,\Big)^s}{\Big(\sqrt{1-4z^2}\,\Big)^{s+1}}
\cdot\frac{1+2z}{\sqrt{1-4z^2}}
.\tag10
$$
Now even and odd powers are easily distinguished,
$$
[z^{2n}]M_s(z)=[z^n]s!\frac{\Big(1-\sqrt{1-4z}\,\Big)^s}{\Big(\sqrt{1-4z}
\,\Big)^{s+2}}
=\frac12[z^{2n+1}]M_s(z),\tag11
$$
and the machinery from before works perfectly. Since, in order to obtain
the moments, these numbers have to be divided by $2^{-2n}$ and
$2^{-2n-1}$, respectively, we see the coincidence between an even number
and the consecutive odd one. So we find
$$
m_s(n)=s!\sum_{i=0}^s\binom si(-1)^{s-i}\binom{\frac i2+\left\lfloor
\frac n2\right\rfloor}{\left\lfloor
\frac n2\right\rfloor}.\tag 12
$$
\medskip
Finally we cite a third problem that can be analyzed easily with the generating
function approach, namely the number of times where a simple random
walk reaches its maximum. This was recently studied in \cite\kapaa\ by
different methods.
We start from the observation that each random walk leading from $(0,0)$
to $(2n,0)$ can be generated in the following way. We take any
non-positive random walk from $(0,0)$
to $(2n,0)$, cut the first sojourn at any point different from its
right end and glue together the cut off part with the
end. The maxima of the produced random walk at time $>0$ correspond
obviously to the returns (at time $>0$) to the $x$--axis of the original
non-positive walk.
The generating function for counting the latter occurrences is therefore
$$
1+\frac{2zu}{\sqrt{1-4z}}\frac{1}{1-uC(z)},\tag13
$$
since the term $\frac{2z}{\sqrt{1-4z}}$ is the generating function of
the $2n\cdot \frac1n\binom{2n-2}{n-1}=2\binom{2n-2}{n-1}$ ``marked''
negative Catalan paths between the origin and the first return. Therefore
the corresponding generating function $M_s(z)$ reads
$$\aligned
&\frac{s!\Big(1-\sqrt{1-4z}\,\Big)^{2s+1}}{\sqrt{1-4z}}+s
\frac{(s-1)!\Big(1-\sqrt{1-4z}\,\Big)^{2s-1}}{\sqrt{1-4z}}\\ &=
\frac{s!}{\sqrt{1-4z}}\Big(1-\sqrt{1-4z}\,\Big)^{2s-1}
\Big(3-4z-2\sqrt{1-4z}\Big),\endaligned\tag14
$$
from which the moments as well as their asymptotics are immediate.
\medskip
We note that the corresponding maximum problem for non-negative paths
is considerably harder, and was studied in \cite{\rkemp}.
\Refs\ref \no \flaodl \by P.Flajolet and A.Odlyzko \pages 216--240\paper
Singularity Analysis of Generating Functions\yr 1990 \vol 3
\jour SIAM J. Disc. Math.
\endref
\ref \no \kapa \by W.Katzenbeisser and W.Panny\paper
A note on the higher moments of the random variable $t$ associated
with the number of returns of a simple random walk
\jour Advances of Applied Probability \vol18\yr 1986\pages279--282
\endref
\ref \no \kapaa \by W.Katzenbeisser and W.Panny\paper
On the number of times where a simple random walk reaches its maximum
\jour Journal of Applied Probability \vol29\yr 1992\pages305--312
\endref
\ref \no \awk \by A.W.Kemp\paper The moments of the random variable
for the number of returns of a simple random walk\yr 1987\vol19\pages
505--507
\jour Advances of Applied Probability
\endref
\ref\no\rkemp\by R.Kemp\paper On the number of deepest nodes in ordered
trees\jour Discrete Mathematics\vol81\yr 1990\pages247--258
\endref
\endRefs
\enddocument